9 顺序容器

9 顺序容器

目录0. 容器概述1. 顺序容器概述2. 容器库概览：对所有容器都适用的操作2.1 迭代器2.2 容器类型成员2.3 begin和end成员2.4 容器定义和初始化2.5 赋值和swap2.6 容器大小操作2.7 关系运算符3. 顺序容器（特有）操作：存储、访问、添加以及删除相关3.1 向顺序容器添加元素：push_back、push_front、insert与emplace_back、emplace_front、emplace3.2 访问元素：front、back、下标和at（访问元素前确保容器非空）3.3 删除元素（除array）：pop_back、pop_front、erase、clear。删除元素前，程序员必须确保目标元素存在3.4 特殊的forward_list操作：insert_after、emplace_after和erase_after作用元素后——对应其他容器的insert、emplace和erase作用元素前3.5 改变容器大小（除array外）：resize——增加或缩小容器3.6 容器操作可能使迭代器失效4. vector对象是如何增长的5. 额外的string操作（除了顺序容器的共同操作外，string的特有）5.1 构造string的其他方法5.2 子字符串substr操作5.3 改变string的其他方法5.4 string搜索操作：6个不同的搜索函数，每个函数都有4个重载版本正向搜索（从左至右搜索）逆向搜索（从右至左搜索）5.5 compare函数（string的比较：关系运算符或compare）5.6 数值转换（int <=> string）6. 容器适配器6.1 定义一个适配器6.2 栈适配器stack6.3 队列适配器queue6.4 优先权队列适配器priority_queue

0. 容器概述

1. 顺序容器概述

2. 容器库概览：对所有容器都适用的操作

// 顺序容器几乎可以保存任意类型的元素list //保存Sales_data对象的listdequevector> lines; //vector的vector// 此处lines是一个vector，其元素类型是string的vector

2.1 迭代器

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

2.2 容器类型成员

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

2.3 begin和end成员

list a = {"Milton", "Shakespeare", "Austen"};auto it1 = a.begin(); // list::iteratorauto it2 = a.rbegin(); // list::reverse_iteratorauto it3 = a.cbegin(); // list::const_iteratorauto it4 = a.crbegin(); // list::const_reverse_iterator

以 c 开头的版本是C++新标准引入的，用以支持 auto 与 begin 和 end 函数结合使用。

// 显式指定类型list::iterator it5 = a.begin();list::const_iterator it6 = a.begin();// 是iterator还是const_iterator依赖于a的类型auto it7 = a.begin(); //仅当a是const时，it7是const_iteratorauto it8 = a.cbigin(); //it8是const_iterator

当 auto 与 begin 或 end 结合使用时，返回的迭代器类型依赖于容器类型。但调用以 c 开头的版本仍然可以获得 const 迭代器，与容器是否是常量无关。当程序不需要"写"访问时，应该使用 cbegin 和 cend。

// 例题：下面4个对象分别是什么类型？vector v1; //v1非常量const vector v2; //v2常量auto it1 = v1.begin(), it2 = v2.begin();auto it3 = v1.cbegin(), it4 = v2.cbegin();/*（1）v1 是 int 的 vector 类型，我们可以修改 v1 的内容，包括添加、删除元素及修改元素值等操作。（2）v2 是 int 的常量 vector 类型，其内容不能修改，添加、删除元素及修改元素值等均不允许。（3）begin 与 auto 结合使用时，会根据调用对象的类型来决定迭代器的类型，因此 it1 是普通迭代器，可对容器元素进行读写访问，而 it2 是 const 迭代器，不能对容器元素进行写访问。（4）而 cbegin 则不管调用对象是什么类型，始终返回 const 迭代器，因此 it3 和 it4 都是 const 迭代器*/

2.4 容器定义和初始化

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

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元余类型都必须相同。C++11允许对容器进行列表初始化。

// 每个容器有三个元素，用给定的初始化器进行初始化list authors = {"Milton", "Shakespeare", "Austen"};vector articles = {"a", "an", "the"};

只有顺序容器的构造函数才接受大小参数，关联容器并不支持。容器初始化方法总结（1）将一个容器初始化为另一个容器的拷贝，两种：1）直接拷贝整个容器：两个容器的容器类型和元素类型都必须相同。2）(array 除外)传递迭代器参数来拷贝一个范围：不要求容器类型相同，而且新容器和原容器中的元素类型也可以不同，但是要能进行类型转换。

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

（2）列表初始化C++11允许对容器进行列表初始化：显式地指定了容器中每个元素的值；对于除了array之外的容器类型，还隐含地指定容器的大小：容器将包含与初始值一样多的元素

// 每个容器有三个元素，用给定的初始化器进行初始化list authors = {"Milton", "Shakespeare", "Austen"};vector articles = {"a", "an", "the"};

（3）与顺序容器大小相关的构造函数（array除外）只有顺序容器的构造函数才接受大小参数，关联容器并不支持。接受一个容器大小和一个（可选的）元素初始值（没有则标准库会创建一个值初始化器P88）如果元素类型是内置类型或者是具有默认构造函数的类类型：可以只提供容器大小参数如果元素类型没有默认构造函数：除了大小参数，必须指定一个显式的元素初始值

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

（4）具有固定大小的标准库array初始化：与内置数组类似定义和使用 array 类型时，需要同时指定元素类型和容器大小：array<元素类型，容器大小>2）对 array 进行列表初始化时，初始值的数量不能大于 array 的大小。如果初始值的数量小于 array 的大小，则只初始化靠前的元素，剩余元素会被值初始化。如果元素类型是类类型，则该类需要一个默认构造函数。3）可以对 array 进行拷贝或赋值操作，但要求二者的元素类型和大小都相同。

// 1）array // 类型为：保存42个int的数组array // 类型为：保存10个string的数组array::size_type i; // 数组类型包括元素类型和大小array::size_type j; // 错误：array不是一个类型// 2）array ia1; array ia2 = {0,1,2,3,4,5,6,7,8,9}; array ia3 = {42}; // ia3[0]为42，剩余元素为0// 3）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; //正确

2.5 赋值和swap

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

（2）使用assign（仅顺序容器——array除外）1）版本1：assign(迭代器1, 迭代器2)赋值运算符两侧的运算对象必须类型相同。assign 允许用不同但相容的类型赋值，或者用容器的子序列赋值。由于其旧元素被替换，因此传递给 assign 的迭代器不能指向调用 assign 的容器本身。

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

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

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

（3）使用swap——交换两个相同类型容器的内容元素本身并未移动，swap只是交换了两个容器的内部数据结构除 array 外，swap 不对任何元素进行拷贝、删除或插入操作，只交换两个容器的内部数据结构，因此可以保证快速完成。元素不会被移动的事实意味着，对于其他容器类型（除string外），指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是，在swap之后，这些元素已经属于不同的容器了。例如下面的例子中，假定iter在swap之前指向svec1[3]的string，那么在swap之后它指向svec2[3]的元素。两个例外：与其他容器不同，对一个string调用swap会导致迭代器、引用和指针失效。对于 array，swap 会真正交换它们的元素。因此在 swap 操作后，指针、引用和迭代器所绑定的元素不变，但元素值已经被交换（即元素值已经与另一个array中对应元素的值进行了互换）——交换两个array所需的时间与array中元素的数目成正比。

vector svec1(10); // 10个元素的vectorvector svec2(24); // 24个元素的vectorswap(svec1, svec2);

新标准库同时提供了成员和非成员函数版本的 swap。非成员版本的 swap 在泛型编程中非常重要，建议统一使用非成员版本的 swap。

2.6 容器大小操作

size 成员返回容器中元素的数量；empty 当 size 为0时返回 true，否则返回 false；max_size 返回一个大于或等于该类型容器所能容纳的最大元素数量的值。forward_list 支持 max_size 和 empty，但不支持 size。

2.7 关系运算符

每个容器类型都支持相等运算符（==、!=）。除无序关联容器外，其他容器都支持关系运算符（>、>=、<、<=）。关系运算符两侧的容器类型和保存元素类型都必须相同。如vector只能与vector比较，不能与list、vector作比较两个容器的比较实际上是元素的逐对比较，其工作方式与string的关系运算符类似：如果两个容器大小相同且所有元素对应相等，则这两个容器相等。如果两个容器大小不同，但较小容器中的每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。如果两个容器都不是对方的前缀子序列，则两个容器的比较结果取决于第一个不等元素的比较结果。

vector v1 = { 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；v1和v2在元素[2]处不同：v1[2]小于等于v2[2]v1 < v3 // false；所有元素都相等，但v3中元素数目更少v1 == v4 // true；每个元素都相等，且v1和v4大小相同v1 == v2 // false；v2元素数目比v1少

容器的相等运算符实际上是使用元素的 == 运算符实现的，而其他关系运算符则是使用元素的 < 运算符。如果元素类型不支持所需运算符，则保存该元素的容器就不能使用相应的关系运算。

3. 顺序容器（特有）操作：存储、访问、添加以及删除相关

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

3.1 向顺序容器添加元素：push_back、push_front、insert与emplace_back、emplace_front、emplace

// 从标准输入读取数据，将每个单词放到容器末尾string word;while (cin >> word) container.push_back(word);/*对push_back的调用在container尾部创建了一个新的元素，将container的size增大了1。该元素的值为word的一个拷贝，container的类型可以是list、vector或deque。*/

关键概念：容器元素是拷贝当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。2）使用push_front：顺序容器头部插入单个元素除了push_back, list、forward_list和deque容器还支持名为push_front的类似操作。此操作将元素插入到容器头部：注意：deque像vector一样提供了随机访问元素的能力，但它提供了vector所不支持的push_front。deque保证在容器首部进行插入和删除元素的操作都只花费常数时间。与vector一样，在deque首尾之外的位置插入元素会很耗时。

list ilist;//将元素添加到Ilist开头for(size_t ix=0;ix!=4;++ix) ilist.push_front(ix);/*此循环将元素0、1、2、3添加到ilist头部。每个元素都插入到list的新的开始位置。即，当我们插入1时，它会被放置在0之前，2被放置在1之前，依次类推。因此，在循环中以这种方式将元素添加到容器中，最终会形成逆序*/

3）使用insert：在容器中的特定位置添加元素——将n个元素插入到迭代器所指定的位置之前第一个参数都为目标容器的一个迭代器p迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置。由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以insert函数将元素插入到迭代器所指定的位置之前。

//（a）c.insert(p,t) 指定元素slist.insert(iter,"Hello!"); //将hello添加到iter之前的位置//（b）c.insert(p,n,t)　指定元素的数量和初始值svec.insert(svec.end(),10,"Anna"); //将10个元素插入到svec的末尾，并将所有元素都初始化为string“Anna”//（c）c.insert(p,b,e)　接受一对迭代器（不能指向添加元素的目标容器）vector v={"quasi","simba","frollo","scar"};//将v的最后两个元素添加到slist的开始位置slist.insert(slist.begin(),v.end()-2,v.end());//运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器 slist.insert(slist.begin(),slist.begin(),slist.end()) //（d）c.insert(p,il) 接受一个初始化列表slist.insert(slist.end(),{"these","words","will","go","at","the","end"});

vector、deque、list和string都支持insert成员。forward_list提供了特殊版本的insert成员一些不支持 push_front 的容器可以使用 insert 将元素插入开始位置将元素插入到 vector、deque 或 string 的任何位置都是合法的，但可能会很耗时

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

4）使用insert的返回值：返回指向第一个新增元素的迭代器；若范围为空，则返回p（可以在容器中一个特定位置反复插入元素）在新标准库中，接受元素个数或范围的 insert 版本返回指向第一个新增元素的迭代器，而旧版本中这些操作返回 void。如果范围为空，不插入任何元素，insert 会返回第一个参数p。

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

（2）构造元素方式添加（特别是容器存储类实例时）：调用 emplace 操作使用emplace操作。新标准库增加了三个直接构造而不是拷贝元素的操作：1）emplace_front——对应push_front2）emplace_back——对应push_back3）emplace——对应insert当调用 push或insert 时，元素对象被拷贝到容器中。而调用 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_backc.push_back(Sales_data(("978-0590353403",25,15.99));

区别：其中对emplace_back的调用和第二个push_back调用都会创建新的Sales_data对象。在调用emplace_back时，会在容器管理的内存空间中直接创建对象。而调用push_back则会创建一个局部临时对象，并将其压入容器中emplace 函数在容器中直接构造元素。传递给 emplace 函数的参数必须与元素类型的构造函数相匹配：元素类型的构造函数可能是多个，根据参数的不同选择不同的函数

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

forward_list 有特殊版本的 insert 和 emplace 操作，且不支持 push_back 和 emplace_back。vector 和 string不支持 push_front 和 emplace_front。

3.2 访问元素：front、back、下标和at（访问元素前确保容器非空）

- **在容器中访问元素的成员函数（即，front、back、下标和at）都返回引用类型**。 - 如果容器是 const 对象，则返回值是 const 引用。 - 如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的。```C++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中的元素}

注意：如果我们使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型下标操作[]和安全的随机访问at可以快速随机访问的容器（string、vector、deque 和 array）都提供下标运算符。保证下标有效是程序员的责任。下标运算符接受一个下标参数，返回容器中该位置的元素的引用如果希望确保下标合法，可以使用 at 成员函数。at 类似下标运算，但如果下标越界，at 会抛出 out_of_range 异常

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

3.3 删除元素（除array）：pop_back、pop_front、erase、clear。删除元素前，程序员必须确保目标元素存在

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

（2）erase 函数删除指定位置的元素。1）可以删除由一个迭代器指定的单个元素2）也可以删除**由一对迭代器指定的范围[…)内&&的所有元素。为了删除一个容器中的所有元素，我们既可以调用clear，也可以用begin和end获得的迭代器作为参数调用erase两种形式的 erase 都返回指向（最后一个）删除元素之后位置的迭代器。即，若j是i之后的元素，那么erase(i)将返回指向j的迭代器

// 1)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;}// 每个循环步中，首先检查当前元素是否是奇数，// 如果是，就删除该元素，并将it设置为我们所删除的元素之后的元素。// 如果*it为偶数，我们将it递增，从而在下一步循环检查下一个元素。// 2）// 删除两个迭代器表示的范围内的元素// 返回指向最后一个被删元素之后位置的迭代器elem1 = slist.erase(elem1, elem2); // 调用后，elem1 == e1em2

（3）clear 函数删除容器内的所有元素。

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

3.4 特殊的forward_list操作：insert_after、emplace_after和erase_after作用元素后——对应其他容器的insert、emplace和erase作用元素前

forward_list flst={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; }}/*此例中，curr表示我们要处理的元素，prev表示curr的前驱。调用begin来初始化curr，这样第一步循环就会检查第一个元素是否是奇数。我们用before_begin来初始化prev，它返回指向curr之前不存在的元素的迭代器。当找到奇数元素后，我们将prev传递给erase_after，此调用将prev之后的元素删除，即，删除curr指向的元素。然后我们将curr置为erase_after的返回值，使得curr指向序列中下一个元素，prev保持不变，仍指向（新）curr之前的元素。如果curr指向的元素不是奇数，在else中我们将两个迭代器都向前移动。*/

3.5 改变容器大小（除array外）：resize——增加或缩小容器

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

resize 函数接受一个可选的元素值参数，用来初始化添加到容器中的元素，如果调用者未提供此参数，新元素进行值初始化。如果容器保存的是类类型元素，且 resize 向容器添加新元素，则必须提供初始值，或元素类型提供默认构造函数。

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

向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重的程序设计错误。向容器中添加元素后：如果容器是 vector 或 string 类型:如果存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效。如果容器是 deque 类型：添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效。如果容器是 list 或 forward_list 类型：指向容器的迭代器、指针和引用仍然有效。从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效。当我们删除一个元素后：如果容器是 list 或 forward_list 类型：指向容器其他位置的迭代器、指针和引用仍然有效。如果容器是 deque 类型：删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响。如果容器是 vector 或 string 类型：指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。使用失效的迭代器、指针或引用是严重的运行时错误。编写改变容器的循环程序添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用和指针。如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：

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

建议：管理迭代器当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的方法。由于向迭代器添加元素和从迭代器删除元素的代码可能会使选代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对 vector、string 和 deque 尤为重要。注意：不要保存end返回的迭代器当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，用来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，然后一直当作容器末尾使用如果在一个循环中插入/删除 deque、string 或 vector 中的元素，不要缓存 end 返回的迭代器，更安全的方法：

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

4. vector对象是如何增长的

// （1）空vector上添加：vector ivec;// 空vector的size为0；capacity的值依赖于具体的实现cout << "ivec: size: " << ivec.size() << "capacity: " << ivec.capacity() << endl;// 向ivec添加24个元素for (vector::size_type ix=0; 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:0ivec: size: 24 capacity:32*/// （2）（重新）预分配一些额外空间：// 使用reverse按照我们的需求大小分配新的空间ivec.reserve(50); // 将capacity至少设定为50，可能会更大// size应该为24；capacity应该大于等于50，具体值依赖于标准库实现cout << "ivec: size: " << ivec.size() << "capacity: " << ivec.capacity() << endl;/*输出：ivec: size: 24 capacity:50*/// （3）用光这些预留空间：//添加元素用光多余容量while (ivec.size != ivec.capacity())ivec.push_back(0);cout << "ivec: size: " << ivec.size() << "capacity: " << ivec.capacity() << endl;/*输出：ivec: size: 50 capacity:50*///（4）只要需求大小没有超出vector的容量，vector就不能重新分配内存空间。// 如果我们现在再添加一个新元素，vector就不得不重新分配内存空间：// size应该为51；capacity应该大于等于51，具体值依赖于标准库实现cout << "ivec: size: " << ivec.size() << "capacity: " << ivec.capacity() << endl;/*输出：ivec: size: 51 capacity:100*/// 这表明vector的实现采用的策略似乎是在每次需要分配内存空间时将当前容量翻倍//（5）可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回给系统ivec.shrink_to_fit(); //要求归还内存// size应该未改变；capacity具体值依赖于标准库实现cout << "ivec: size: " << ivec.size() << "capacity: " << ivec.capacity() << endl;// 调用shrink_to_fit只是一个请求，标准库并不保证退还内存

只有在执行insert操作时size与capacity相等，或者调用resize或reserve时给定的大小超过当前capacity，vector才可能重新分配内存空间。额外分配多少空间取决于具体实现只有当需要的内存空间超过当前容量时，reserve 才会真正改变容器容量，分配不小于需求大小的内存空间。如果需求大小 > 当前容量，reserve至少分配与要求一样大的内存空间（可能更大）。如果需求大小 ≤ 当前容量，reserve什么也不做。特别是当需求大小 < 当前容量时，reserve 并不会退回内存空间。因此在调用 reserve 之后，capacity 会大于或等于传递给 reserve 的参数。在C++11中可以使用 shrink_to_fit 函数来要求 deque、vector 和 string 退回不需要的内存空间（并不保证退回）。每个 vector 实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：只有当迫不得已时才可以分配新的内存空间

5. 额外的string操作（除了顺序容器的共同操作外，string的特有）

string大小写敏感额外操作中的大部分要么是提供string类和C风格字符数组之间的相互转换，要么是增加了允许我们用下标代替迭代器的版本

5.1 构造string的其他方法

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

5.2 子字符串substr操作

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

如果传递给 substr 函数的开始位置超过 string 的大小，则函数会抛出 out_of_range 异常。如果开始位置加上计数值大于string的大小，则substr会调整计数值，只拷贝到string的末尾。

5.3 改变string的其他方法

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

（3）接受C风格字符数组的insert和assign版本

// 例如，我们可以将以空字符结尾的字符数组insert到或assign给一个string：const char *cp="Stately,plump Buck"; // 赋予s的是从cp指向的地址开始的7个字符。要求赋值的字符数必须小于或等于cp指向的数组中的字符数（不包括结尾的空字符）s.assign(cp,7); //s="Stately" // 将字符插入到s[size()]处（不存在的）元素之前的位置，并将cp开始的7个字符（至多到结尾空字符之前）拷贝到s中。s.insert(s.size(),cp+7); //s=="Stately,plump Buck" // 也可以指定将来自其它string或字符串的字符插入到当前string中或赋予当前string：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());

（4）string类定义了两个额外的成员函数：append和replace，这两个函数可以改变string的内容1）append 函数是在 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 Ed."追加到s2; s == s2

2）replace 函数是调用 erase 和 insert 函数的简写形式。

// 将"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// 上面调用replace时，插入的文本恰好与删除的文本一样长。这不是必须的，可以插入一个更长或更短的string：s.replace(11,3,"Fifth"); //删除了3个字符，但在其位置插入了5个新字符。

5.4 string搜索操作：6个不同的搜索函数，每个函数都有4个重载版本

正向搜索（从左至右搜索）

（1）完成最简单的搜索。它查找参数指定的字符串，若找到，则返回第一个匹配位置的下标，否则返回npos：

string name("AnnaBelle");auto pos1=name.find("Anna"); //pos1==0，即子字符串"Anna"在"AnnaBelle"中第一次出现的下标

（2）查找与给定字符串中任何一个字符匹配的位置：s.find_first_of(args)　常见场景：args表示所有可能出现情况（如所有可能数字"123456789"），然后在字符串中查找第一次出现args中任意一种情形的位置（如查找s中第一个数值出现的位置）

// 例如，下面代码定位name中的第一个数字：string numbers("0123456789"),name("r2d2");//返回1，即，name中第一个数字的下标auto pos=name.find_first_of(numbers);//调用了find_first_of来获得name中第一个可能是数值的字符的位置

（3）如果是要搜索第一个不在参数中的字符，我们应该调用find_first_not_of

例如，为了搜索一个string中第一个非数字字符，可以这样做：string dept("03714p3");//返回5，字符'p'的下标auto pos=dept.find_first_not_of(numbers);

-（4）指定开始搜索位置pos- 我们可以传递给find操作一个可选的开始位置。这个可选的参数指出从哪个位置开始搜索。默认情况下，此位置被置为0。一种常见的程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置：

string::size_type pos=0;//每步循环查找name中下一个数 while((pos=name.find_first_of(numbers,pos))!=string::npos){ cout<<"found number at index:"<

逆向搜索（从右至左搜索）

（1）rfind成员函数：搜索最后一个匹配，即子字符串最靠右的出现位置：

string river("Mississippi"); auto first_pos=river.find("is");  //返回1 auto last_pos=river.rfind("is");  //返回4 // find返回下标1，表示第一个"is"的位置，而rfind返回下标4.表示最后一个"is"的位置。

（2）find_last函数：功能与find_first函数相似，只是它们返回最后一个而不是第一个匹配：find_last_of搜索与给定string中任何一个字符匹配的最后一个字符find_last_not_of搜索最后一个不出现在给定string中的字符每个操作都接受一个可选的第二参数，可用来指出从什么位置开始搜索

5.5 compare函数（string的比较：关系运算符或compare）

5.6 数值转换（int <=> string）

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

string转换为数值的条件：string中第一非空白符必须是数值中可能出现的字符：

string s2="pi=3.14"; //转换s中以数字开始的第一个子串，结果d=3.14 d=stod(s2.substr(s2.find_first_of("+-.0123456789)));//调用了find_first_of来获得s2中第一个可能是数值的一部分的字符的位置

进行数值转换时，string 参数的第一个非空白字符必须是符号（+ 或 -）或数字。它可以以 0x 或 0X 开头来表示十六进制数。对于转换目标是浮点值的函数，string 参数也可以以小数点开头，并可以包含 e 或 E 来表示指数部分。如果给定的 string 不能转换为一个数值，则转换函数会抛出 invalid_argument 异常。如果转换得到的数值无法用任何类型表示，则抛出 out_of_range 异常。

6. 容器适配器

6.1 定义一个适配器

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

// 假定deq是一个deque，我们可以用deq来初始化一个新的stackstack stk(deq); // 从deq拷贝元素到stk

默认情况下，stack 和 queue 是基于 deque 实现的，priority_queue 是基于 vector 实现的。可以在创建适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

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

但每个容器适配器只可以使用自己的适配器操作，而不能使用底层容器类型的操作。对于一个给定的适配器，可以使用哪些容器是有限制的所有适配器都要求容器具有添加和删除元素的能力，因此适配器不能构造在 array 上。适配器还要求容器具有添加、删除和访问尾元素的能力，因此也不能用 forward_list 构造适配器。stack 只要求 push_back、pop_back 和 back 操作，因此可以使用除 array 和 forward_list 之外的任何容器类型来构造。queue 要求 back、push_back、front、push_front，因此它可以构建在 list 和 deque 之上，但不能基于 vector 构造。priority_queue 除了 front、push_back、pop_back 操作之外还要求随机访问能力，因此可以构造于vector 或 queue 之上，但不能基于 list 构造。每个容器适配器都基于底层容器类型的操作定义自己的特殊操作，使用时只可以使用适配器操作，而不能使用底层容器类型的操作。

intStack.push(ix);    /*此语句试图在intStack的底层deque对象上调用push_back。虽然stack是基于deque实现的，但我们不能直接使用deque操作。不能在一个stack上调用push_back，而必须使用stack自己的操作：push*/

6.2 栈适配器stack

stack intStack; //空栈：定义了一个保存整型元素的栈intStack，初始时为空//填满栈for (size_t ix = 0; ix != 10; ++ix) intStack.push(ix); //intStack保存0到9十个数 while (!intStack.empty()) //intStack中有值就循环直至栈空{ int value = intStack-(); //使用栈顶值 intStack.pop(); //弹出栈顶元素}

6.3 队列适配器queue

6.4 优先权队列适配器priority_queue

priority_queue 允许我们为队列中的元素建立优先级。新加入的元素会安排在所有优先级比它低的已有元素之前。优先队列例子：饭店按照客人预订时间而不是到来时间来为他们安排座位。默认情况下，标准库在元素类型上使用 < 运算符来确定相对优先级。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。