顺序容器
c++中顺序容器包含三种方法：
- verctor (可以简单的看作是可以动态调控大小的数组)
- list （可以简单的看作是双向链表）
- deque（可以简单的看作是双向队列）
1、三种容器的异同
vector：表示一段连续的内存区域，每个元素被顺序存储在这段内存中。
对vector其的访问效率很高，但是插入和删除操作的效率很低,因为它要像数组那样对其他的数据进行拷贝、移位。它的动态扩容实现的原理是当容量不够时把整体全部数据拷贝到另一个全新的分配容量充足区域。
list：表示非连续的内存区域 并通过一对指向首尾元素的指针双向链接起来 从而允许向前和向后两个方向进行遍历
在 list 的任意位置插入和删除元素的效率都很高，指针的指向关系必须被重新赋值， 但是不需要用拷贝元素来实现移动。但是另一方面 它对随机访问的支持并不好访问一个元素需要遍历中间的元素 另外 每个元素还有两个指针的额外空间开销。
deque：也表示一段连续的内存区域 但是 与 vector 不同的是 它支持高效地在其首部插入和删除元素。
它通过两级数组结构来实现，一级表示实际的容器 ，第二级指向容器的首和尾。
2、三种容器选择的准则：
- 如果我们需要随机访问一个容器 则 vector 要比 list 好得多
- 如果我们已知要存储元素的个数 则 vector 又是一个比 list 好的选择
- 如果我们需要的不只是在容器两端插入和删除元素 则 list 显然要比 vector 好
- 除非我们需要在容器首部插入和删除元素 否则 vector 要比 deque 好
3、 定义一个顺序容器
为了定义一个容器对象 我们必须先包含相关联的头文件，应该是下列头文件之一：
#include <vector>
#include <list>
#include <deque>
#include <map> //映射容器（关联容器）
#include <set> //集合容器（关联容器）
定义一个容器
容器对象的定义以容器类型的名字开始 后面是所包含的元素的实际类型：
vector< string > svec;
list< int > ilist;
上述定义了两个空的容器，也可以为容器指定显示的长度。
const int list_size = 64;
list< int > ilist( list_size );
初始化容器
- 那么下面需要对其进行赋值初始化，可以调用push_back()方法向容器中插入元素，它将元素插入在容器的尾部(list 和 deque 容器也支持 push_front() 它把新元素插入在链表的前端)：
string text_word;
while ( cin >> text_word ) //linux 中跳出次循环的条件是输入错误或者按键 Ctrl + D
svec.push_back( text_word );
- 我们还可以指定一个容器长度，并指定一个值用它来初始化每个元素。指定长度之后我们可以利用resize()方法对其重新规划容量，而且可以为新规划的元素初始化为特定的值；
list< int > ilist( list_size, - 1 ); //第一个参数是容器的显式长度，第二个是初始化的每个元素的值
vector< string > svec( 24, "pooh" ); //第一个参数是容器的显式长度，第二个是初始化的每个元素的值
svec.resize( 2 * svec.size(), "piglet" ); //将容量重新规划成原来的两倍，并将新规划的部分用 “piglet” 进行初始化
- 我们也可以用一个现有的容器对象初始化一个新的容器对象
vector< string > svec2( svec );
list< int > ilist2( ilist );
容器之间的关系操作符（== ,>,>=,<,<=, !=）
- 如果所有元素相等而且两个容器含有相同数目的元素 则两个容器相等
- 第一个不相等元素的比较决定了两个容器的小于或大于关系
- 如果所有元素相同但是长度不等，短的容器 < 长的容器
注意：我们能够定义的容器的类型有三个限制（实际上，它们只适用于用户定义的类类型）
- 元素类型必须支持等于操作符;
- 元素类型必须支持小于操作符 (前面讨论的所有关系操作符都用这两个操作符来实现 );
- 元素类型必须支持一个缺省值( 对于类类型,即指缺省构造函数);
4、顺序容器的操作
插入
方法主要有两种
- push_back(value)
从容器的尾部插入一个元素，value的类型需要与容器初始化的类型一致
- insert()
// 等价的尾部插入元素
slist.push_back( value );
slist.insert( slist.end(), value );
//在某个位置插入元素，把spouse插入到Danny前面
string son( "Danny" );
list<string>::iterator iter;
iter = find( slist.begin(), slist.end(), son );
slist.insert( iter, "spouse" );
//在某个位置插入指定数量的元素，在容器首部插入10个Anna
vector<string> svec;
string anna( "Anna" );
svec.insert( svec.begin(), 10, anna );
向容器某位置插入一段范围内的元素
string sarray[4] = { "quasi", "simba", "frollo", "scar" };
svec.insert(svec.begin(),sarray,sarray+4); //sarray+4是指从string数组第0个元素开始至第四个元素之间的元素，不包括下界。
删除
方法也是两种
pop_back()从尾部删除元素，删除容器里面的末尾元素，它不返回元素 只是简单地删除它。
erase() 两种应用形式:1、删除特定位置的单个元素 2、删除由一对
iterator 标记的一段范围内的元素
string searchValue( "Quasimodo" );
list<string>::iterator iter = find( slist.begin(), slist.end(), searchValue );
if ( iter != slist.end() )
slist.erase( iter );
slist.erase( slist.begin(), iter );
slist.erase( slist.begin(), slist.end() );
赋值和对换
赋值操作符使用针对容器元素类型的赋值操作符 把右边容器对象中的元素依次拷贝到左边的容器对象中。对换的操作有swap()方法，这是将两个容器的内容进行互换。
// slist1 含有 10 个元素
// slist2 含有 24 个元素
// 赋值之后都含有 24 个元素,反之则都含有10个元素
slist1 = slist2;
//对换过后slist1含有24个元素，ilist2含有10个元素。
slist1.swap( slist2 );
- 赋值还有一个assign()方法相关的一些说明参照官方手册https://zh.cppreference.com/w/cpp/container/vector
泛型算法
从概念上讲，我们的思想是把所有容器类型的公共操作抽取出来，形成一个通用算法集合，它能够被应用到全部容器类型以及内置数组类型上 。这组通用算法被称作泛型算法。下面主要将find()操作
#include <list>
#include <vector>
// the associated header file
#include <algorithm>
int ia[ 6 ] = { 0, 1, 2, 3, 4, 5 };
vector<string> svec;
list<double> dlist;
vector<string>::iterator viter;
list<double>::iterator liter;
int *pia;
// 如果找到, find()返回指向该元素的 iterator
// 对于数组, 返回指针
pia = find( &ia[0], &ia[6], some_int_value );
liter = find( dlist.begin(), dlist.end(), some_double_value );
viter = find( svec.begin(), svec.end(), some_string_value );
网友评论