C++中的顺序容器（一）

顺序容器概述

元素在顺序容器中顺序与其加入容器时的位置相对应。

选择合适的顺序容器：

• 除非有很好的理由选择其他容器，否则使用vector；
• 程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list；
• 要求随机访问，vector、deque；
• 要求在容器的中间插入或删除，list或forward_list；
• 只在头尾插入或删除，deque；
• 输入时要求在中间插入元素，随后要求随机访问：如果在中间插入只是为了排序的话，可以在vector尾部添加元素之后在使用sort排序；如果必须在中间插入，则可以先使用list接收数据，在将接收的数据拷贝到vector中。

如果不确定应该使用哪种容器，那么可以在程序中只是用vector或list公共的操作：使用迭代器，不使用下标操作，避免随机访问。

虽然我们可以在容器中保存几乎任何类型，但某些容器操作对元素类型有自己的特殊要求。例如顺序容器的一个版本的构造函数接收容器大小参数，并使用元素类型的默认构造函数。我们可以定义保存这种类型对象的容器，但在构造这种容器时不能只传递元素数量：

//假定noDefault是一个没有构造函数的类型
vector<noDefault> v1(10, init); //ok
vector<noDefault> v1(10); //err，必须提供一个元素初始化器

所有容器类型都支持的操作

迭代器

一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者尾元素之后的位置。可以使用begin得到第一个元素位置，end得到尾元素之后的位置。

//显式指定类型
list<string>::iterator it = a.begin();
list<string>::const_iterator it = a.begin();
//auto
auto it = a.begin(); //当a是const时，为const_iterator，否则为iterator
auto it = a.cbegin(); //const_iterator

当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型。但与cbegin或cend结合时，获得的是const_iterator。

容器定义与初始化

每个容器都定义了一个默认构造函数。除array之外，其他容器的默认构造函数都会创造一个指定类型的空容器。

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

将一个容器初始化为另一个容器的拷贝的方法有两种：

• 可以直接拷贝整个容器，要求容器类型和元素类型必须匹配；
• 拷贝由一个迭代器对指定的元素范围（array除外），不在要求要求容器类型和元素匹配，而要求拷贝的元素能够转化为目标元素即可。

list<string> authors = {"Mi", "Sh", "Au"};
vector<const char*> articles = {"a", "an", "the"};

list<string> li(authors); //ok
deque<string> de(authors); //err
vector<string> words(articles); //err
//const char* 可以转换为string
forward_list<string> words(articles.begin(), articles.end()); //ok

标准库array具有固定大小

与内置数组一样，标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，还要指定容器大小：

array<int, 42> ia1; //42个默认初始化的int
array<int, 42> ia1 = {0}; //一个0，41个默认初始化的int
array<int, 42>::size_type i;

值得注意的是，内置数组不能进行拷贝或者赋值，但是array可以：

int digs[4] = {0, 1, 2, 3};
int cpy[4] = digs; //err，内置数组不支持拷贝或赋值
array<int, 4> digits = {0, 1, 2, 3}; //初始化后，不可使用{}赋值
array<int, 4> copy = digits; //ok，要求类型（容器类型以及大小）一致

赋值和swap

赋值运算符要求左右两边的运算对象具有相同的类型，它将右边运算对象中的所有元素拷贝到左边运算对象中。assign也可以实现类似的功能，但不在要求要求容器类型和元素匹配，而要求拷贝的元素能够转化为目标元素即可。

swap可以交换两个相同类型容器的内容。除了array之外，swap不会对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间完成，swap只是交换了两个容器之间的内部结构。这意味着指向容器（string除外）的迭代器、引用或指针在swap之后不会失效。

例如，iter在swap之前指向svec[3]，在swap之后就会指向svec2[3]:

vector<string> svec1(10);
vector<string> svec2(10);
swap(svec1, svec2);

与其他容器不同，swap会真正交换array中元素，虽然swap不会使得array中的指针、引用、迭代器失效，但是在swap之后解引用得到的结果是另外一个array相应位置的值。

关系运算符

每个容器都支持相等运算符（==、!=），除了无序关联容器都支持关系运算符（>、>=、<、<=）。关系运算符左右两边运算对象必须是相同类型的容器，且必须保存相同类型的元素。并且只有当其元素也定义了相应的比较运算时，才可进行比较。

顺序容器的特有操作

向顺序容器添加元素

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器的大小。

当我们用一个对象来初始化容器时，或将一个对象插入（push、insert）到容器时，实际上放入到容器中的是对象值得拷贝，而不是对象本身。值得注意得是，使用emplace时，则是将参数传递给元素得构造函数，并在容器内直接构造元素。

//使用三个参数构造函数
c.emplace_back("789", 25, 15.99);
//err
c.push_back("789", 25, 15.99);
//ok，创建一个临时对象传递给push
c.push_back(Sales_data("789", 25, 15.99));

访问元素

在容器中访问元素的成员函数返回的都是引用：

if(c.empty())
{
	c.front() = 42;
	auto &v = c.back();
	v = 1024; //改变容器中的元素
	auto v2 c.back;
	v2 = 0; //无法改变容器中元素
}

删除元素

特殊的forward_list操作

因为forward_list是单向列表，插入删除等操作会影响目标节点之前的节点，因此以目标节点的前节点作为参数。

改变容器的大小

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

向容器中添加元素或从容器中删除元素的操作可能会使指向容器中元素的指针、引用、迭代器失效。

添加、删除元素：

• vector、string，且存储空间被重新分配，则指向容器的迭代器、指针和引用全部失效。如果为重新分配存储空间，则只失效指向插入后的元素的；
• deque，插入删除到首尾之外的位置会导致指向其中元素的迭代器、指针和引用失效。
• list、forward_list，不会失效；

使用失效的迭代器、指针或引用是严重的运行时错误。