【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.顺序容器操作
顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。在【C++基础】第五十一课：[顺序容器]容器库概览一文中介绍了所有容器都支持的操作（表9.2）。本文将介绍顺序容器所特有的操作。
2.向顺序容器添加元素
除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。表9.5列出了向顺序容器（非array）添加元素的操作。
当我们使用这些操作时，必须记得不同容器使用不同的策略来分配元素空间，而这些策略直接影响性能。在一个vector或string的尾部之外的任何位置，或是一个deque的首尾之外的任何位置添加元素，都需要移动元素。而且，向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。
2.1.使用push_back
除array和forward_list之外，每个顺序容器（包括string类型）都支持push_back。比如：
1
2
3
4
//从标准输入读取数据，将每个单词放在容器末尾
string word;
while (cin >> word)
container.push_back(word);
对push_back的调用在container尾部创建一个新的元素，将container的size增大了1。该元素的值为word的一个拷贝。container的类型可以是list、vector或deque。
由于string是一个字符容器，我们也可以用push_back在string末尾添加字符：
1
2
3
4
5
void pluralize(size_t cnt, string &word)
{
if(cnt > 1)
word.push_back('s'); //等价于word+='s'
}
当把string对象和字符字面值及字符串字面值混在一条语句中使用时，必须确保每个加法运算符（+）的两侧的运算对象至少有一个是string。详见：字面值和string对象相加。
关键概念：容器元素是拷贝
当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。
2.2.使用push_front
除了push_back，list、forward_list和deque容器还支持名为push_front的类似操作。此操作将元素插入到容器头部：
1
2
3
4
list<int> ilist;
//将元素添加到ilist开头
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_front(ix);
此循环将元素0、1、2、3添加到ilist头部。每个元素都插入到list的新的开始位置（new beginning）。即，当我们插入1时，它会被放置在0之前，2被放置在1之前，依此类推。因此，在循环中以这种方式将元素添加到容器中，最终会形成逆序。在循环执行完毕后，ilist保存序列3、2、1、0。
注意，deque像vector一样提供了随机访问元素的能力，但它提供了vector所不支持的push_front。deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间。与vector一样，在deque首尾之外的位置插入元素会很耗时。
2.3.在容器中的特定位置添加元素
push_back和push_front操作提供了一种方便地在顺序容器尾部或头部插入单个元素的方法。insert成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。forward_list提供了特殊版本的insert成员，我们将在后文介绍。
每个insert函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置。insert函数将元素插入到迭代器所指定的位置之前。例如，下面的语句：
1
slist.insert(iter, "Hello!"); //将"Hello!"添加到iter之前的位置
虽然某些容器不支持push_front操作，但它们对于insert操作并无类似的限制（插入开始位置）。因此我们可以将元素插入到容器的开始位置，而不必担心容器是否支持push_front：
1
2
3
4
5
6
7
8
9
vector<string> svec;
list<string> slist;
//等价于调用slist.push_front("Hello!")
slist.insert(slist.begin(), "Hello!");
//vector不支持push_front，但我们可以插入到begin()之前
//警告：插入到vector末尾之外的任何位置都可能很慢
svec.insert(svec.begin(), "Hello!");
将元素插入到vector、deque和string中的任何位置都是合法的。然而，这样做可能很耗时。
2.4.插入范围内元素
除了第一个迭代器参数之外，insert函数还可以接受更多的参数，这与容器构造函数类似。其中一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：
1
svec.insert(svec.end(), 10, "Anna");
这行代码将10个元素插入到svec的末尾，并将所有元素都初始化为string “Anna”。
接受一对迭代器或一个初始化列表的insert版本将给定范围中的元素插入到指定位置之前：
1
2
3
4
5
6
vector<string> v = {"quasi", "simba", "frollo", "scar"};
//将v的最后两个元素添加到slist的开始位置
slist.insert(slist.begin(), v.end()-2, v.end());
slist.insert(slist.end(), {"these", "words", "will", "go", "at", "the", "end"});
//运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器
slist.insert(slist.begin(), slist.begin(), slist.end());
在C++11新标准下，接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。（在旧版本的标准库中，这些操作返回void。）如果范围为空，不插入任何元素，insert操作会将第一个参数返回。
可以选择不使用insert的返回值：
2.5.使用insert的返回值
通过使用insert的返回值，可以在容器中一个特定位置反复插入元素：
1
2
3
4
list<string> lst;
auto iter = lst.begin();
while (cin >> word)
iter = lst.insert(iter, word); //等价于调用push_front
2.6.使用emplace操作
C++新标准引入了三个新成员—emplace_front、emplace和emplace_back，这些操作构造而不是拷贝元素。这些操作分别对应push_front、insert和push_back，允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。
当调用push或insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。例如，假定c保存Sales_data元素：
1
2
3
4
5
6
7
//在c的末尾构造一个Sales_data对象
//使用三个参数的Sales_data构造函数
c.emplace_back("978-0590353403", 25, 15.99);
//错误：没有接受三个参数的push_back版本
c.push_back("978-0590353403", 25, 15.99);
//正确：创建一个临时的Sales_data对象传递给push_back
c.push_back(Sales_data("978-0590353403", 25, 15.99));
在调用emplace_back时，会在容器管理的内存空间中直接创建对象。而调用push_back则会创建一个局部临时对象，并将其压入容器中。
emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配：
1
2
3
4
5
//iter指向c中一个元素，其中保存了Sales_data元素
c.emplace_back(); //使用Sales_data的默认构造函数
c.emplace(iter, "999-999999999"); //使用Sales_data(string)
//使用Sales_data的接受一个ISBN、一个count和一个price的构造函数
c.emplace_front("978-0590353403", 25, 15.99);
emplace函数在容器中直接构造元素。传递给emplace函数的参数必须与元素类型的构造函数相匹配。
3.访问元素
表9.6列出了我们可以用来在顺序容器中访问元素的操作。如果容器中没有元素，访问操作的结果是未定义的。
包括array在内的每个顺序容器都有一个front成员函数，而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用：
1
2
3
4
5
6
7
8
9
10
//在解引用一个迭代器或调用front或back之前检查是否有元素
if (!c.empty())
{
//val和val2是c中第一个元素值的拷贝
auto val = *c.begin(), val2 = c.front();
//val3和val4是c中最后一个元素值的拷贝
auto last = c.end();
auto val3 = *(--last); //不能递减forward_list迭代器
auto val4 = c.back(); //forward_list不支持
}
3.1.访问成员函数返回的是引用
在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。如果容器是一个const对象，则返回值是const的引用。如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值：
1
2
3
4
5
6
7
8
if (!c.empty())
{
c.front() = 42; //将42赋予c中的第一个元素
auto &v = c.back(); //获得指向最后一个元素的引用
v = 1024; //改变c中的元素
auto v2 = c.back(); //v2不是一个引用，它是c.back()的一个拷贝
v2 = 0; //未改变c中的元素
}
与往常一样，如果我们使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型。
3.2.下标操作和安全的随机访问
提供快速随机访问的容器（string、vector、deque和array）也都提供下标运算符。就像我们已经看到的那样，下标运算符接受一个下标参数，返回容器中该位置的元素的引用。给定下标必须“在范围内”（即，大于等于0，且小于容器的大小）。保证下标有效是程序员的责任，下标运算符并不检查下标是否在合法范围内。使用越界的下标是一种严重的程序设计错误，而且编译器并不检查这种错误。
如果我们希望确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，但如果下标越界，at会抛出一个out_of_range异常：
1
2
3
vector<string> svec; //空vector
cout << svec[0]; //运行时错误：svec中没有元素！
cout << svec.at(0); //抛出一个out_of_range异常
4.删除元素
与添加元素的多种方式类似，（非array）容器也有多种删除元素的方式。表9.7列出了这些成员函数。
删除元素的成员函数并不检查其参数。在删除元素之前，程序员必须确保它（们）是存在的。
4.1.pop_front和pop_back成员函数
pop_front和pop_back成员函数分别删除首元素和尾元素。与vector和string不支持push_front一样，这些类型也不支持pop_front。类似的，forward_list不支持pop_back。与元素访问成员函数类似，不能对一个空容器执行弹出操作。
这些操作返回void。如果你需要弹出的元素的值，就必须在执行弹出操作之前保存它：
1
2
3
4
5
while (!ilist.empty())
{
process(ilist.front()); //对ilist的首元素进行一些处理
ilist.pop_front(); //完成处理后删除首元素
}
4.2.从容器内部删除一个元素
成员函数erase从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除的（最后一个）元素之后位置的迭代器。即，若j是i之后的元素，那么erase[i]将返回指向j的迭代器。
例如，下面的循环删除一个list中的所有奇数元素：
1
2
3
4
5
6
7
list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end())
if (*it % 2) //若元素为奇数
it = lst.erase(it); //删除此元素
else
++it;
4.3.删除多个元素
接受一对迭代器的erase版本允许我们删除一个范围内的元素：
1
2
3
//删除两个迭代器表示的范围内的元素
//返回指向最后一个被删元素之后位置的迭代器
elem1 = slist.erase(elem1, elem2); //调用后，elem1 == elem2
‼️迭代器elem1指向我们要删除的第一个元素，elem2指向我们要删除的最后一个元素之后的位置。
为了删除一个容器中的所有元素，我们既可以调用clear，也可以用begin和end获得的迭代器作为参数调用erase：
1
2
slist.clear(); //删除容器中所有元素
slist.erase(slist.begin(), slist.end()); //等价调用
5.特殊的forward_list操作
为了理解forward_list为什么有特殊版本的添加和删除操作，考虑当我们从一个单向链表中删除一个元素时会发生什么。如图9.1所示，删除一个元素会改变序列中的链接。在此情况下，删除$elem_3$会改变$elem_2$，$elem_2$原来指向$elem_3$，但删除$elem_3$后，$elem_2$指向了$elem_4$。
当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。为了添加或删除一个元素，我们需要访问其前驱，以便改变前驱的链接。但是，forward_list是单向链表。在一个单向链表中，没有简单的方法来获取一个元素的前驱。出于这个原因，在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。这样，我们总是可以访问到被添加或删除操作所影响的元素。
由于这些操作与其他容器上的操作的实现方式不同，forward_list并未定义insert、emplace和erase，而是定义了名为insert_after、emplace_after和erase_after的操作（见表9.8）。例如，在我们的例子中，为了删除$elem_3$，应该用指向$elem_2$的迭代器调用erase_after。为了支持这些操作，forward_list也定义了before_begin，它返回一个首前（off-the-beginning）迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素（亦即在链表首元素之前添加删除元素）。
当在forward_list中添加或删除元素时，我们必须关注两个迭代器—一个指向我们要处理的元素，另一个指向其前驱。例如，我们将4.2部分的例子改为从forward_list中删除元素：
1
2
3
4
5
6
7
8
9
10
11
12
13
forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); //表示flst的“首前元素”
auto curr = flst.begin(); //表示flst中的第一个元素
while (curr != flst.end()) //仍有元素要处理
{
if (*curr % 2) //若元素为奇数
curr = flst.erase_after(prev); //删除它并移动curr
else
{
prev = curr; //移动迭代器curr，指向下一个元素，prev指向curr之前的元素
++curr;
}
}
6.改变容器大小
如表9.9所描述，我们可以用resize来增大或缩小容器，与往常一样，array不支持resize。如果当前大小大于所要求的大小，容器后部的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部：
1
2
3
4
list<int> ilist(10, 42); //10个int：每个的值都是42
ilist.resize(15); //将5个值为0的元素添加到ilist的末尾
ilist.resize(25, -1); //将10个值为-1的元素添加到ilist的末尾
ilist.resize(5); //从ilist末尾删除20个元素
7.容器操作可能使迭代器失效
向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误，很可能引起与使用未初始化指针一样的问题。
在向容器添加元素后：
- 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
- 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
- 对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效，这应该不会令人惊讶。毕竟，这些元素都已经被销毁了。当我们删除一个元素后：
- 对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
- 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
- 对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。
7.1.编写改变容器的循环程序
添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//傻瓜循环，删除偶数元素，复制每个奇数元素
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin(); //调用begin而不是cbegin，因为我们要改变vi
while (iter != vi.end())
{
if (*iter % 2)
{
iter = vi.insert(iter, *iter); //复制当前元素
iter += 2; //向前移动迭代器，跳过当前元素以及插入到它之前的元素
}
else
{
iter = vi.erase(iter); //删除偶数元素
//不应向前移动迭代器，iter指向我们删除的元素之后的元素
}
}
7.2.不要保存end返回的迭代器
当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。通常C++标准库的实现中end()操作都很快，部分就是因为这个原因。
例如，考虑这样一个循环，它处理容器中的每个元素，在其后添加一个新元素。我们希望循环能跳过新添加的元素，只处理原有元素。在每步循环之后，我们将定位迭代器，使其指向下一个原有元素。如果我们试图“优化”这个循环，在循环之前保存end()返回的迭代器，一直用作容器末尾，就会导致一场灾难：
1
2
3
4
5
6
7
8
9
10
//灾难：此循环的行为是未定义的
auto begin = v.begin(), end = v.end(); //保存尾迭代器的值是一个坏主意
while (begin != end)
{
//做一些处理
//插入新值，对begin重新赋值，否则的话它就会失效
++begin; //向前移动begin，因为我们想在此元素之后插入元素
begin = v.insert(begin, 42); //插入新值
++begin; //向前移动begin跳过我们刚刚加入的元素
}
此代码的行为是未定义的。在很多标准库实现上，此代码会导致无限循环。问题在于我们将end操作返回的迭代器保存在一个名为end的局部变量中。在循环体中，我们向容器中添加了一个元素，这个操作使保存在end中的迭代器失效了。这个迭代器不再指向v中任何元素，或是v中尾元素之后的位置。
必须在每次插入操作后重新调用end()，而不能在循环开始前保存它返回的迭代器：
1
2
3
4
5
6
7
8
//更安全的方法：在每个循环步添加/删除元素后都重新计算end
while (begin != v.end())
{
//做一些处理
++begin; //向前移动begin，因为我们想在此元素之后插入元素
begin = v.insert(begin, 42); //插入新值
++begin; //向前移动begin跳过我们刚刚加入的元素
}
