《C++ Primer》第9章：顺序容器-冲突漫画

最近几天都是满课，每天的可支配时间都很短，真是吐了

只能硬熬到3点钟了，趁着国庆节，明天开干龙书

1.概述

2.确定使用哪种顺序容器

默认使用vector

如果要求随机访问元素，使用vector或deque

如果要求在中间插入或删除元素，使用list或forward_list

如果要求在头尾插入或删除，但不会在中间位置进行插入或删除操作，使用deque

如果只在读取输入时需要在中间插入元素，随后需要随机访问元素，考虑在输入阶段使用list，随后将list中的内容拷贝到vector中

二、容器库概述

1.概述

容器类型上的操作形成了一种层次：

某些操作是所有容器类型都提供的

另外一些操作仅针对顺序容器、关联容器或无序容器

还有一些操作只适用于一小部分容器

2.迭代器

迭代器范围

一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或尾元素之后的位置，这两个迭代器通常被称为begin和end

迭代器范围中的元素包括begin所表示的元素和从begin开始直到end（但不包含end）之间的所有元素，即左闭右开区间 [begin, end)

使用左闭右开区间蕴含的编程假定

如果begin与end相等，则范围为空

如果begin与end不等，则范围中至少包含一个元素，且begin指向该范围中的第一个元素

我们可以对begin递增若干次，使得begin==end

3.容器类型成员

通过类型别名，可以在不了解容器中元素类型的情况下使用它

如果需要元素类型，可以使用容器的value_type

如果需要元素类型的一个引用可以使用容器的reference或const_reference

4.begin和end成员

当不需要写访问时，应使用cbegin()和cend()

rbegin()和rend()返回指向目标尾元素和首元素之前的位置的迭代器

5.容器定义和初始化

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同

当传递迭代器参数来拷贝一个范围时，对容器类型不做要求，而对元素类型，只要能将拷贝的元素类型转换为初始化的容器的元素类型即可

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

如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数

如果元素类型没有默认构造函数，除了大小参数，还必须指定一个显示的元素初始值

标准库array具有固定大小

当定义一个array时，除了指定元素类型，还要指定容器大小

6.赋值和swap

使用swap

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

除array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间内完成

除string外，指向容器的迭代器、引用和指针在swap操作后都不会失效，它们仍指向swap操作之前所指向的那些元素

7.容器大小操作

size()：返回容器中元素的数目

empty()：当size为0时返回true，否则返回false

max_size()：返回一个大于或等于该类型容器所能容纳的最大元素数的值

8.关系运算符

每个容器类型都支持相等运算符（==和≠），除了无需关联容器外所有容器都支持关系运算符（>、≥、<、≤）

关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素

只有当元素类型定义了相应的比较运算符时，才可以使用关系运算符来比较两个容器

比较两个容器实际上是逐对比较，与string的关系运算类似

三、顺序容器操作

1.添加元素

使用push_back

除array和forward_list，每个顺序容器都提供了push_back操作

push_back操作将在容器尾部创建一个新的元素，并将容器的size增大1，该元素的值为添加元素的拷贝

使用push_front

list、forward_list和deque容器都提供了push_front操作

push_front操作将元素插入容器头部

在容器中的特定位置添加元素

vector、deque、list和string都提供了insert操作

insert操作将元素插入到迭代器所指定的位置之前

插入范围内元素

insert操作接受一个元素数目和一个值的版本，将指定数量的元素添加到指定位置之前，并将这些元素按给定值初始化

insert操作接受一对迭代器或一个初始化列表的版本，将给定范围中的元素插入到指定位置之前

使用insert的返回值

接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器，如果范围为空，不插入任何元素，insert操作会将第一个参数返回

通过使用insert的返回值，可以在容器中一个特定位置反复插入元素

使用emplace操作

当调用push或insert时，将元素类型的对象传递给它们，这些对象被拷贝到容器

当调用emplace时，将参数传递给元素类型的构造函数，emplace成员使用这些参数在容器管理的内存空间中直接构造元素

emplace函数在容器中直接构造元素，传递给emplace函数的参数必须与元素类型的构造函数相匹配

2.访问元素

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

在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用，如果容器是一个const对象，则返回值是const的引用

下标操作和安全的随机访问

at操作类似下标运算，但如果下标越界，at会抛出一个out_of_range异常

3.删除元素

pop_front和pop_back成员函数

pop_front和pop_back操作分别删除首元素和尾元素，这些操作返回void，如果你需要pop元素的值，就必须在执行pop之前保存它

从容器内部删除一个元素

erase操作从容器指定位置删除元素，可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素

两种形式的erase的返回值都返回指向删除的（最后一个）元素之后位置的迭代器

删除多个元素

erase操作接受一对迭代器的版本允许删除一个范围内的元素

4.特殊的forward_list操作

*以下内容如果学过数据结构中的链表操作应该会很好理解

从一个单向链表中添加或删除一个元素时，会改变序列中的链接，删除或添加的元素之前的那个元素的后继会发生改变

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

forward_list定义了insert_after、emplace_after和erase_after操作，为了删除elem3，应该用指向elem2的迭代器调用erase_after

为了支持这些操作，forward_list定义了before_begin，它返回一个首前迭代器（指向头结点），这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素

5.改变容器大小

resize操作可以增大或缩小容器，如果当前容量大于新容量，容器后部的元素会被删除；如果当前容量小于新容量，会将新元素添加到容器后部

resize操作接受一个可选的元素值参数，用来初始化添加到容器中的元素

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

在容器中添加元素后：

对于vector和string，如果存储空间重新分配，则指向容器的迭代器等都会失效。如果存储空间未重新分配，则指向插入位置前的迭代器等仍有效，但指向插入位置之后的元素的迭代器等会失效

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

对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效

在容器中删除元素后，指向被删除元素的迭代器、指针和引用都会失效：

对于vector和string，指向删除位置之前的迭代器、引用和指针仍有效，但指向删除位置之后的元素的迭代器等都会失效

对于deque，在首尾之外的任何位置删除元素都会导致迭代器、引用和指针失效。如果在尾部删除元素，则尾后迭代器会失效，但其他迭代器、引用和指针不受影响。如果在头部删除元素，则这些也不会受影响

对于list和forward_list，指向容器的其他位置的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效

不要保存end返回的迭代器

添加/删除vector、string或deque中首元素之外的位置的元素后，原来的end返回的迭代器总是会失效。

因此，添加/删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用

四、vector对象是如何增长的

1.容器大小

管理容量的成员函数

reserve改变容器的容量，resize改变容器中元素的数目

shrink_to_fit并不保证一定会退回内存空间

capacity和size

capacity是在容器不分配内存空间的前提下，最多可以保存的元素数目

size是容器已经保存的元素数目

每个vector的实现都可以选择自己的内存分配策略，但必须遵守的一条原则是：只有当迫不得已时才可以分配新的内存空间

五、额外的string操作

1.构造string的其他方法

从一个const char*创建string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止

substr操作

substr操作返回一个string，它为原始string的一部分或全部的拷贝，可以传递给substr一个可选的开始位置和计数值

2.改变string的其他方法

string类型提供了接受下标的insert和erase版本

string类型也提供了接受C风格字符数组的insert和assign版本

append和replace函数

append操作是在string末尾进行插入操作的一种简写形式，即追加

replace操作是调用erase和insert的一种简写形式，即替换

改变string的多种重载函数

assign总是替换string中的所有内容，append总是将新字符追加到string末尾

replace可以通过一个位置和一个长度来指定范围，也可以通过一个迭代器来指定范围

insert可以通过一个下标或一个迭代器来指定插入点，新元素会插入到给定下标（或迭代器）之前的位置

新字符可以来自于另一个string，来自于字符指针（指向字符数组），来自于一个花括号包括的字符列表，或者是一个字符和一个计数器

3.string搜索操作

string搜索函数返回string::size_type值，该类型是一个unsigned类型。因此用一个int来保存并不是一个好主意

如果搜索失败，则返回string::npos的static成员，标准库将nops定义为一个const string::size_type类型，并初始化为-1

find搜索

find：查找指定的字符串，若找到，则返回第一个匹配位置的下标，否则返回npos

find_first_of：查找第一个与给定字符串中任何一个字符匹配的位置

find_first_not_of：查找第一个与给定字符串中的任何一个字符不匹配的位置

指定在哪里开始搜索

可以给find传递一个可选的开始位置，默认为0，可以用这个可选参数在字符串中循环地搜索子字符串出现的所有位置

逆向搜索

rfind：由右至左搜索，即搜索匹配字符串最靠右的出现位置

find_last_of：搜索与给定string中任何一个字符匹配的最后一个字符

find_last_not_of：搜索最后一个不出现在给定string中的字符

每个操作都接受一个可选的第二参数，指出从什么位置开始搜索

4.compare函数

compare根据s是等于、大于还是小于参数指定的字符串，返回0、整数或负数

5.数值转换

新标准引入了多个函数，可以实现数值数据与标准库string直接的转换

如果string不能转换为一个数值，这些函数抛出一个invalid_argument异常。如果转换得到的数值无法用任何类型表示，则抛出一个out_of_range异常

六、容器适配器

除了顺序容器，标准库还定义了三个顺序容器适配器：stack、queue和priority_queue

本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型

定义一个适配器

每个适配器都定义了两个构造函数：默认构造函数创建一个空对象，另一个构造函数接受一个容器的构造函数拷贝来初始化适配器

例如，假定deq是一个deque<int>，我们可以用deq来初始化一个新的stack

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的

我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型

stack可以使用除array和forward_list之外的任何容器类型来构造

queue可以用list和deque来构造

priority_queue可以用vector和deque来构造

栈适配器

stack<int> intStack; 定义了一个保存整型元素的栈intStack，初始时为空

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。我们只可以使用适配器操作，而不能使用底层容器的操作

队列适配器

标准库queue使用一种先进先出的存储和访问策略，进入队列的对象被放置到队尾，而离开队列的对象则从队首删除

priority_queue允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。默认情况下，标准库在元素类型上使用<运算符来确定相对优先级

七、总结

标准库容器是模板类型，用来保存给定类型的对象。在一个顺序容器中，元素是按顺序存放的，通过位置来访问。

所有容器（除array外）都提供高效的动态内存管理。vector和string都提供更细致的内存管理控制，这是通过它们的reserve和capacity实现的

当使用添加或删除元素的容器操作时，必须注意这些操作可能使指向容器中元素的迭代器、指针或引用失效，很多会使迭代器失效的操作，如insert和erase，都会返回一个新的迭代器，来帮助程序员维护容器中的位置