第9章 顺序容器

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

1 顺序容器概述

标准库中的顺序容器如下表所示：

通常，使用vector是最好的选择，除非有很好的理由选择其他

2 容器库概览

所有容器类型都提供以下操作：

2.1 迭代器

迭代器的范围是左闭右开区间，[begin, end)。对构成范围的迭代器的要求：

• 它们指向同一个容器中的元素
• end不在begin之前

begin和end有多个版本：带r的版本返回反向迭代器；以c开头的版本则返回const迭代器。

容器的定义和初始化方法：

简而言之：

• 列表初始化 C c{a,b,c}或者C c={a,b,c}
• 拷贝初始化C c1=c2或者C c1(c2)
• 大小与（可选的）元素初始值构造 C seq(n)或者C seq(n,t)

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同；不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，并且新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

只有顺序容器（除array外）的构造函数才接受大小参数，关联容器并不支持。

list<string> authors = {"Mike","Jack","Austin"};
vector<const char*> articles = {"a","an","the"};
list<string> list2(authors); // 正确，类型匹配
deque<string> authList(authors); // 错误，容器类型不匹配
vector<string> words(articles); // 错误，元素类型不匹配
forward_list<string> words(article.begin(), articles.end()); // 正确，可以将const char*转换成string

标准库array具有固定大小。为了使用array类型，必须同时指定元素类型和大小。

array<int, 42>
array<int, 10>::size_type i; // 正确
array<int>::size_type j; // 错误：array<int>不是一个类型

2.5 赋值和swap

与内置数组不同，标准库array类型允许赋值

array<int,5> a1 = {0,1,2,3,4};
array<int,10> a2 = {0}; // 所有元素均为0
a1 = a2; // 替换a1中的元素
a2 = {0}; // 错误，不能将一个花括号列表赋予数组

由于右边运算对象的大小可能与左边运算对象的大小不同，因此array类型不支持assign，也不允许用花括号包围的值列表进行赋值。

使用assign（仅顺序容器）

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

list<string> names;
vector<const char*> oldstyle;
names = oldstyle; // 错误，类型不匹配
// 正确，可以将const char*转换成string
names.assign(oldstyle.cbegin(), oldstyle.cend()); 

使用swap

swap操作交换两个相同类型容器的内容

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

swap中元素本身并未交换，只是交换了两个容器的内部数据结构。因此指向容器的迭代器、引用和指针在swap操作后都不会失效，它们仍指向swap操作之前指向的那些元素。

Note: 对一个string调用swap会导致迭代器等失效；swap两个array会真正交换它们的元素。

3 顺序容器操作

3.1 添加元素

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

3.2 访问元素

访问成员函数的返回是引用。

3.3 删除元素

// 删除一个list中的所有奇数元素
list<int> lst = {0,1,2,3,4};
auto it = lst.begin();
while(it != lst.end())
    if (*it % 2)
        it = lst.erase(it); 
	else
        ++it;

3.4 特殊的forward_list操作

当从一个单向链表中删除元素时，会改变序列中的链接。

因此为了添加或删除一个元素，需要访问其前驱以改变链接，但在单向链表中难以获取元素的前驱，因此forward_list中添加或删除元素的操作是通过改变元素之后的元素来完成的。

其中定义了一个首前迭代器before_begin，允许在链表首元素之前并不存在的元素“之后”添加删除元素。

改写前序从list中删除奇数元素：

forward_list<int> flst = {0,1,2,3,4};
auto prev = flst.before_begin();  // 表示flst的首前元素
auto curr = flst.begin(); 
while (curr != flst.end()) {
    if (*curr % 2)
        curr = flst.erase_after(prev); 
    else { // 移动curr指向下一个元素，prev指向之前的元素
		prev = curr;
    	++curr;
    }
}

3.5 改变容器大小

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

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

在向容器添加元素后：

• 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器等仍有效，而指向插入位置之后的失效。
• 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。
• 对于list和forward_list，指向容器的迭代器等仍有效

当删除元素时：

• 对于list和forward_list，指向容器其他位置的迭代器等仍有效
• 对于deque，如果在首尾之外的任何位置删除元素，则指向其他元素的迭代器等失效
• 对于vector和string，指向被删元素之前的仍有效。

因此，添加/删除元素的循环程序必须考虑迭代器等失效的问题。insert和erase操作返回迭代器，可以用来更新：

// 删除偶数元素，复制奇数元素
vector<int> vi = {0,1,2,3,4}
auto iter = vi.begin(); 
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter,*iter); // 在当前元素之前复制元素
        iter += 2; // 向前移动迭代器，跳过当前元素以及插入到它之前的元素
    }
    else
        iter = vi.erase(iter); // iter指向删除的元素之后的元素
}

4 vector对象是如何增长的

为了支持快速随机访问，vector 将元素连续存储一每个元素紧挨着前一个元素存储。 为了提高添加元素的效率，vector 和 string 的实现通常会分配比新的空间需求更大的内存空间 。其也提供了一些成员函数管理容量：

5 额外的string操作

除了顺序容器共同的操作之外，string 类型还提供了一些额外的操作。 这些操作中的大部分要么是提供 string 类和 C 风格字符数组之间的相互转换，要么是增加了允许用下标代替迭代器的版本。

5.1 构造string的其他方法

通常当我们从一个const char*创建string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。如果还传递给构造函数一个不大于数组大小的计数值，则数组就不必以空字符结尾。

const char *cp = "Hello World!!"; // 以空字符结束的数组
char noNull[] = {'H', 'i'}; // 不是以空字符结束
string s1(cp); // 正确
string s2(noNull,2); // 正确，s2 == "Hi"
string s3(noNull); // 未定义，noNull不是以空字符结束

substr操作

substr(pos,n) 返回一个string,包含s中从pos开始的n个字符的拷贝。pos默认值0，n默认值s.size()-pos。

5.2 改变string的其他方法

除了接收迭代器的insert和erase版本外，string还提供了接受下标的版本。下标指出了开始删除的位置，或是insert到给定值之前的位置。

append和replace函数

5.3 string搜索操作

string类提供的搜索操作如下表。每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败，则返回一个名为string::npos的static成员。

对于args的要求：

compare函数

s.compare(pos1,n1,s2,pos2,n2)，根据s与s2的比较结果，返回0、正数或负数。

数值转换

6 容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue、priority_queue。适配器是标准库中的一个通用概念，容器、迭代器和函数都有适配器。