C++学习之顺序容器（一）

一个容器就是一些特定类型对象的集合。顺序容器（sequential container）为我们提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置向对应。

顺序容器类型概述

容器名称	容器特性	访问特性	修改特性
vector	可变大小数组	随机	尾部插入/删除速度快
deque	双端队列	随机	头尾位置插入/删除速度快
list	双向链表	双向顺序	任意位置插入/删除均很快
forward_list	单项链表	单向顺序	任意位置插入/删除均很快
array	固定大小数组	随机	不可添加/删除元素
string	与vector相似，但只保存字符	随机	尾部插入/删除速度快

除了固定大小的array外，其他容器都提供高效、灵活的内存管理。在一些情况下，存储策略会影响特定容器是否支持特定操作：

1.string和vector将元素保存在连续的内存空间中，因此由元素下班来计算地址十分快速；但在容器中间位置添加/删除元素非常耗时，需要一定插入/删除位置之后的所有元素（用以保证连续存储）；另外，添加一个元素有时可能需要分配额外的存储空间，此时每个元素必须移动到新的存储空间。

2.list和forward_list的设计目的即是令容器任何位置的添加/删除操作都很快速，但是作为代价，为了访问一个元素，必须遍历整个容器，另外与vector、deque和array相比，这两个容器的额外内存开销也很大。

3.deque在中间位置添加/删除元素代价（可能）很高，但在两端添加/删除很快

有关顺序容器的详细结构还需要多看看《STL源码解析》相关书籍...

 

容器库概览

迭代器

begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器

auto it1 = a.begin();
// list<string>::iterator
auto it2 = a.cbegin();
/ /list<string>::const_iterator
// 显式指定类型
list<string>::iterator it3 = a.begin();
list<string>::const_iterator it4 = a.begin();
// 反向迭代器不在本次讨论范围内

 

容器定义和初始化

　　将一个容器初始化为另一个容器的拷贝

i.直接拷贝整个容器：要求两个容器的类型极其元素类型必须匹配

ii.拷贝一个由一个迭代器对特定元素范围（array除外）：不要求容器类型相同，元素类型可转换目标元素即可

// 列表初始化
list<string> authors = {"Alan", "Bob", "David"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors );
// 正确： 类型匹配
deque<string> authList(authors );
// 错误： 容器类型不匹配
vector<string> words(articles);
// 错误： 容器类型不匹配
// 正确： 可以将const char* 元素转换为string
forward_list<string> words(articles.begin(), articles.end());

 

与顺序容器大小相关的构造函数

顺序容器（除array）提供一个构造函数，接受一个容器大小和一个（可选）元素初始值

vector<int> ivec(10, -1);
// 10个int 元素，每个都初始化为-1
listing<string> svec(10, "hi");
// 10个string；每个都初始化为"hi"
forward_list<int> ivec(10);
// 10个元素，每个都初始化为0
deque<string> svec(10);
// 10个元素，每个都是空string

 

标准库array具有固定大小

定义array，需指定元素类型和容器大小

array<int>::size_type j;
// 错误：array<int>不是一个类型
array<int, 42> ia1;
// 默认初始化int

 

note：虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但array并无此限制，但被赋值的array要与原array具有相同的元素类型和大小

赋值和swap

赋值运算符赋值

i.要求左右运算对象具有相同的类型

ii.如果两个容器原来大小不同，赋值运算后两者的大小和右边容器的原大小相同。

assign赋值

i.该操作不适用于关联容器和array

ii.允许从一个不同但相容的类型赋值，或者从容器的一个子序列赋值

iii.由于assign操作首先删除容器中原来存储的所有元素，因此传递给assign函数的迭代器不能指向调用该函数的容器内的元素

使用swap

i.除array外，交换两个容器内容的操作保证会很快，因为元素本身并未交换，swap只是交换了两个容器的内部结构。

ii.除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效；因为交换的数据结构，各元素存储的值并未发生改变，元素所属容器发生了改变，因此容器中所存储的元素地址也发生了改变。

例如：在gcc中，vector的swap是交换三个指针：_M_start，_M_finish，_M_end_of_storage，而引用是没有解绑的。

iii.swap两个array会真正交换它们的元素（相应的，交换时间和array的大小成正相关）：交换后，两个array交换了元素的值，但容器中所存地址并未发生交换；另外，swap操作后，指针、引用和迭代器所绑定的元素保持不变，但元素内的值发生了改变

iiii.swap一个string导致指针、引用和迭代器的失效，找到了一个解释：https://www.zhihu.com/question/57561910

顺序容器操作

顺序容器操作	操作功能	支持容器	返回值
push_back	追加元素在容器尾部	list,vector,deque,string	void
push_front	插入元素到容器头部	list,forward_list,deque	void
insert	在容器特定位置之前添加元素或插入范围内元素	vector,deque,list,string	返回指向第一个新加入元素的迭代器
emplace_front	构造元素，插入元素到容器头部	list,forward_list,deque	void
emplace	构造元素，在容器特定位置之前添加元素或插入范围内元素	vector,deque,list,string	返回指向第一个新加入元素的迭代器
emplace_back	构造元素，追加元素在容器尾部	list,vector,deque,string	void
pop_front	删除首元素	list,forward_list,deque	void
pop_back	删除尾元素	list,vector,deque,string	void
erase	从容器特定位置删除元素或删除范围内元素	vector,deque,list,string	返回指向删除的最后一个元素之后位置的迭代器

 

list<string> slist;
// 等价于调用 slit.push_back("hi");
slist.insert(slist.begin(),"hi");
vector<string> svec = {"a", "b", "c"};
//一对迭代器，不能指向被插入容器
slist.insert(slist.begin(), svec.end()-2, svec.end());
//删除多个元素
slist.clear();
// 删除容器中所有元素
slist.erase(slist.begin(), slist.end());
// 等价调用

 

特殊的forward_list操作

在forward_list中插入或删除元素的操作
lst.before_begin()	返回指向链表首元素之前并不存在的元素的迭代器，此迭代器不能解引用。cbefore_begin()返回一个const_iterator
lst.cbefore_begin()
lst.insert_after(p,t)	在迭代器p之后的位置插入元素。t是一个对象，n是数量，b和e是表示范围的一对迭代器（b和e不能指向lst内），il是一个花括号列表。 返回一个指向最后一个插入l元素的迭代器。 如果范围为空，则返回p，若p为尾后迭代器，则函数行为未定义。
lst.insert_after(p,n,t)
lst.insert_after(p,b,e)
lst.insert_after(p,il)
emplace_after(p,args)	使用args在p指定的位置之后创建一个元素，返回一个指向这个新元素的迭代器。若p为尾后迭代器，则函数的行为未定义
lst.erase_after(p)	删除p指向的位置之后的元素，或删除从b之后直到（但不包含）e之间的元素。 返回一个指向被删除元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代器，如果p指向lst的尾元素或者是一个尾后迭代器，则函数的行为未定义
lst.erase_after(p，e)

 

容器操作可能使迭代器失效

向容器中添加元素后：

1. 如果容器时vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效，如果存储空间未重新分配，则指向插入元素之前的迭代器、指针和引用都有效，指向插入元素之后元素的迭代器、指针和引用都会失效。

2. 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、引用和指针失效，如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。

3. 对于list和forward_list，指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用都有效。

 

容器在删除元素后：

1.  对于list和forward_list，指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用都有效

2. 对于deque，如果在首尾之外的任何位置删除元素，那么指向删除元素外其他元素的迭代器、引用和指针也会失效。如果是删除deque的尾元素，则尾后迭代器失效，但其他迭代器、引用和指针不受影响; 如果删除首元素，这些也不会受影响。

3. 对于vector和string，指向被删除元素之前元素的迭代器、引用和指针扔有效

 

当我们删除元素时，尾后迭代器总是会失效。

因此，必须保证每次改变容器的操作之后都正确的重新定位迭代器，还有不要保存end返回的尾后迭代器。

 

 

参考：

http://blog.csdn.net/jy_95/article/details/47679185

http://blog.csdn.net/imkelt/article/details/52213735