《C++primer》读书笔记---第九章：顺序容器

9.1顺序容器概述

下表列出了标准库的顺序容器，所有容器都提供了快速顺序访问元素的能力：
在这里插入图片描述
多种容器中，通常使用vector是最好的选择，除非你有很好的理由选则其他容器。以下是一些选择容器的基本原则：

除非你有很好的理由选择其他容器，否则选择vector
如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list
如果程序要求随机访问元素，使用vector或deque
如果程序要求在容器的中间增加或删除元素，则使用list或forward_list
如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque

注：如果你不确定应该是使用哪种容器，那么可以在程序中只使用vector和list的公共操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用vector或list都很方便。

9.2容器库概览

一般来说，每种容器都定义在一个头文件中，且头文件的名字和容器名字相同。例如：deque容器保存在deque头文件中，list容器保存在list头文件中。下表是容器的一些通用操作：
在这里插入图片描述

在这里插入图片描述

迭代器

迭代器范围：

一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾后元素。这两个迭代器通常被称为begin和end，或者是first和last（可能有些误导），他们标记了容器中元素的一个范围。
这种元素范围被称为左闭合区间，其标准数学描述为：[begin,end)，表示范围自begin开始，与end前结束。
标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和ebd构成一个合法的迭代器范围，则：

如果begin和end相等，则容器为空
如果begin和end不相等，则容器中至少包含一个元素，且begin指向第一个元素
我们可以对begin递增若干次，使得begin==end

begin和end成员

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

list<string> a = {"a","b","c"};
auto it1 = a.begin();//list<string>::iteartor
auto it2 = a.rbegin();//list<string>::reverse_iteartor
auto it3 = a.cbegin();//list<string>::const_iteartor
auto it4 = a.crbegin();//list<string>::const_reverse_iteartor

以c开头的是C++11的新标准引入的，用以支持auto与begin和end函数结合使用。当不需要写访问时，应该使用cbegin和cend。

容器定义和初始化

每个容器都定义了一个默认构造函数。除array外，其它容器默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数
在这里插入图片描述
将一个新容器创建为另一个容器的拷贝的方法有两种：可以直接拷贝整个容器，或者（array除外）拷贝由一个迭代器对指定的范围。为了创建一个容器为另一个容器的拷贝时，两个容器的类型及其元素类型必须匹配。不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。

//每个容器都有三个元素，用给定的初始化器进行初始化
list<string> authors = {"a","b","c"};
vector<const char*> articles = {"a","an","the"};
list<string> list2(authhor);//正确，类型匹配
deque<string> authList(authors);//错误，容器类型不匹配
vector<string> words(articles);//错误，容器类型必须匹配
//正确，可以将const char*元素转换为string
forwward_list<string> words(articles.begin(),articles.end());

赋值和swap

与内置数组不同，标准库array类型允许赋值。赋值号左右两侧的运算对象必须具有相同的类型：

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

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

使用assign（仅顺序容器）

赋值运算符要求左边和右边的运算对象具有相同的类型。它将右边运算对象中所有元素拷贝到左边运算对象中。顺序容器（除array外）还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。

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

使用swap

swap操作交换两个相同类型容器的内容。调用swap后，两个容器中的元素将会交换：

vector<string> svec1(10);//10个元素的vector
vector<string> svec2(24);//24个元素的vector
swap(svec1,svec2);

调用swap后，svec1将包含24个string元素，svec2将包含10的string。除array外，交换两个容器内容的操作保证会很快–元素本身并未交换，swap只是交换了两个容器的内部数据结构。
注：除array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间完成。
元素不会被移动的事实意味着，除string外，指向容器的迭代器、引用和指针在swap后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是，在swap后，这些元素已经属于不同容器了。例如：假定iter在swap之前指向svec1[3]的string，那么在swap后它指向svec2[3]的元素。
与其他容器不同，swap两个array会真正交换它们的元素。因此，交换两个array所需的时间与array中元素的数目成正比。

9.3顺序容器操作

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。下表列出了向顺序容器添加元素的操作。
在这里插入图片描述
前面的章节中介绍过push_back,除了push_back外，list、forward_list和deque容器还支持名为push_front的类似操作。此操作将元素插入到容器头部：

list<int> ilist;
//将元素添加到ilist开头
for(size_t ix = 0;ix!=4;++ix)ilist.push_front(ix);

此循环将元素0、1、2、3添加到ilist头部。
insret成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。每个insert函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置放置新元素。insert函数将元素插入到迭代器所指定的位置之前。例如下面的语句：

slist.insert(iter,"Hello!");//将Hello！添加到iter之前的位置

除了第一个迭代器参数之外，insert函数还可以接受更多的参数，其中一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些位置都按给定值初始化：

svec.insert(svec.end(),10,"Anna");

这行代码将10个元素插入到svec的末尾，并将所有元素都初始化为string"Anna"。
接受一对迭代器或一个初始化列表的insert版本将给定范围中的元素插入到指定位置之前：

vector<string> v ={"a","b","c","d"};
//将v的最后两个元素添加到slist的开始位置
slist.insert(slist.begin(),v.end()-2,v.end());
slist.insert(slist.end(),{"a","b","c","d"});
//运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器
slist.insert(slist.begin(),slist.begin(),slist.end());

访问元素

在这里插入图片描述
在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。如果容器是一个const对象，则返回值是const的引用。如果容器不是const的，则返回值是普通引用。

删除元素

下表列出的是多种删除元素的方式
在这里插入图片描述

forward_list的特殊操作

下表列出了forward_list的特殊操作：
在这里插入图片描述

改变容器大小

在这里插入图片描述

list<int> ilist(10,42);//十个int，每个值都是42
ilist.resize(15);//将五个值为0的元素添加到ilist的末尾
ilist.resize(25,-1);//将十个值为-1的元素添加到ilist的末尾
ilist.resize(5);//从ilist末尾删除20个元素

9.4vector对象是如何增长的

假定容器中元素是连续存储的，且容器的大小是可变的，考虑向vector或string中添加元素会发生什么:如果没有空间容纳新元素，容器不可能简单地将它添加到内存中其他位置–因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。如果我们每添加一个新元素，vector就执行一次这样的内存分配和释放操作，性能会慢到不可接受。
为了避免这种代价，标准库实现者采用了可以减少容器的空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间，容器预留这些空间作为备用，可用来保存更多元素。
vector和string类型提供了一些成员函数，允许我们与它的实现中内存分配部分互动：
在这里插入图片描述