顺序容器概述

一、前言

介绍顺序容器的种类及基本操作。

顺序容器

一个容器就是一些特定类型对象的集合。顺序容器（sequential container）为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。与之相对的是11章的有序和无序关联容器，它们根据关键字的值来存储元素。

所有顺序容器都提供了快速访问元素的能力，但是，这些容器在以下方面都有不同的性能折中。

• 向容器添加或从容器中删除元素的代价。
• 非顺序访问容器中的元素。

顺序容器类型：

vector 可变大小数组。支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。
list 双向链表。只支持双向顺序访问。在list中任何位置插入/删除都很快
forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作都很快。
array 固定大小数组。支持快速随机访问。不能添加或删除元素。
string 与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快。

• 除了array外，其他容器都提供高效、灵活的内存管理。
• string和vector将元素保存在连续的内存空间中。因为连续，所以下标访问非常快。但在中间插入、删除较慢（O(n)）。有时添加一个元素还可能需要分配的额外空间，这种情况所有元素必须移动到新的存储空间中
• forward_list和array是新C++标准增加的类型。array比内置数组更安全。forward_list没有size()操作。新标准库的容器比旧版本的快得多。

确定使用哪种顺序容器

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

• 一般用vector。
• 如果程序有很多小元素，且空间的额外开销很重要，则不要用list或forward_list。
• 要随机访问元素用vector或deque。
• 如果要在中间插入或删除元素，应用list或forward_list。
• 如果要在头尾插入或删除元素。但不会在中间插入或删除元素，用deque。
• 如果程序只有在读取输入的时候才需要在容器中间位置插入元素，随后需要随机访问元素。如果确实需要，则考虑在输入阶段用list，一旦输入完成，将list中的元素拷贝到一个vector中。

如果程序既需要随机访问元素，又需要在容器中间插入元素，该怎么办？

一般来说，应用中占主导地位的操作（执行的访问操作更多还是插入/删除更多）决定了容器类型的选择。在此情况下，对两种容器分别测试应用的性能可能就是必要的了。

容器库概述

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

• 某些操作是所有容器类型都提供的。
• 另外一些操作仅针对顺序容器、关联容器或无序容器。
• 还有一些操作只适用于一小部分容器。

对容器可以保存的元素类型的限制

顺序容器几乎可以保存任意类型的元素。特别是，我们可以定义一个容器，其元素的类型是另外一个容器。

vector<vector<string>> lines;     //lines是一个vector，其元类型是string的vector

某些类没有默认的构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：

//假定noDefault是一个没有默认构造函数的类型
vector<noDefault> v1(10,init);      //正确：提供了元素初始化器
vector<noDefault> v2(10);           //错误：必须提供一个元素初始化器

容器操作：(待补充)

迭代器

标准库array具有固定大小

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

array<int,42>        //类型为：保存42个int的数组
array<string,10>     //类型为：保存10个string的数组

为了使用array类型，我们必须同时指定元素类型和大小：

array<int,10>::size_type i;     //数组类型包括元素类型和大小
array<int>::size_type j;        //错误：array<int>不是一个类型

初始化array：

array<int,10> ia1;       //10个默认初始化的int
array<int,10> ia2 = {0,1,2,3,4,5,6,7,8,9};    //列表初始化
array<int,10> ia3 = {42};      //ia3[0]为42，剩余元素为0

值得注意的是，虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但是array并无此限制。

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;            //错误，内置数组不支持拷贝或赋值
array<int,10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int,10> copy = digits;   //正确，只要数组类型匹配即合法

赋值和swap

赋值相关的运算符可用于所有的容器。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝。

c1 = c2;       //将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c};  //赋值后，c1大小为3

如果两个容器原来的大小不同，赋值运算后两者的大小都与右边容器的原大小相同。

与内置数组不同，标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型。也就是array进行赋值，左右两边数组大小必须相等。

1.assign(仅顺序容器)

允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。例如，我们可以用assign实现将一个vector中的一段char *值赋予一个list中的string：

list<string> names;
vector<const char *> oldstyle;
name = oldstyle;   //错误，容器类型不匹配，赋值，类型必须完全一样
//正确：可以将const char * 转化为string
names.assign(oldstyle.cbegin(),oldstyle.cend());

assign的第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素：

//等价于slist1.clear();
//后跟slist1.insert(slist1.begin(),10,"Hiya!");
list<string> slist1(1);      //1个元素，为空string
slist1.assign(10,"Hiya!");

2.使用swap

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

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

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

在新标准中，容器既提供成员版本的swap，也提供非成员版本的swap。而早期标准库版本只提供成员函数版本的swap。非成员版本的swap在泛型编程中是非常重要的。统一使用非成员版本的swap是一个好习惯。

关系运算符

每个容器类型都支持相等运算符（== 和 ！=）；除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。关系运算符左右两边的运算对象必须是相同类型的容器。且必须保存相同类型的元素。

• 如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等；否则两个容器不等。
• 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
• 如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等的元素的比较结果。

容器的关系运算符使用元素的关系运算符完成比较：
容器的相等运算符实际上是使用元素的==运算符 来实现比较的，而其他关系运算符 是使用元素的<运算符 。如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算符。

vector<Sale_data> storeA, storeB;
if(storeA < storeB)                 // 错误：Sales_data没有<运算符

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

顺序容器的操作

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。上一节介绍了所有容器都支持的操作。本章剩余部分将介绍顺序容器所特有的操作。

向顺序容器添加元素

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

向顺序容器添加元素的操作：
操作会改变容器的大小；array不支持这些操作。

forward_list有自己专有版本的insert和emplace；
forward_list不支持push_back和emplace_back
vector和string不支持push_front和emplace_front
c.push_back(t)　　　　　　　　在c的尾部创建一个值为t或由args创建的元素，返回void
c.emplace_back(args)
c.push_front(t)　　　　　　　　在c的头部创建一个值为t或由args创建的元素，返回void
c.emplace_front(args)
c.insert(p,t)　　　　　　　　　  在迭代器p指向的元素之前创建一个值为t或由args创建的元素，返回指向新添加的元素的迭代器
c.emplace(p,args)
c.insert(p,n,t)　 在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器；若n为0，则返回p
c.insert(p,b,e)　 将迭代器b和e指向的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素，返回指向新添加的第一个元素的迭代器；若范围为空，则返回p
c.insert(p,il)　　il是一个花括号包围的元素值列表，将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器：若列表为空，则返回p

向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。

当我们使用这些操作时，必须记得不同容器使用不同的策略来分配元素空间，而这些策略直接影响性能。在一个vector或string的尾部之外的任何位置，或是一个deque的首位之外的任何位置添加元素，都需要移动元素。而且，向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。

使用push_back

我们看到push_back将一个元素追加到一个vector的尾部。除array和forward_list之外，每个顺序容器（包括string类型）都支持push_back。

例如，下面的循环每次读取一个string到word中，然后追加到容器尾部：

//从标准输入读取数据，将每个单词放到容器末尾
string word;
while(cin>>word)
　　container.push_back(word);

对push_back的调用在container尾部创建了一个新的元素，将container的size增大了1。该元素的值为word的一个拷贝，container的类型可以是list、vector或deque。

关键概念：当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

使用push_front

除了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头部。每个元素都插入到list的新的开始位置。即，当我们插入1时，它会被放置在0之前，2被放置在1之前，依次类推。因此，在循环中以这种方式将元素添加到容器中，最终会形成逆序。

注意： deque像vector一样提供了随机访问元素的能力，但它提供了vector所不支持的push_front。deque保证在容器首部进行插入和删除元素的操作都只花费常数时间。与vector一样，在deque首尾之外的位置插入元素会很耗时。

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

push_back和push_front操作提供了一种方便地在顺序容器尾部或头部插入单个元素的方法。insert成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。forward_list提供了特殊版本的insert成员。

每个insert函数都接受一个迭代器作为其一个参数。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置。由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能， 所有insert函数将元素插入到迭代器所指定的位置之前 。例如，下面的语句

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

虽然某些容器不支持push_front操作，但他们对于insert操作并无类似的限制（插入开始位置）。因此我们可以将元素插入到容器的开始位置，而不必担心容器是否支持push_front:

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中的任何位置都是合法的。然而，这样做可能很耗时。

插入范围内元素

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

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

这行代码将10个元素插入到svec的末尾，并将所有元素都初始化为string“Anna”。

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

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()); //运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器

如果我们传递给insert一对迭代器，它们不能指向添加元素的目标容器。

使用insert的返回值

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

list<string> lst;
auto iter=lst.begin();
while(cin>>word)
　　iter=lst.insert(iter,word);  //等价于调用push_front

在循环之前，我们将iter初始化为lst.begin()。第一次调用insert会将我们刚刚读入的string插入到iter所指向的元素之前的位置。insert返回的迭代器恰好指向这个新元素。我们将此迭代器赋予iter并重复循环，读取下一个单词。

使用emplace操作

使用emplace操作

新标准引入了三个成员——emplace_front、emplace和emplace_back，这些操作（构造而不是拷贝元素）。这些操作分别对应push_front、insert和push_back，允许我们将元素放置在容器头部、一个指定的位置之前或容器尾部。

当调用push或insert成员函数时，我们将元素类型对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。例如，假定c保存Sales_data元素：

//在c的末尾构造一个Sales_data对象
//使用三个参数的Sales_data的构造函数
c.emplace_back("978-0590353403",25,15.99);
c.push_back("978-0590353403",25,15.99);     //错误：没有接受三个参数的push_back版本
//正确：创建一个临时的Sales_data对象传递给push_back
c.push_back(Sales_data(("978-0590353403",25,15.99));

其中对emplace_back的调用和第二个push_back调用都会创建新的Sales_data对象。在调用emplace_back时，会在容器管理的内存空间中直接创建对象。而调用push_back则会创建一个局部临时对象，并将其压入容器中。

emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配 ：

//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函数的参数必须与元素类型的构造函数相匹配。


## 访问元素 （访问成员函数返回的是引用）

下表列出了我们可以用来在顺序容器值访问元素的操作。如果容器中没有元素，访问操作的结果是未定义的。

包括array在内的每个顺序容器都有一个front成员函数，而除了forward_list之外的所以顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用：

//在解引用一个迭代器或调用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不支持

此程序用两种不同方式来获取c中的首元素和尾元素的引用。 直接的方式是调用front和back。而间接的方法是通过解引用begin返回的迭代器来获得首元素的引用，以及通过递减然后解引用end返回的迭代器来获取尾元素的引用。

在顺序容器中访问元素的操作

at和下标操作只适用于string、vector、deque和array。
back不适用于forward_list。
c.back() 　　　　　　　　　　返回c中尾元素的引用。若c为空，函数行为未定义
c.front()　　　　　　　　　　 返回c中首元素的引用。若c为空，函数行为未定义
c[n]　　　　　　　　　　　　 返回c中下标为n的元素的引用，n是一个无符号整数。若n>c.size(),则函数的行为未定义
c.at[n]　　　　　　　　　　  返回下标为n的元素的引用。如果下标越界，则抛出一个out_of_range异常

对一个空容器调用front和back，就像使用一个越界的下标一样。是一种严重的程序设计错误。

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

在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。如果容器是一个const对象，则返回值是const的引用。如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值：

if(!c.empty()){
    c.front() = 42;   //将42赋予c中的第一个元素
    auto &v = c.back();     //获得指向最后一个元素的引用
    v = 1024;          //改变c中的元素
    auto v2 = c.back();    //v2不是一个引用，它是c.back()的一个拷贝
    v2 = 0;
}

与往常一样，如果我们使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型。

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

提供快速随机访问的容器(string、vector、deque和array)也都提供下标运算符。就像我们已经看到的那样，下标运算符接受一个下标参数，返回容器中该位置的元素的引用。

我们希望确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，但如果下标越界，at会抛出一个out_of_range异常：

vector<string> svec;  //空vector
cout<<svec[0];   //运行时错误：svec中没有元素
cout<<svec.at[0];   //抛出一个out_of_range异常

删除元素

与添加元素的多种方式类似，（非array）容器也有多种删除元素的方式。如下表所示：

顺序容器的删除操作

这些操作会改变容器的大小，所以不适用于array
forward_list有特殊版本的erase
forward_list不支持pop_back；vector和string不支持pop_front
c.pop_back() 　　　　　　删除c中尾元素，若c为空，则函数行为未定义，函数返回void
c.pop_front()　　　　　　删除c中首元素，若c为空，则函数行为未定义，函数返回void
c.erase(p)　　　　　　　 删除迭代器p所指的元素，返回以指向被删除元素之后的迭代器，若p指向尾元素，则返回尾后迭代器。若p是尾后迭代器，则函数的行为未定义
c.erase(b,e)　　　　　　 删除迭代器b和e所指定范围内的元素，返回一个指向最后一个被删除元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear()　　　　　　　　 删除c中的所以元素，返回void

删除deque中除首位元素之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

pop_front和pop_back成员函数

pop_front和pop_back成员函数分别删除首元素和尾元素。与vector和string不支持push_front一样，这些类型也不支持pop_front。类似的，forward_list不支持pop_back。与元素访问成员函数类似，不能对一个空容器执行弹出操作。

这些操作返回void，如果你需要弹出的元素的值，就必须在执行弹出操作之前保存它：

while(!ilist.empty()){
　　process(ilist.front());  //对ilist的首元素进行一些处理
　　ilist.pop_front();　　//完成处理后删除首元素
}

从容器内部删除一个元素

成员函数erase从容器中指定位置删除元素，我们可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除的（最后一个）元素之后位置的迭代器。即，若j是i之后的元素，那么erase(i)将返回指向j的迭代器。

例如，下面的循环删除一个list中的所有奇数元素：

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;

每个循环步中，首先检查当前元素是否是奇数，如果是，就删除该元素，并将it设置为我们所删除的元素之后的元素。如果*it为偶数，我们将it递增，从而在下一步循环检查下一个元素。

删除多个元素

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

//删除两个迭代器表示的范围内的元素
//返回指向最后一个被删除元素之后位置的迭代器
elem1=slist.erase(elem1,elem2);  //调用后，elem1==elem2

迭代器elem1指向我们要删除的第一个元素，elem2指向我们要删除的最后一个元素之后的位置。

为了删除一个容器中的所有元素，我们既可以调用clear，也可以用begin和end获得的迭代器作为参数调用erase：

slist.clear() ;//删除容器中的所有元素
slist.erase(slist.begin(),slist.end());   //等价调用