C++ Primer记录

文章目录

第九章 顺序容器

9.1 顺序容器概述9.2 容器库概览

9.2.1 迭代器9.2.2 容器类型成员9.2.3 begin和end成员9.2.4 容器定义和初始化9.2.5 赋值和swap9.2.6 容器大小操作9.2.7 关系运算符 9.3 顺序容器操作

9.3.1 向顺序容器添加元素9.3.2 访问元素9.3.3 删除元素9.3.4 特殊的forward_list操作9.3.5 改变容器大小9.3.6 容器操作可能使迭代器失效 9.4 vector对象是如何增长的9.5 额外的string操作

9.5.1 构造string的其他方法9.5.2 改变string的其他方法9.5.3 string搜索操作9.5.4 compare函数9.5.5 数值转换 9.6 容器适配器

第九章 顺序容器

一个容器就是一些特定类型对象的集合。顺序容器为程序员提供了控制元素存储和访问顺序的能力。 9.1 顺序容器概述

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

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

如何挑选容器：

通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。如果程序要求随机访问元素，应使用vector或deque。如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque。如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素:

首先，确定是否真的需要在容器中间位置添加元素，当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。 9.2 容器库概览

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

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

list //保存Sales_data对象的list
deque    //保存double的deque

可以定义一个容器，其元素的类型是另一个容器。

vector> lines; // vector的vector

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

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

容器操作

操作	注释
类型别名
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
difference_type	带符号整数类型，足够保存两个迭代器之间的距离
value_type	元素类型
reference	元素的左值类型；与value_type&含义相同
构造函数
C c;	默认构造函数，构造空容器
C cl(c2);	构造c2的拷贝cl
C c(b, e);	构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持）
C c{a, b, c …};	列表初始化c
赋值与swap
c1 = c2	将c1中的元素替换为c2中元素
cl = {a, b, c …)	将c1中的元素替换为列表中元素（不适用于array）
a.swap(b)	交换a和b的元素
swap(a, b)	与a.swap(b)等价
大小
c.size()	c中元素的数目(不支持forward_list)
c.max_size()	c可保存的最大元素数目
c.empty()	若c中存储了元素，返回false，否则返回true
添加／删除元素（不适用于array）	注意：在不同容器中，接口不相同
c.insert(args)	将args中的元素拷贝进c
c.emplace(inits)	使用inits构造c中的一个元素
c.erase(args)	删除args指定的元素
c.clear()	删除c中的所有元素，返回void
关系运算符
==, !=	所有容器都支持相等（不等）运算符
<, <=, >, >=	关系运算符（无序关联容器不支待）
获取迭代器
c.begin(), c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend()	返回constiterator
反向容器的额外成员（不支持forwardlist）
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(), c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()	返回const_reverse_iterator

9.2.1 迭代器

与容器一样，迭代器有着公共的接口：如果个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置。迭代器范围中的元素包含first表示的元素以及从first开始直至last（但不包含last）之间的所有元素。这种元素范围被称为左闭合区间，[begin, end)。使用左闭合范围蕴含的编程假定有三种方便的性质：

如果begin与end相同，则范围为空。如果begin与end不相同，则范围至少包含一个元素，且begin指向该范围中的第一个元素。我们可以对begin递增若干此，使得begin==end。 可以使用循环来处理一个元素范围。

while (begin != end)
{
    *begin = val; //正确：范围非空，因此begin指向一个元素
    ++begin;      //移动迭代器，获取下一个元素
}

9.2.2 容器类型成员

除了已经使用过的迭代器类型，大多数容器还提供反向迭代器，剩下的就是类型别名了。

// iter是通过list定义的一个迭代器类型
list::iterator iter;
// count是通过vector定义的一个difference_type类型
vector::difference_type count;

9.2.3 begin和end成员

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

list a = {"Milton", "Shakespeare", "Austen"};
auto itl = a.begin();   // list::iterator
auto it2 = a.rbegin();  // list::reverse_iterator
auto it3 = a.cbegin();  // list::const_iterator
auto it4 = a.crbegin(); // list::const_reverse_iterator
//显式指定类型
list::iterator it5 = a.begin();
list::const_iterator it6 = a.begin();
//是iterator还是const_iterator依赖于a的类型
auto it7 = a.begin();  //仅当a是const时，it7是const_iterator
auto it8 = a.cbegin(); // it8是const_iterator

9.2.4 容器定义和初始化

每个容器类型都定义了一个默认构造函数（除array之外）。

容器定义和初始化	解释
C c	默认构造函数。如果C是一个array,则c中元素按默认方式初始化，否则c为空
C c1(c2)	cl和c2必须是相同类型（它们必须是相同的容器类型，且保存的是相同的元素类型。对于array类型，两者还必须具有相同大小
C c1=c2	同上
C c{a,b,c …}	c初始化为初始化列表中元素的拷贝，列表中元素的类型必须与c的元素类型相同
C c={a,b, c …}	同上
C c(b,e)	c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与C的元素类型相容（array不适用）
	只有顺序容器（不包括array）的构造函数才能接受大小参数
C seq(n)	seq包含n个元素，这些元素进行了值初始化，此构造函数是explicit的
C seq(n,t)	seq包含n个初始化为值t的元素

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型必须相同。当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。只要能将拷贝的元素转换。

//每个容器有三个元素，用给定的初始化器进行初始化
list authors = {"Milton", "Shakespeare", "Aussten"};
Vebtor articles = {"a", "an", "the"};
list list2(authors);     //正确：类型匹配
deque authList(authors); //错误：容器类型不匹配
vector words(articles);  //错误：容器类型必须匹配
//正确：可以将const char*元素转换为string
forward_list words(articles.begin(), articles.end());
//拷贝元素，直到it（但不包括） 指向的元素
deque authList(authors.begin(), it); //假设迭代器it表示authors中的一个元素

除了与关联容器相同的构造函数外，顺序容器（除array除外）还提供一种构造函数，接受一个容器大小和一个元素初始值。因为只有顺序容器的构造函数才接受大小参数，关联容器并不支持。如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小的参数。如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显示的元素初始值。

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

标准库array具有固定大小。

array a;                                    //类型为：保存42个int的数组
array b;                                 //类型为：保存10个string的数组
array::size_type i;                         //数组类型包括元素类型和大小
array::size_type j;                             //错误：array不是一个类型
array ia1;                                  // 10个默认构造化的int
array ia2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //列表初始化
array ia3 = {42};                           // ia3[0]为42，剩余元素为0
int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int cpy[10] = digs; //错误：内置类型不支持拷贝和赋值
array digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array copy = digits; //正确：只要数组类型匹配即合法

9.2.5 赋值和swap

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

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

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

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

容器赋值运算	解释
c1=c2	将c1中的元素替换为c2中元素的拷贝，cl和c2必须具有相同的类型
c= {a, b, c … }	将c1中元素替换为初始化列表中元素的拷贝(array不适用）
swap(c1,c2)	交换c1和c2中的元素，c1和c2必须具有相同的类型，swap通常比从c2向c1拷贝元素快得多
c1.swap(c2)	同上
	assign操作不适用于关联容器和array
seq.assign(b, e)	将seq中的元素替换为迭代器b和e所表示的范围中的元素，迭代器b和e不能指向seq中的元素
seq.assign(il)	将seq中的元素替换为初始化列表il中的元素
seq.assign(n, t)	将seq中的元素替换为n个值为t的元素

如何使用assign（仅顺序容器）。

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

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

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

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

vector svecl(10); // 10个元素的vector
vector svec2(24); // 24个元素的vector
swap(svecl, svec2);

9.2.6 容器大小操作

每个容器类型都有三个与大小相关的操作。

成员函数size返回容器中元素的数目。empty当size为0时返回布尔值true，否则返同false。max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。

forward_list支持max_size和empty，但不支持size。 9.2.7 关系运算符

每个容器类型都支持相等运赁符（==和!=）。除了无序关联容器外的所有容器都支待关系运算符（>、>=、<、<=）。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。比较两个容器实际上是进行元素的逐对比较，这些运算符的工作方式与string的关系运算类似：

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

vector vl = {1, 3, 5, 7, 9, 12};
vector v2 = {1, 3, 9};
vector v3 = {1, 3, 5, 7};
vector v4 = {1, 3, 5, 7, 9, 12};
v1 < v2;  // true;vl和v2在元素[2]处不同，vl[2]小于等于v2[2]
v1 < v3;  // false;所有元素都相等，但v3中元素数组更少
v1 == v4; // true;每个元素都相等，且v1和v4大小相同
v1 == v2; // false;v2元素数目比v1少

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

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。 9.3.1 向顺序容器添加元素

除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)	在e的头部创建一个值为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

除array和forward_list之外，每个顺序容器（包括string类型）都支持push_back。

//从标准捡入读取数据，将每个单词放到容器末尾
string word;
while (cin >> word)
{
    container.push_back(word);//container的类型可以是list、vector或deque
}

void pluralize(size_t cnt, string &word)
{
    if (cnt > 1)
    {
        word.push_back('s'); //等价于word+='s'
    }
}

list、forward_list和deque容器支持名为push_front的类似操作。

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

insert成员提供了更一般的添加功能。

vector svec;
list slist;
//等价于调用slist.push_front("Hello!");
slist.insert(slist.begin(), "Hello!");

// vector不支持push_front，但我们可以插入到begin()之前
// 警告：插入到vector末尾之外的任何位置都可能很慢
svec.insert(svec.begin(), "Hello!");

insert函数还可以接受更多的参数，这与容器构造函数类似。

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

vector 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的返回值，可以在容器中一个特定位置反复插入元素。

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

新标准引入了三个新成员emplace_front、emplace和emplace_back，这些操作构造而不是拷贝元素。分别对应push_front、insert、push_back。调用一个emplace成员函数，则是将参数传递给元素类型的构造函数。

//假定c保存Sales_data元素
//在c的末尾构造一个Sales_data对象
//使用三个参数的Sales_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));

// 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);

9.3.2 访问元素

如果容器中没有元素，访问操作的结果是未定义的。

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

注意：

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，就像使用一个越界的下标一样，是一种严重的程序设计错误。在容器中访问元素的成员函数返回的都是引用，如果容器是一个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;             //未改变c中的元素
}

提供快速随机访问的容器(string、vector、deque和array)也都提供下标运算符。

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

9.3.3 删除元素

与添加元素的多种方式类似，（非array）容器也有多种删除元素的方式。注意：

这些操作会改变容器的大小，所以不适用于array。forward_list有特殊版本的erase。forward_list不支持pop_back。vector和string不支持pop_front。删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

顺序容器的删除操作	解释
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

pop_front和pop_back成员函数分别删除首元素和尾元素。

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

成员函数erase从容器中指定位置删除元素。

list 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;
    }
}

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

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

删除一个容器中的所有元素。

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

9.3.4 特殊的forward_list操作

在一个单向链表中，没有简单的方法来获取一个元素的前驱。在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。

在forward_list中插入或删除元素的操作	解释
lst.before_begin()	返回指向链表首元素之前不存在的元素的迭代器，此迭代器不能解引用
lst.cbefore_begin()	cbefore_begin()返回一个const_iterator
lst.insert_after(p,t)	在迭代器p之后的位置插入元素，t是一个对象，返回一个指向最后一个插入元素的迭代器，如果范围为空，则返回p，若p为尾后迭代器，则函数行为未定义
lst.insert_after(p,n,t)	在迭代器p之后的位置插入元素，t是一个对象，n是数量，同上
lst.insert_after(p, b, e)	在迭代器p之后的位置插入元素，b和e是表示范围的一对迭代器，同上
lst.insert_after(p, il)	在迭代器p之后的位置插入元素，il是一个花括号列表，同上
emplace_after(p,args)	使用args在p指定的位置之后创建一个元素，返回一个指向这个新元素的迭代器，若p为尾后迭代器，则函数行为未定义
lst.erase_after(p )	删除p指向的位置之后的元素，返回一个指向被删元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代器，如果p指向lst的尾元素或者是一个尾后迭代器，则函数行为未定义
lst.erase_after(b,e)	删除从b之后直到e之间的元素，同上

当forward_list在中添加或删除元素时，必须关注两个迭代器，一个是我们要处理的元素，另一个指向其前驱。

forward_list float = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto prev = flst.before_begin(); //表示flst的“首前元素”
auto curr = flst.begin();        //表示flst中的第一个元素
while (curr != flst.end())       //仍有元素要处理
{
    if (*curr % 2) //若元素为奇数
    {
        curr = flst.erase_after(prev); //删除它并移动curr
    }
    else
    {
        prev = curr; //移动迭代器curr，指向下一个元素，prev指向
        ++curr;      // curr之前的元素
    }
}

9.3.5 改变容器大小

用resize来增大或缩小容器（array不支持）。

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

顺序容器大小操作	解释
c.resize(n)	调整c的大小为n个元素，若n
c.resize(n,t)	调整c的大小为n个元素，任何新添加的元素都初始化为值t

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

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

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

对于list和forward_list,指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响，如果是删除首元素，这些也不会受影响。对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。 因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。

//傻瓜循环，删除偶数元素，复制每个奇数元素
vector vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto iter = vi.begin(); //调用begin而不是cbegin，因此我们要改变vi
while (iter != vi.end())
{
    if (*iter % 2)
    {
        iter = vi.insert(iter, *iter); //复制当前元素
        iter += 2;                     //向前移动迭代器，跳过当前元素以及插入它之前的元素
    }
    else
    {
        iter = vi.erase(iter); //删除偶数元素
        //不应向前移动迭代器，iter指向我们删除的元素之后的元素
    }
}

不要保存end返回的迭代器。

//灾难：此循环的行为是未定义的
auto begin = v.begin();
end = v.end(); //保存尾迭代器的值是一个坏主意
while (begin != end)
{
    //做一些处理
    //插入新值，对begin重新赋值，否则的话它就会失效
    ++begin;                     //向前移动begin，因此我们想在此元素之后插入元素
    begin = v.insert(begin, 42); //插入新值
    ++begin;                     //向前移动begin跳过我们刚刚加入的元素
}

必须在每次插入操作后重新调用end(),而不能在循环开始前保存它返回的迭代器。

//更安全的方法：在每个循环步添加/删除元素后都重新计算end
while (begin != v.end())
{
    //做一些处理
    ++begin;                     //向前移动begin，因为我们想在此元素之后插入元素
    begin = v.insert(begin, 42); //插入新值
    ++begin;                     //向前移动begin,跳过我们刚刚加入的元素
}

9.4 vector对象是如何增长的

为了支持快速随机访间，vector将元素连续存储。vector分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间，性能会慢。为了避免，vector和string的实现通常会分配比新的空间需求更大的内存空间。允许我们与它的实现中内存分配部分互动。注意：

shrink_to_fit只适用于vector、string和deque。capacity和reserve只适用于vector和string。

容器大小管理操作	解释
c.shrink_to_fit()	请将capacity()减少为与size()相同大小。
c.capacity()	不重新分配内存空间的话，c可以保存多少元素。
c.reserve(n)	分配至少能容纳n个元素的内存空间。

reserve并不改变容器中元素的数量，它仅影响vector预先分配多大的内存空间。只有当需要的内存空间超过当前容量时，reserve调用才会改变vector的容量。分配多少额外空间视标准库具体实现而定。

vector ivec;
// size应该为0；capacity的值依赖于具体实现
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;
//向ivec添加24个元素
for (vector::size_type ix = 0; ix != 24; ++ix)
{
    ivec.push_back(ix);
}
// size应该为24，capacity应该大于等于24，具体值依赖于标准库实现
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

ivec: size: 0 capacity: 0
ivec: size: 24 capacity: 32

可以预分配一些额外空间。

ivec.reserve(50); //将capacity至少设定为50，可能会更大
// size应该为24；capacity应该大于等于50，具体值依赖于标准库实现
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

ivec: size: 24 capacity: 50

用光预留空间。

//添加元素用光多余容量
while (ivec.size() != ivec.capacity())
{
    ivec.push_back(0);
}
// capacity应该未改变size和capacity不相等
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

ivec: size: 50 capacity: 50

再添加一个新元素。

ivec.push_back(42);
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

ivec: size: 50 capacity: 100

将超出当前大小的多余内存退回给系统。

ivec.shrink_to_fit(); //要求归还内存
//size应该未改变；capacity的值依赖于具体实现
cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

注意：标准库并不保证退还内存。 9.5 额外的string操作

除了顺序容器共同的操作之外，string类型还提供了一些额外的操作。 9.5.1 构造string的其他方法

string类型还支持另外三个构造函数。注意：n，len2和pos2都是无符号值。

构造string的其他方法	解释
string s(cp, n)	s是cp指向的数组中前n个字符的拷贝，此数组至少应该包含n个字符
string s(s2, pos2)	s是s2从下标pos2开始的字符的拷贝，若pos2>s2.size()，构造函数的行为未定义。
string s(s2, pos2, len2)	s是s2从下标pos2开始len2个字符的拷贝。若pos2>s2.size()，构造函数的行为未定义。不管len2的值是多少，构造函数至多拷贝s2.size()-pos2个字符。

const char *cp = "Hello World!!!"; //以空字符结束的数组
char noNull[] = {'H', 'i'};        //不是以空字符结束
string s1(cp);                     //拷贝cp中的字符直到遇到空字符
string s2(noNull, 2);              //从noNull拷贝两个字符；s2 == "Hi"
string s3(noNull);                 //未定义：noNull不是以空字符结束
string s4(cp + 6, 5);              //从cp[6]开始拷贝5个字符；s4 == "World"
string s5(sl, 6, 5);               //从s1[6]开始拷贝5个字符；s5 == "World"
string s6(sl, 6);                  //从s1[6]开始拷贝，直至s1末尾；s6 =="World'!!"
string s7(sl, 6, 20);              //正确，只拷贝到s1末尾；s7 == "World!!!"
string s8(sl, 16);                 //抛出一个out_of_range异常

substr操作返回一个string，它是原始string的一部分或全部的拷贝。

子字符串操作	解释
s.substr(pos, n)	返回一个string，包含s中从pos开始的n个字符的拷贝。pos的默认值为0。n的默认值为s.size()-pos，即拷贝从pos开始的所有字符。

string s("hello world");
string s2 = s.substr(0, 5);  // s2=hello
string s3 = s.substr(6);     // s3=world
string s4 = s.substr(6, 11); // s3=world
string s5 = s.substr(12);    //抛出一个out_of_range异常

9.5.2 改变string的其他方法

string类型支持顺序容器的赋值运算符以及assign、insert和erase操作，还定义了额外的insert和erase版本。

修改string的操作	解释
s.insert(pos,args)	在pos之前插入args指定的字符，pos可以是一个下标或一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器。
s.erase(pos,len)	删除从位置pos开始的len个字符，如果len被省略，则删除到末尾，返回一个指向s的引用。
s.assign(args)	将s中的字符替换为args指定的字符，返回一个指向s的引用。
s.append(args)	将args追加到s，返回一个指向s的引用。
s.replace(range,args)	删除s中范围range内的字符，替换为args指定的字符，range可以是一个下标和一个长度，或是一对指向s的迭代器，返回一个指向s的引用。

额外的insert和erase版本。

s.insert(s.size(), 5, '!'); //在s末尾插入5个感叹号
s.erase(s.size() - 5, 5);   //从s删除最后5个字符

const char *cp = "Stately, plump Buck";
s.assign(cp, 7);            // s == "Stately"
s.insert(s.size(), cp + 7); // s == "Stately, plump Buck"

string s = "some string", s2 = "some other string";
s.insert(0, s2); //在s中位置0之前插入s2的拷贝
//在s[0]之前插入s2中s2[0]开始的s2.size()个字符
s.insert(0, s2, 0, s2.size());

String类定义了两个额外的成员函数：append和replace，这两个函数可以改变string的内容。

string s("C++ Primer"), s2 = s; //将s和s2初始化为"C++ Primer"
s.insert(s.size(), " 4th Ed."); // s=="C++ Primer 4th Ed."
s2.append(" 4th Ed.");          //等价方法
//将"4th"替换为"5th"的等价方法
s.erase(11, 3);      // s=="C++ Primer Ed."
s.insert(11, "5th"); // s=="C++ Primer 5th Ed."
//从位置11开始，删除3个字符并插入"5th"
s2.replace(11, 3, "5th"); //等价方法：s==s2

s.replace(ll, 3, "Fifth"); // s=="C++ Primer Fifth Ed."

9.5.3 string搜索操作

string类提供了6个不同的搜索函数，每个函数都有4个重载版本。

string 搜索操作	解释
s.find(args)	查找s中args第一次出现的位置。
s.rfind(args)	查找s中args最后一次出现的位置。
s.find_first_of(args)	在s中查找args中任何一个字符第一次出现的位置。
s.find_last_of(args)	在s中查找args中任何一个字符最后一次出现的位置。
s.find_first_not_of(args)	在s中查找第一个不在args中的字符。
s.find_last_not_of(args)	在s中查找最后一个不在args中的字符。
args必须是以下形式之一
c,pos	从s中位置pos开始查找字符c。pos默认为0。
s2,pos	从s中位置pos开始查找字符串s2。pos默认为0。
cp,pos	从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认为0。
cp,pos,n	从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值。

指定在哪里开始搜索。

string::size_type pos = 0;
//每步循环查找name中下一个数
while ((pos = name.find_first_of(numbers, pos)) != string::npos)
{
    cout << "found number at index: " << pos << " element is " << name[pos] << endl;
    ++pos; //移动到下一个字符
}

逆向搜索

string river("Mississippi");
auto first_pos = river.find("is"); //返回 1
auto last_pos = river.rfind("is"); //返回 4

9.5.4 compare函数

除了关系运算符外，标准库string类型还提供了一组compare函数。s.compare(args)的参数形式。

s.compare的几种参数形式	解释
s2	比较s和s2。
pos1, n1, s2	将s中从pos1开始的n1个字符与s2进行比较。
pos1, n1, s2, pos2, n2	将s中从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较。
cp	比较s与cp指向的以空字符结尾的字符数组。
pos1, n1, cp	将s中从pos1开始的n1个字符与cp指向的以空字符结尾1的字符数组进行比较。
pos1, n1, cp, n2	将s中从pos1开始的n1个字符与指针cp指向的地址开始的n2个字符进行比较。

9.5.5 数值转换

新标准引入了多个函数，可以实现数值数据与标准库string之间的转换。注意：

返回s的起始子串的数值。表示转换所用的基数，默认值为10。p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0。

string和数值之间的转换	解释
to_string(val)	一组重载函数，返回数值val的string表示
stoi(s, p, b)	返回值类型是int
stol(s, p, b)	返回值类型是long
stoul(s, p, b)	返回值类型是unsigned long
stoll(s, p, b)	返回值类型是long long
stoull(s, p, b)	返回值类型是unsigned long long
stof(s, p)	返回值类型是float
stod(s, p)	返回值类型是double
stold(s, p)	返回值类型是long double

int i = 42;
string s = to_string(i); //将整数i转换为字符表示形式
double d = stod(s);      //将字符串s转换为浮点数

string s2 = "pi=3.14";
//转换s中以数宇开始的第一个子串，结果d= 3.14
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));

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

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue和priority_queue。适配器是标准库中的一个通用概念。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种串事物一样。

所有容器适配器都支持的操作和类型	解释
size_type	一种类型，足以保存当前类型的最大对象的大小
value_type	元素类型
container_type	实现适配器的底层容器类型
A a	创建一个名为a的空适配器
A a(c )	创建一个名为a的适配器，带有容器c的一个拷贝。
关系运算符	每个适配器都支待所有关系运算符：==、!=、<、<=、>和>=这些运算符返回底层容器的比较结果
a.empty()	若a包含任何元素，返回false，否则返回true
a.size()	返回a中的元素数目
swap(a,b)	交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同
a.swap(b)	同上

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

deque deq;
stack stk(deq); //从deq拷贝元素到stk

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。queue也可以用list或vector实现，priority_queue也可以用deque实现。

//在vector上实现的空栈
stack> str_stk;
// str_stk2在vector上实现，初始化时保存svec的拷贝
stack> str_stk2(svec);

栈适配器。stack类型定义在stack头文件中。

未列出的栈操作	解释
s.pop()	删除栈顶元素，但不返回该元素值
s.push(item)	创建一个新元素压入栈顶，该元素通过拷贝或移动item而来
s.emplace(args）	创建一个新元素压入栈顶，该元素通过args构造而来
s.top()	返回栈顶元素，但不将元素弹出栈

stack intStack; //空栈
//填满栈
for (size_t ix = 0; ix != 10; ++ix)
{
    intStack.push(ix); // intStack保存0到9十个数
}
while (!intStack.empty()) // intStack中有值就继续循环
{
    int value = intStack.top();
    //使用栈顶值的代码
    intStack.pop(); //弹出栈顶元素，继续循环
}

队列适配器。queue和priority_queue适配器定义在queue头文件中。

未列出的queue和priority_queue操作	解释
q.pop()	返回queue的首元素或priority_queue的最高优先级的元素，但不删除此元素。
q.front()	返回首元素或尾元素，但不删除此元素。
q.back()	只适用于queue。
q.top()	返回最高优先级元素，但不删除该元素。
q.push(item)	在queue末尾或priority_queue中恰当的位置创建一个元素，其值为item。
q.emplace(args)	在queue末尾或priority_queue中恰当的位置创建一个元素，由args构造。