下载文档原格式
STL的基本操作指令list :Lists将元素按顺序储存在链表中. 与向量(vectors)相⽐, 它允许快速的插⼊和删除，但是随机访问却⽐较慢. assign() 给list赋值back() 返回最后⼀个元素begin() 返回指向第⼀个元素的迭代器clear() 删除所有元素empty() 如果list是空的则返回trueend() 返回末尾的迭代器erase() 删除⼀个元素front() 返回第⼀个元素get_allocator() 返回list的配置器insert() 插⼊⼀个元素到list中max_size() 返回list能容纳的最⼤元素数量merge() 合并两个listpop_back() 删除最后⼀个元素pop_front() 删除第⼀个元素push_back() 在list的末尾添加⼀个元素push_front() 在list的头部添加⼀个元素rbegin() 返回指向第⼀个元素的逆向迭代器remove() 从list删除元素remove_if() 按指定条件删除元素rend() 指向list末尾的逆向迭代器resize() 改变list的⼤⼩reverse() 把list的元素倒转size() 返回list中的元素个数sort() 给list排序splice() 合并两个listswap() 交换两个listunique() 删除list中重复的元素String类：1) string s; //⽣成⼀个空字符串s2) string s(str) //拷贝构造函数⽣成str的复制品3) string s(str,index) //将字符串str内“始于位置index”的部分当作字符串的初值4) string s(str,index, n) //将字符串str内“始于index且长度顶多n”的部分作为字符串的初值5) string s(cstr) //将C字符串作为s的初值6) string s(chars,chars_len) //将C字符串前chars_len个字符作为字符串s的初值。
STL（标准模板库）基本概念⼀、什么是STLSTL（Standard Template Library，标准模板库)的从⼴义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），容器和算法通过迭代器可以进⾏⽆缝地连接。
⼏乎所有的代码都采⽤了模板类和模板函数的⽅式，这相⽐于传统的由函数和类组成的库来说提供了更好的代码重⽤机会。
在C++标准中，STL被组织为下⾯的13个头⽂件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>。
STL详细的说六⼤组件– 容器（Container）– 算法（Algorithm）– 迭代器（Iterator）– 仿函数（Function object）– 适配器（Adaptor）– 空间配制器（allocator）使⽤STL的好处1）STL是C++的⼀部分，因此不⽤额外安装什么，它被内建在你的编译器之内。
2）STL的⼀个重要特点是数据结构和算法的分离。
尽管这是个简单的概念，但是这种分离确实使得STL变得⾮常通⽤。
例如，在STL的vector容器中，可以放⼊元素、基础数据类型变量、元素的地址；STL的sort()函数可以⽤来操作vector,list等容器。
1）程序员可以不⽤思考STL具体的实现过程，只要能够熟练使⽤STL就OK了。
这样他们就可以把精⼒放在程序开发的别的⽅⾯。
2） STL具有⾼可重⽤性，⾼性能，⾼移植性，跨平台的优点。
⾼可重⽤性：STL中⼏乎所有的代码都采⽤了模板类和模版函数的⽅式实现，这相⽐于传统的由函数和类组成的库来说提供了更好的代码重⽤机会。
STL常用总结Last Update (July. 2014) by WINGACM/ICPC 竞赛之STL 简介一、关于STLSTL(Standard Template Library，标准模板库）是C++语言标准中的重要组成部分。
STL 以模板类和模板函数的形式为程序员提供了各种数据结构和算法的精巧实现，程序员如果能够充分地利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。
STL 大致可以分为三大类：算法(algorithm)、容器(container)、迭代器(iterator)。
STL 容器是一些模板类，提供了多种组织数据的常用方法，例如vector(向量，类似于数组)、list(列表，类似于链表)、deque(双向队列)、set(集合)、map(映象)、stack(栈)、queue(队列)、priority_queue(优先队列)等，通过模板的参数我们可以指定容器中的元素类型。
STL 算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序）。
STL 迭代器是对C 中的指针的一般化，用来将算法和容器联系起来。
几乎所有的STL 算法都是通过迭代器来存取元素序列进行工作的，而STL 中的每一个容器也都定义了其本身所专有的迭代器，用以存取容器中的元素。
有趣的是，普通的指针也可以像迭代器一样工作。
熟悉了STL 后，你会发现，很多功能只需要用短短的几行就可以实现了。
通过STL，我们可以构造出优雅而且高效的代码，甚至比你自己手工实现的代码效果还要好。
STL 的另外一个特点是，它是以源码方式免费提供的，程序员不仅可以自由地使用这些代码，也可以学习其源码，甚至按照自己的需要去修改它。
下面是用STL 写的题Ugly Numbers 的代码：#include <iostream>#include <queue>using namespace std;typedef pair<unsigned long, int> node_type;int main(){unsigned long result[1500];priority_queue< node_type, vector<node_type>, greater<node_type> >Q;Q.push( make_pair(1, 2) );for (int i=0; i<1500; i++){node_type node = Q.top(); Q.pop();switch(node.second){case 2: Q.push( make_pair(node.first*2, 2) );case 3: Q.push( make_pair(node.first*3, 3) );case 5: Q.push( make_pair(node.first*5, 5) );}result[i] = node.first;}int n;cin >> n;while (n>0){cout << result[n-1] << endl;cin >> n;}return 0;}在ACM 竞赛中，熟练掌握和运用STL 对快速编写实现代码会有极大的帮助。
优先队列的实现（⼤根堆，⼩根堆） 本博客不讲解具体的原理，仅仅给出⼀种优先队列较为⼀般化的，可重⽤性更⾼的⼀种实现⽅法。
我所希望的是能过带来⼀种与使⽤STL相同的使⽤体验，因为学习了STL源码之后深受STL代码的影响，对每个ADT都希望能过给出⼀种⾼效，可重⽤，更⼀般的实现⽅法，即使我的代码在STL的priority_queue⾯前仅仅只是三流⽔平，但也⾜够吧⼆叉堆这种数据结构演绎好了。
为了更⼀般化，我抛弃C语⾔的函数指针，改⽤STL相同的仿函数来实现更加⽅便的⾃定义优先级⽐较函数，于此同时我也兼容了已有类型的原有优先级⽐较仿函数。
⾸先给出maxPriorityQueue的ADT以及默认的优先级⽐较仿函数，默认为⼤根堆，⼩根堆重载优先级⽐较仿函数即可。
#ifndef MAXPRIORITYQUEUE_H#define MAXPRIORITYQUEUE_H#include <cstring>template<class T>struct Compare {bool operator () (const T& a, const T& b) {return a < b;}};template<>struct Compare<char*> {bool operator () (char* s1, char* s2) {return strcmp(s1, s2) < 0;}};template<class T>class maxPriorityQueue {public:~maxPriorityQueue() {}virtual bool empty() const = 0;virtual int size() const = 0;virtual T& top() = 0;virtual void pop() = 0;virtual void push(const T& theElement) = 0;};#endif 对于ADT的设计与实现，在C++中，相应ADT的纯虚类是必不可少的，它是ADT的逻辑定义，是设计数据结构的基础，上述代码给出了maxPriorityQueue的定义以及默认优先级⽐较仿函数，对于仿函数的使⽤⽅法，可在下⾯的maxHeap类中找到。
C++priority_queue的⽤法（含⾃定义排序⽅式）priority_queue本质是⼀个堆。
1. 头⽂件是#include<queue>2. 关于priority_queue中元素的⽐较 模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素⽐较⽅式。
Container必须是⽤数组实现的容器，⽐如vector,deque等等，但不能⽤ list。
STL⾥⾯默认⽤的是vector。
2.1 ⽐较⽅式默认⽤operator<，所以如果把后⾯2个参数缺省的话，优先队列就是⼤顶堆（降序），队头元素最⼤。
特别注意pair的⽐较函数。
以下代码返回⼀个降序输出：1 #include <iostream>2 #include <queue>3 using namespace std;4 int main(){5 priority_queue<int> q;6 for( int i= 0; i< 10; ++i ) q.push(i);7 while( !q.empty() ){8 cout<<q.top()<<endl;9 q.pop();10 }11 return 0;12 }以下代代码返回pair的⽐较结果，先按照pair的first元素降序，first元素相等时，再按照second元素降序：1 #include<iostream>2 #include<vector>3 #include<queue>4 using namespace std;5 int main(){6 priority_queue<pair<int,int> > coll;7 pair<int,int> a(3,4);8 pair<int,int> b(3,5);9 pair<int,int> c(4,3);10 coll.push(c);11 coll.push(b);12 coll.push(a);13 while(!coll.empty())14 {15 cout<<coll.top().first<<"\t"<<coll.top().second<<endl;16 coll.pop();17 }18 return 0;19 }2.2 如果要⽤到⼩顶堆，则⼀般要把模板的3个参数都带进去。
优先队列的重载运算符⼤家都知道优先队列是个好东西但它怎么如同sort⼀样⾃定义⽐较⽅式呢这⾥就献上⼏种重载运算符的⽅法First如果对象是intSTL默认是⼤根堆只需要priority<int> Q↓↓↓priority<int,vector<int>,greater<int> > Q它就能摇⾝变为⼩根堆so easy 过Secondly重点是结构体的重载隆重推出operator给出四种⽅法吧（都是等价的）struct node{int x;int y;friend bool operator<(const node a,const node b){return a.x>b.x;}};priority_queue<node> Q;struct node{int x;int y;bool operator<(const node &a) const{return x>a.x;}};priority_queue<node> Q;struct node{int x;int y;}point;bool operator<(const node &a,const node &b){return a.x>b.x;}priority_queue<node> Q;struct node{int x;int y;};struct cmp{bool operator()(node a,node b){return a.x>b.x;}};priority_queue<node,vector<node>,cmp> Q;暂时这样吧以后可能还会补充。
