1 顺序容器

1.1 顺序容器概述

1.1.2 选择容器的基本原则

• 除非你有很好的理由选择其他容器，否则应使用 vector。
• 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用 list 或 forward_list。
• 如果程序要求随机访问元素，应使用vector或 deque。
• 如果程序要求在容器的中间插入或删除元素，应使用list或 forward_1ist。
• 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque。
• 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
  • 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向 vector 追加数据，然后再调用标准库的 sort 函数（我们将在10.2.3节介绍 sort（第343页））来重排容器中的元素，从而避免在中间位置添加元素。
  • 如果必须在中间位置插入元素，考虑在输入阶段使用1ist，一旦输入完成，将list中的内容拷贝到一个 vector中。

1.2 容器库概览

1.2.1 头文件

#include<vector>//类似的

较旧的编译器可能需要在两个>间加上空格

vector<vector<int> >

1.2.2 容器适用操作

续：
反向容器的额外成员（不支持 forward_list）

1.2.3 迭代器所有操作

1.2.4容器类型成员

iterator:迭代器
const_iterator:cbegin(),cend();只能读，不能用迭代器写
反向迭代器：++返回的是上一个而不是下一个
类型别名：reference和const_reference;在泛型编程中非常有用，16章看完后再整理

1.2.5 begin和end成员

list<string> a = {"Milton","Shakespeare","Austen");
auto it1 = a.begin();//list<string>;:iterator
auto it2 = a.rbeqin();//list<string>::reverse iterator
auto it3 = a.cbegin();//1ist<string>::const iterator
auto it4 a.crbegin();// list<string>::const_reverseiterator


// 显式指定类型
list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();
//是iterator还是 const iterator依赖于a的类型
auto it7= a.begin（）;// 仅当a是const时，it7是constiterator
auto it8 = a.cbegin（）;// it8是const_iterator

当 auto与begin 或end结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。但以c开头的版本还是可以获得 const iterator的，而不管容器的类型是什么。
当不需要写访问时，应使用 cbegin和 cend。

1.2.6 容器定义和初始化

每个容器类型都定义了一个默认构造函数（参见7.1.4 节，第 236 页）。除 array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数。

(1) 一个容器初始化为另一个的拷贝

1. 不使用迭代器直接拷贝

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

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

2. 使用迭代器的方法

//拷贝元素，直到（但不包括）it指向的元素
deque<string> authList(authors,begin(),it);

3. 列表初始化

//每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors =("Milton","Shakespeare","Austen");
vector<const char*> articles={"a","an","the");
//当这样做时，我们就显式地指定了容器中每个元素的值。对于除 array之外的容器类型，初始化列表还隐含地指定了容器的大小∶容器将包含与初始值一样多的元素。

4. 与顺序容器大小相关的构造函数,即C seg(n,t),array除外

vector<int> ivec (10,-1); //10个int元素，每个都初始化为-1
list<string> svec (10,"hi!"); // 10个 strings;每个都初始化为"hi!"
forward_1ist<int> ivec (10); //10个元素，每个都初始化为0
deque<string> svec(10); //10个元素，每个都是空string

只有顺序容器的构造函数才接收大小参数，关联容器不支持
只有有默认构造函数的才可以只指定大小参数而不指定初始值

5. 关于array的
   a. 必须指定容器大小

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

//为了使用 array类型，我们必须同时指定元素类型和大小∶
array<int,10>::size_type i; // 数组类型包括元素类型和大小
array<int>::size_type j; // 错误∶array<int>不是一个类型

b. 列表初始化时，初始值数目必须小于等于array大小

array<int,10> ial; // 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

c. 不能对内置数组类型进行拷贝或对象赋值操作，但 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;//正确∶只要数组类型匹配即合法

d. array类只能在初始化时才可以用列表，赋值时不可以用列表赋

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

由于右边运算对象的大小可能与左边运算对象的大小不同，因此array类型不支持 assign，
也不允许用花括号包围的值列表进行赋值。
e. array使用swap会真正的交换数据

1.2.7 赋值和swap

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

注意：第一个赋值运算后，左边容器将与有边容器相等。如果两个容器原来大小不同，赋值运算后两者的大小都与右边容器的原大小相同。第二个赋值运算后，c1的 size变为3，即花括号列表中值的数目。

(1) assign的使用(仅顺序容器)

1. 一个容器给另一个赋值

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

注意：1. 前面初始化时也是，可以这样用

2. 用指定数目且具有相同给定值的元素替换容器中原有的元素

//等价于slist1.clear（）;
//后跟 slist1.insert（slist1.begin（），10，"Hiya!"》;
1ist<string> slist1(1); // 1个元素，为空string
slist1.assign（10，"Hiya!"); // 10个元素，每个都是"Hiya!"

(2) 使用swap

//swap 操作交换两个相同类型容器的内容。调用swap 之后，两个容器中的元素将会交换∶
vector<string> svecl（10）;// 10个元素的vector
vector<string> svec2（24）;// 24个元素的 vector
swap (svec1,svec2);

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

1.2.8 容器大小的操作

除了一个例外，每个容器类型都有三个与大小相关的操作。

1. 成员函数 size返回容器中元素的数目；
2. empty当size 为0时返回布尔值 true，否则返回 false;
3. max_size 返回一个大于或等于该类型容器所能容纳的最大元素数的值。
4. forwardlist支持max_size 和empty，但不支持size，原因我们将在下一节解释。

1.2.9 关系运算符

顺序与关联均支持：==和!=
仅顺序支持：>,<,>=,<=

(1) 使用规则

1. 左右必须是相同类型的容器
2. 比较实际上是逐元素比较的
3. 如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等;否则两个容器不等。
4. 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。（感觉和第五个判断冲突了）
5. 如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等的元素的比较结果。

vector<int> vl=! 1,3,5,7,9,12 );
vector<int> v2 =1,3,9J;
vector<int> v3 =[ 1,3,5,7 1;
vector<int> v4=[1,3,5,7,9,12);
v1< v2 //true;v1和v2在元素【2】处不同∶v1【2】小于等于v2【2】
vl < v3 // false;所有元素都相等，但v3中元素数目更少
v1 == v4// true;每个元素都相等，且v1和v4大小相间
vl== v2 // false;v2元素数目比v1少

注意：容器的运算符比较实际还是内部元素的比较，如果元素没有定义这种比较，就会报错

1.3 顺序容器的操作

1.3.1 添加元素

(1) push_back的使用

除array和forward_list之外都支持

1. string以外的

//例如，下面的循环每次读取一个 string到 word中，然后追加到容器尾部∶
// 从标准输入读取数据，将每个单词放到容器末尾
string word;
while (cin >> word)
    container.push_back (word);

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

由于string是一个字符容器，我们也可以用push_back 在string末尾添加字符∶
void pluralize(size_t cnt,string word)
{
    if (cnt > 1)
        word.push_back（'s'）;// 等价于word +='s'
}

(2) push_front

仅list，forward_list,deque支持

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

(3) 特定位置插入元素

第一个参数都是迭代器

1. 插入单个元素

list.insert（iter，"Hello!"）;//将"Hello!"添加到iter之前的位置

vector<string> svec;
list<string> slist;
//等价于调用slist.push_front（"Hello!"）;
s1ist.insert(slist.begin(),"Hello!");
// vector 不支持push front，但我们可以插入到 begin（）之前
//警告∶插入到vector末尾之外的任何位置都可能很慢
svec.insert(svec.begin(),"Hello!");

2. 插入范围元素

a. 其中一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化∶

svec.insert(svec.end(),10,"Anna");
//这行代码将10个元素插入到svec的末尾，并将所有元素都初始化为string"Anna"。

b. 接受一对迭代器或一个初始化列表的 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一对迭代器，它们不能指向添加元素的目标容器。
3. 返回值
在新标准下，接受元素个数或范围的insert 版本返回指向第一个新加入元素的迭代器。（在旧版本的标准库中，这些操作返回void。）如果范围为空，不插入任何元素，insert 操作会将第一个参数返回。

vector<int> v1={1,2,3,4,5,6};
    vector<int> v2={7,8,9};
    auto it=v1.begin();
    it++;
    auto it2=v1.insert(it,{7,8,9});
    cout<<*it2<<endl;
    for(int i=0;i<v1.size();i++)
    {
        cout<<v1[i]<<endl;
    }
//输出
7//返回第一个插入的元素的迭代器
1
7
8
9
2
3
4
5
6

(4) emplace操作

1. 与push，insert的不同处
   push，insert是将对象传递给他们，这些对象被拷贝到容器中，会去创建一个局部临时对象，并将其压入容器中
   emplace是将参数传递给元素类型的构造函数，emplace成员使用这些参数在容器管理的内存空间直接构造元素
2. emplace接收的是容器内元素的构造函数的参数
3. emplace_back的使用，front类似

/ 在c的末尾构造一个Sales data对象
// 使用三个参数的 Sale3_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));

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

1.3.2 元素访问