C++中STL容器的分类和基本功能（一）： 向量(vector) 双端队列(deque) 列表(list)

容器的分类与基本功能
七种基本容器
向量(vector)
双端队列(deque)
列表(list)
集合(set)
多重集合(multiset)
映射(map)
多重映射(multimap)

按容器中元素的组织方式
顺序容器
关联容器

按与容器相关的迭代器类型
可逆容器
随机访问容器


容器的通用功能
vector<int> s1,s2; //使用默认构造函数构造空容器
s1 == s2; //支持关系运算符： == 、!=、<、<=、>、>=
s1.begin() s1.end(); //获得容器首、尾迭代器
s1.clear(); //将容器清空
s1.empty(); //判断容器是否为空
s1.size(); //得到容器元素个数
s1.swap(s2); //将s1和s2两容器内容交换


随机访问容器
s[n] //获得容器s的第n个元素


相关迭代器类型（s 表示容器类型）
s::iterator //指向容器元素的迭代器类型
s::const_iterator //常迭代器类型 一经初始化便无法修改


可逆（双向）容器的功能
s::reverse_iterator //双向迭代器类型
s::const_reverse_iterator //逆向常迭代器类型
rbegin() //指向容器尾的逆向迭代器
rend() //指向容器首的逆向迭代器
例：
copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
copy(s.rbegin(), s.rend(), ostream_iterator<int>(cout, " "));


顺序容器通用功能
构造：
S s(n,t);  //构造一个由n个t元素构成的容器实例s
S s(n);  //构造一个有n个元素的容器实例s，每个元素都是T()
S s(q1,q2);  //使用将[q1,q2)区间内的数据作为s的元素构造s

赋值：
s.assing(n,t); //赋值后的容器由n个t元素构成  
s.assing(n);  //赋值后的容器由n个元素，每个元素都是T()
s.assing(q1,q2);赋值后的容器为[q1,q2)区间内的数据

插入： 
s.insert(p1,t);  //在容器s中p1所指向的位置插入一个新的元素t，该函数会返回一个迭代器指向新插入的元素
s.insert(p1,n,t);  //在容器s中p1所指向的位置插入n个新的元素t，没有返回值
s.insert(p1,q1,q2);  //将[q1,q2)区间内的元素顺序插入到s容器中p1位置处。
s.push_front(t); s.push_front(); //在容器前插入一个元素，对list 和 deque使用
s.push_back(t); s.push_back();  //在容器后插入一个元素，对list 和 deque使用

删除：
s.erase(p1);  //删除s1容器中p1所指向的元素，返回被删除的下一个元素的迭代器
s.erase(p1,p2);  //删除s1容器中[p1,p2)区间内元素，返回最后一个被删除元素的下一个元素的迭代器
s.erase();
s.clear();
s.pop_front();  //取出前面第一个的元素，对list和deque 使用 
s.pop_back();  //取出最后面的元素，对list和deque 使用 

首尾元素直接访问：
s.front(); s.back();  //返回引用

改变大小：
s.resize(n);  //将容器的大小变为n，如果原有的元素个数大于n，则容器末尾多余的元素会被删除；如果原油的元素个数小于n，则在容器的末尾会用T()填充

/************************************************************************************************************/
向量vector


特点：
一个可以扩展的动态数组
随机访问容器
在头部插入速度较慢，在尾部插入速度较快，容器内存连续，在头部插入要修改n个内存。

向量的容量：
容量(capacity)：实际分配空间的大小
s.capacity();  //发挥当前容量
s.reserve(n);  //若容量小于n，则对s进行扩展，使其容量至少为n

#include <stdlib.h> #include <iostream> #include <algorithm> #include <iterator> #include <vector> using namespace std;int main() {const int N = 5;vector<int> s;s.reserve(3);cout << s.capacity() << endl; cout << s.size() <<endl;for(int i = 0; i < N; i++){s.push_back(i);}s.insert(s.begin() + 3, 9);copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));cout << endl;s.pop_back();copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));cout << endl;system("pause");return 0; }

输出： 3
0
0 1 2 9 3 4
0 1 2 9 3

/*********************************************************************************************************/
双端队列(deque)

特点：
在两端插入或删除元素较快
在中间插入或删除元素较慢
随机访问较快，但是比向量容器慢

存储结构：
数组
分段数组

再例：奇偶排序
先按照从大到小顺序输出奇数，再按照从小到大顺序输出偶数

#include <stdlib> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <iterator> using namespace std;int main() {istream_iterator<int> i1(cin), i2;vector<int> s1(i1, i2);sort(s1.begin(), s1.end());copy(s1.begin(), s1.end(), ostream_iterator<int>(cout, " "));cout << endl;deque<int> s2;for(vector<int>::iterator iter = s1.begin(); iter != s1.end(); iter++){if(*iter % 2 == 0){s2.push_back(*iter);}else{s2.push_front(*iter);}}copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " "));cout << endl;system("pause");return 0; }

输出： 1 4 3 2 7 6 5 
^Z                               //此处的为 CTRL+Z表示结束符
1 2 3 4 5 6 7
7 5 3 1 2 4 6
/************************************************************************************************************/

列表(list)


贴点：
再任意位置插入和删除元素都很快
不支持随机访问

接合(splice)操作：
s1.splice(p ,s2, q1, q2);  //将s2中[q1,q2)移动到s1中p所指向元素之前

#include <stdlib> #include <iostream> #include <algorithm> #include <vector> #include <list> #include <iterator> using namespace std;int main() {string names1[] = {"A", "B", "C", "D"};string names2[] = {"E", "F", "G", "H"};list<string> s1(names1, names1 + 4);list<string> s3(names2, names2 + 4);s2.splice(s2.end(), s1, s1.begin());//s1:B C D s2:E F G H Acopy(s1.begin(), s1.end(), ostream_iterator<string>(cout, " "));cout << endl;copy(s2.begin(), s2.end(), ostream_iterator<string>(cout, " "));cout << endl;list<string>::iterator iter1 = s1.begin();advance(iter1, 2);list<string>::iterator iter2 = s2.begin();++iter2;list<string>::iterator iter3 = s3.begin();s1.splice(iter1, s2, iter2, iter3); //s1:B C Dcopy(s1.begin(), s1.end(), ostream_iterator<string>(cout, " "));cout << endl;copy(s2.begin(), s2.end(), ostream_iterator<string>(cout, " "));cout << endl;system("pause");return 0; }

输出： B C D
E F G H A
B C D
E F G H A

/************************************************************************************************************/

三种顺序容器的比较
如果需要执行大量的随机访问操作，而且当扩展容器时只需要向容器尾部加入新的元素，就应当选择向量容器(vector)
如果需要少量的随机访问操作，需要在容器两端插入或删除元素，则应当选择双端队列容器(deque)
如果不需要对容器进行随机访问，但是需要在中间位置插入或者删除元素，就应当选择列表容器(list)