STL基准容器类学习笔记之(Vector/Deque/List)
STL标准容器类简介
1.顺序性容器
vector相当与数组，从后面快速的插入与删除，直接访问任何元素
deque双队列，从前面或后面快速的插入与删除，直接访问任何元素
list双链表，从任何地方快速插入与删除
2.关联容器
set快速查找，不允许重复值
multiset快速查找，允许重复值
map一对一映射，基于关键字快速查找，不允许重复值
multimap一对多映射，基于关键字快速查找，允许重复值
3.容器适配器
stack后进先出
queue先进先出
priority_queue最高优先级元素总是第一个出列
4.所有标准库共有函数
默认构造函数 提供容器默认初始化的构造函数。
复制构造函数 将容器初始化为现有同类容器副本的构造函数
析构函数 不再需要容器时进行内存整理的析构函数
empty 容器中没有元素时返回true,否则返回false
max_size 返回容器中最大元素个数
size 返回容器中当前元素个数
operator= 将一个容器赋给另一个容器
operator< 如果第一个容器小于第二个容器，返回true，否则返回false，
operator<= 如果第一个容器小于或等于第二个容器，返回true，否则返回false
operator> 如果第一个容器大于第二个容器，返回true，否则返回false
operator>= 如果第一个容器大于或等于第二个容器，返回true，否则返回false
operator== 如果第一个容器等于第二个容器，返回true，否则返回false
operator!= 如果第一个容器不等于第二个容器，返回true，否则返回false
swap 交换两个容器的元素
其operator>,operator>=,operator<,operator<=,operator==,operator!=均不适用于priority_queue
5.顺序容器和关联容器共有函数
begin 该函数两个版本返回iterator或const_iterator，引用容器第一个元素
end 该函数两个版本返回iterator或const_iterator,引用容器最后一个元素后面一位
rbegin 该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器最后一个元素
rend 该函数两个版本返回reverse_iterator或const_reverse_iterator，引用容器第一个元素前面一位
erase 从容器中清除一个或几个元素
clear 清除容器中所有元素
下表显示了顺序容器和关联容器中常用的typedef，这些typedef常用于变量、参数和函数返回值的一般性声明。
value_type 容器中存放元素的类型
reference 容器中存放元素类型的引用
const_reference 容器中存放元素类型的常量引用，这种引用只能读取容器中的元素和进行const操作
pointer 容器中存放元素类型的指针
iterator 指向容器中存放元素类型的迭代器
const_iterator 指向容器中存放元素类型的常量迭代器，只能读取容器中的元素
reverse_iterator 指向容器中存放元素类型的逆向迭代器，这种迭代器在容器中逆向迭代
const_reverse_iterator 指向容器中存放元素类型的逆向迭代器，只能读取容器中的元素
difference_type 引用相同容器的两个迭代器相减结果的类型（list和关联容器没有定义operator-）
size_type 用于计算容器中项目数和检索顺序容器的类型（不能对list检索）
6.容器实现
6.1Vector是一个类模板，而不是一种数据类型，使用时需要：
#include<vector>
using std::vector;
定义vector对象：
vector<类型> 变量名;
初始化对象：
vector<T> v1: vector保存类型为T的对象，默认构造函数v1为空。
vector<T> v2(v1):v2是v1的一个副本。
vector<T> v3(n, i):v3包含n个值为i的元素。
vector<T> v4(n):v4含有值初始化的元素的n个副本，具体初始值由系统定义。
Vector对象的操作：
v.empty():如果v是空，返回true，否则返回false。
v.size():返回v中元素的个数。
v.push_back(t):在v的末尾增加一个值为t的元素。
v[n]:返回v中位置为n的元素，下标从0开始。
v1 = v2:将v2赋给v1;保持逻辑操作符的原有含义。
注：在C++中的for循环判断中，习惯用!=而不是><来编写循环的判断条件，只是为了安全的泛型编程。
vector对象元素的访问除了使用下标的方法以外，常用的方法是使用迭代器，迭代器是一种检查容器中元素并遍历元素的数据类型，标准库为每一种容器定义了一种迭代器类型。
容器的iterator类型分类：
1. vector<T>::iterator iter;
2. vector<T>::const_iterator iter;
容器的iterator的其他操作：
迭代器还可以用来进行比较运算和算术运算。
容器的iterator使用：
1. vector<T>::iterator iter;
概述：迭代器相当于指向vector容器的指针。
for(vector<int>::iterator iter = ivec.begin(); iter!=ivec.end();++iter)
{
*iter = 0;
}
迭代器最为常用的操作就是用已经存在的vector向量的begin和end对其进行赋值。
2.vector<T>::const_iterator iter;
它与上面的区别是使用它所定义的iter只能读取容器内的元素，不能改变它的值。要注意的是可以使用++iter，他与const vector不同，若定义const vector<T>::iterator iter,则iter不能进行自加运算。
Vector元素删除：
在使用Vector的时候，不可避免的要对其中的一些元素进行删除操作，删除的时候使用的操作时vector.erase(迭代器)的结构，具体的例子如下所示：
#include <vector>
#include <iostream>
using namespace std;
void main()
{
vector<int> a;
for ( int i = 0; i != 5; i++ )
{
a.push_back(i+1);
cout<<"the value is "<<a[i]<<endl;
}
cout<<a.size()<<endl;
cout<<endl;
for ( vector<int>::iterator iter = a.begin(); iter != a.end(); iter++ )
{
if ( *iter == 3 )
{
iter = a.erase(iter);
/*此处一定要注意：在使用erase后，iter编程了一个野指针，但是erase返回的值指向当前被删元素的前一个元素，因此要返回迭代器的指针，
这样循环过程会顺利进行*/
}
cout<<"the value is "<<*iter<<endl;
}
cout<<a.size();
}
6.2deque
C++ STL容器deque和vector很类似，也是采用动态数组来管理元素。deque和vector的不同之处：
1、两端都能够快速插入和删除元素。vector只能在尾端进行。
2、deque的元素存取和迭代器操作会稍微慢一些。因为deque的内部结构会多一个间接过程。
3、迭代器是特殊的智能指针，而不是一般指针。它需要在不同的区块之间跳转。
4、deque可以包含更多的元素，其max_size可能更大。因为不止使用一块内存。
5、不支持对容量和内存分配时机的控制。
注意：在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector。因为其内部结构显示不需要复制所有元素。
6、deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实作版本定义。
deque和vector相似的特性：
1、在中间部分插入和删除元素相对较慢，因为所有元素都要被移动。
2、迭代器属于随即存取迭代器。
最好采用deque的情形：
1、需要在两端插入和删除元素。
2、无需引用容器内的元素。
3、要求容器释放不再使用的元素。
使用deque之前需包含头文件：
#include <deque>
deque<Elem> c创建一个空的deque。
deque<Elem> c1(c2)复制一个deque。
Deque<Elem> c(n)创建一个deque，含有n个数据，数据均已缺省构造产生。
Deque<Elem> c(n, elem)创建一个含有n个elem拷贝的deque。
Deque<Elem> c(beg,end)创建一个以[beg;end)区间的deque。
Deque成员函数
c.assign(beg,end)将[beg; end)区间中的数据赋值给c。
c.assign(n,elem) 将n个elem的拷贝赋值给c。
c.at(idx) 传回索引idx所指的数据，假如idx越界，抛出out_of_range。
c.back() 传回最后一个数据，不检查这个数据是否存在。
c.begin() 传回迭代器重的可一个数据。
c.clear() 移除容器中所有数据。
c.~deque<Elem>() 销毁所有数据，释放内存。
c.empty() 判定容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos)删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() 传回地一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem) 在pos位置插入一个elem拷贝，传回新数据位置。
c.insert(pos,n,elem)在pos位置插入>n个elem数据。无返回值。
c.insert(pos,beg,end)在pos位置插入在[beg,end)区间的数据。无返回值。
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.pop_front() 删除头部数据。
c.push_back(elem) 在尾部加入一个数据。
c.push_front(elem) 在头部插入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.size() 返回容器中实际数据的个数。
C1.swap(c2) 将c1和c2元素互换。
Swap(c1,c2)同上操作。
使用deque示例：
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
deque<string> strDeq;
strDeq.assign(4,string("CHINA"));
strDeq.push_back("first_string");
strDeq.push_front("last_string");
copy(strDeq.begin(),strDeq.end(),
ostream_iterator<string>(cout," "));
cout << endl;
cout << endl;
for(int i = 0;i < strDeq.size();++i)
cout << "strDeq[" << i << "] : " << strDeq[i] << endl;
cout << endl;
for(int i = 0;i < strDeq.size();++i)
cout << "strDeq.at(" << i << ") : " << strDeq.at(i) << endl;
cout << endl;
strDeq.pop_front();
strDeq.pop_back();
copy(strDeq.begin(),strDeq.end(),
ostream_iterator<string>(cout," "));
cout << endl;
cout << endl;
for(int i = 1;i < strDeq.size();++i)
strDeq[i] = "pre" + strDeq[i];
copy(strDeq.begin(),strDeq.end(),
ostream_iterator<string>(cout," "));
cout << endl;
cout << endl;
strDeq.resize(4,"resized string");
copy(strDeq.begin(),strDeq.end(),
ostream_iterator<string>(cout," "));
cout << endl;
cout << endl;
}
6.3List容器以双向链表的方式管理它的元素，list容器的内部结构跟vector和deque都差别巨大，所以list容器在行为特征上跟vector和deque有明显差异：
1.list容器不提供随机元素访问。如果你想访问第五个元素，那么必须先遍历前四个元素才能到达第五个元素。所以使用list容器访问任意元素是低效的。
2.在list容器的任何位置插入和删除元素的效率都是一样的，都同样高效，这基于list容器的内部结构，不需要移动其他元素，只需要维护相应的指针即可。
3.插入和删除操作不会使其他元素的引用、指针和迭代器失效。
4.List容器对异常处理有着完美的支持，一个操作要么成功完成，要么对容器不产生任何影响。
跟vector和deque相比，在外部操作接口上list容器有下列区别：
1.list容器既没有[]操作符，也没有at()接口，因为list容器不支持随机元素访问。
2.list容器不提供对capacity和内存维护相关的接口，因为list容器中的每个元素分配自己的内存空间，当元素删除时，其对应的内存空间销毁。
3.list容器额外提供了一些移动元素的接口，这些接口比相应的通用算法要高效，因为它们基于list容器的内部结构而设计，所以在需要时应该优先使用它们。
list容器的操作
list容器跟vector、deque容器都属于序列容器(sequence containers), 所以大部分的操作接口还是类似的，像创建(create)、复制(copy)、销毁(destroy)、大小(size)、比较(compare)、赋值(assignment)、迭代器(iterator)等都基本类似。
Element Access
因为list容器不支持随机访问，所以元素访问接口只保留了front()和back()，分别用来访问第一个和最后一个元素。同样这两个接口不会检查容器是否为空，如果对一个空的list容器调用这两个接口，结果未可知。
Iterator Functions
跟vector和deque容器类似，list容器也提供了四个获取iterator的接口：begin(), end(), rbegin(), rend()。但是有一个细节上的不同就是vector和deque的迭代器是随机访问迭代器(random access iterator), 而list容器的迭代器是双向迭代器(bidirectional iterator)。它们的区别就是随机访问迭代器可以进行一些算术运算(+, -)，而双向迭代器只可以进行递增(++)、递减(--)操作。而且一些通用算法也只接受随机访问迭代器，使用时要注意。
Inserting and Removing Elements
对于插入和删除元素，list容器除了提供所有跟deque一样的接口外，还额外增补了两个删除元素的接口：remove(), remove_if()：
c.remove(val): 删除容器中所有值为val的元素。
c.remove_if(op): 删除容器中所有使op为true的元素。
这两个函数因为根据list容器的内部结构而设计，所以比对应的通用算法要高效，所以在同等的条件下应该优先使用这两个成员函数。
Splice Functions(拼接函数)
对比vector和deque容器，list容器在内部结构上采用了链表结构，这就使得在任意位置插入和删除元素都非常便利，所以list容器额外提供了一组拼接函数，你可以使用这些成员接口在一个容器内部或者两个容器之间方便地移动元素，当然这两个容器要具备相同的类型。
c.unique(): 删除容器中值相同位置相邻的额外元素，只保留一个元素。
c.unique(op): 删除容器中同时满足op条件位置相邻的额外元素，只保留一个元素。
c1.splice(pos, c2): 把容器c2中的所有元素移动到容器c1的迭代器位置pos之前。
c1.splice(pos, c2, c2pos): 把容器c2中的c2pos位置的元素移动到容器c1的pos位置之前。（c1和c2可以是同一个容器）
c1.splice(pos, c2, c2beg, c2end): 把容器c2中的[c2beg, c2end)范围内的所有元素移动到容器c1的pos位置之前。（c1和c2可以是同一个容器）
c.sort(): 以操作符<（升序）来排序容器中所有元素。
c.sort(op): 以运算子op来排序容器中所有元素。
c1.merge(c2): 假定容器c1和c2包含的元素都已经过排序(sorted with operation < ), 该接口把c2容器中的所有元素移动到c1中并且也按照排序规则排序。
c1.merge(c2, op): 假定容器c1和c2包含的元素都已经过排序(sorted with op), 该接口把c2容器中的所有元素移动到c1中并且也按照排序规则排序。
c.reverse(): 反序容器中的元素次序。
使用list容器的一个例子：
#include <iostream>
#include <list>
#include <algorithm>
#include "print.hpp"
using namespace std;
int main()
{
//create tow list set
list<int> col1, col2;
//insert some elements into two set
for (int i = 0; i < 6; ++i)
{
col1.push_back(i);
col2.push_front(i);
}
//print two set
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(col2, "col2: ");
//move all elements of col1 in front of the first element with value 3 in col2
col2.splice(find(col2.begin(), col2.end(), 3), col1);
//print two set
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(col2, "col2: ");
//move the first element of col2 to the end position
col2.splice(col2.end(), col2, col2.begin());
//print two set
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(col2, "col2: ");
//assign col2 to col1 and unique col2
col2.sort();
col1 = col2;
col2.unique();
//print two set
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(col2, "col2: ");
//merge the col2 to col1
col1.merge(col2);
//print two set
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(col2, "col2: ");
}
执行结果如下：
col1: 0 1 2 3 4 5 col2: 5 4 3 2 1 0 col1: col2: 5 4 0 1 2 3 4 5 3 2 1 0 col1: col2: 4 0 1 2 3 4 5 3 2 1 0 5 col1: 0 0 1 1 2 2 3 3 4 4 5 5 col2: 0 1 2 3 4 5 col1: 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 col2: