在虚拟机做网站平台搭建大概多少钱

当前位置： 首页 > news >正文

在虚拟机做网站,平台搭建大概多少钱,建e网模型官网,展芒设计网页CSTL标准手册#xff1a; https://cplusplus.com/reference/stl/ https://cplusplus.com/reference/vector/vector/at/ 1、STL基础 1.1、STL基本组成(6大组件13个头文件) 通常认为#xff0c;STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成… CSTL标准手册 https://cplusplus.com/reference/stl/ https://cplusplus.com/reference/vector/vector/at/ 1、STL基础 1.1、STL基本组成(6大组件13个头文件) 通常认为STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成其中后面 4 部分是为前 2 部分服务的它们各自的含义如表 1 所示。 表 1 STL 组成结构 STL的组成含义容器一些封装数据结构的模板类例如 vector 向量容器、list 列表容器等。算法STL 提供了非常多大约 100 个的数据结构算法它们都被设计成一个个的模板函数这些算法在 std 命名空间中定义其中大部分算法都包含在头文件 algorithm 中少部分位于头文件 numeric 中。迭代器在 C STL 中对容器中数据的读和写是通过迭代器完成的扮演着容器和算法之间的胶合剂。函数对象如果一个类将 () 运算符重载为成员函数这个类就称为函数对象类这个类的对象就是函数对象又称仿函数。适配器可以使一个类的接口模板的参数适配成用户指定的形式从而让原本不能在一起工作的两个类工作在一起。值得一提的是容器、迭代器和函数都有适配器。内存分配器为容器类模板提供自定义的内存申请和释放功能由于往往只有高级用户才有改变内存分配策略的需求因此内存分配器对于一般用户来说并不常用。 另外在惠普实验室最初发行的版本中STL 被组织成 48 个头文件但在 C 标准中它们被重新组织为 13 个头文件如表 2 所示。 表 2 C STL头文件 iteratorfunctionalvectordequelistqueuestacksetmapalgorithmnumericmemoryutility 按照 C 标准库的规定所有标准头文件都不再有扩展名。以 vector 为例此为无扩展名的形式而 vector.h 为有扩展名的形式。 但是或许是为了向下兼容或许是为了内部组织规划某些 STL 版本同时存储具备扩展名和无扩展名的两份文件例如 Visual C 支持的 Dinkumware 版本同时具备 vector.h 和 vector甚至有些 STL 版本同时拥有 3 种形式的头文件例如 SGI 版本同时拥有 vector、vector.h 和 stl_vector.h但也有个别的 STL 版本只存在包含扩展名的头文件例如 C Builder 的 RaugeWare 版本只有 vector.h。 建议读者养成良好的习惯遵照 C 规范使用无扩展名的头文件(即使用vector)。 1.2、容器 简单的理解容器它就是一些模板类的集合但和普通模板类不同的是容器中封装的是组织数据的方法(也就是数据结构)。 STL 提供有 3 类标准容器分别是序列容器、排序容器和哈希容器其中后两类容器有时也统称为关联容器。它们各自的含义如表 1 所示。   容器种类功能序列容器主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器是因为元素在容器中的位置同元素的值无关即容器不是排序的。将元素插入容器时指定在什么位置元素就会位于什么位置。排序容器包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的即便是插入元素元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。哈希容器C 11 新加入 4 种关联式容器分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同哈希容器中的元素是未排序的元素的位置由哈希函数确定。 注意由于哈希容器直到 C 11 才被正式纳入 C 标准程序库而在此之前“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本不过该版本只能在某些支持 C 11 的编译器下使用如 VS有些编译器如 gcc/g是不支持的。 另外以上 3 类容器的存储方式完全不同因此使用不同容器完成相同操作的效率也大不相同。所以在实际使用时要善于根据想实现的功能选择合适的容器。有关这些容器的具体用法本章后续会逐个进行介绍。 1.3、 迭代器是什么CSTL迭代器(iterator) 注 不想记的话这些类型可以直接用auto代替 1.3.1、 迭代器是什么 无论是序列容器还是关联容器最常做的操作无疑是遍历容器中存储的元素而实现此操作多数情况会选用“迭代器iterator”来实现。那么迭代器到底是什么呢 我们知道尽管不同容器的内部结构各异但它们本质上都是用来存储大量数据的换句话说都是一串能存储多个数据的存储单元。因此诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。 既然类似完全可以利用泛型技术将它们设计成适用所有容器的通用算法从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置它除了要具有对容器进行遍历读写数据的能力之外还要能对外隐藏容器的内部差异从而以统一的界面向算法传送数据。这就是迭代器了。 这是泛型思维发展的必然结果于是迭代器就产生了。简单来讲迭代器和 C 的指针非常类似它可以是需要的任意类型通过迭代器可以指向容器中的某个元素如果需要还可以对该元素进行读/写操作。 1.3.2、迭代器类别 STL标准库为每一种标准容器定义了一种迭代器类型。这意味着不同容器的迭代器也不同。

1. 前向迭代器forward iterator 假设 p 是一个前向迭代器则 p 支持 pp*p 操作还可以被复制或赋值可以用 和 ! 运算符进行比较。此外两个正向迭代器可以互相赋值。
2. 双向迭代器bidirectional iterator 双向迭代器具有正向迭代器的全部功能除此之外假设 p 是一个双向迭代器则还可以进行 –p 或者 p– 操作即一次向后移动一个位置。 双向迭代器不支持、比较     双向迭代器不支持用下标随机访问元素; 3) 随机访问迭代器random access iterator 随机访问迭代器具有双向迭代器的全部功能。除此之外假设 p 是一个随机访问迭代器i 是一个整型变量或常量则 p 还支持以下操作     pi使得 p 往后移动 i 个元素。     p-i使得 p 往前移动 i 个元素。     pi返回 p 后面第 i 个元素的迭代器。     p-i返回 p 前面第 i 个元素的迭代器。     p[i]返回 p 后面第 i 个元素的引用。 此外两个随机访问迭代器 p1、p2 还可以用 、、、 运算符进行比较。另外表达式 p2-p1 也是有定义的其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差也可以说是 p2 和 p1 之间的元素个数减一。   表 1 所示是 C 11 标准中不同容器指定使用的迭代器类型。   表 1 不同容器的迭代器 容器对应的迭代器类型array随机访问迭代器vector随机访问迭代器deque随机访问迭代器list双向迭代器set / multiset双向迭代器map / multimap双向迭代器forward_list前向迭代器unordered_map / unordered_multimap前向迭代器unordered_set / unordered_multiset前向迭代器stack不支持迭代器queue不支持迭代器 1.3.3、迭代器的定义方式 尽管不同容器对应着不同类别的迭代器但这些迭代器有着较为统一的定义方式具体分为 4 种如表 1 所示。 表 2 迭代器的 4 种定义方式 迭代器定义方式具体格式正向迭代器容器类名::iterator  迭代器名;常量正向迭代器容器类名::const_iterator  迭代器名;反向迭代器容器类名::reverse_iterator  迭代器名;常量反向迭代器容器类名::const_reverse_iterator  迭代器名; 通过定义以上几张迭代器就可以读取它指向的元素 *迭代器名 就表示迭代器指向的元素。其中常量迭代器和非常量迭代器的分别在于通过非常量迭代器还能修改其指向的元素。另外反向迭代器和正向迭代器的区别在于 对正向迭代器进行 操作时迭代器会指向容器中的后一个元素 而对反向迭代器进行 操作时迭代器会指向容器中的前一个元素。 注意以上 4 种定义迭代器的方式并不是每个容器都适用。有一部分容器同时支持以上 4 种方式比如 array、deque、vector而有些容器只支持其中部分的定义方式例如 forward_list 容器只支持定义正向迭代器不支持定义反向迭代器。   #include vector #include iostreamusing namespace std;int main() {vectorint vec1{1,2,3,4,5,6,7,8,9,10};//size的方式遍历for (int i 0; i vec1.size(); i){cout vec1[i] ;}cout endl;//创建一个正向迭代器vectorint::iterator i;//用 ! 比较两个迭代器for (ivec1.begin(); i ! vec1.end(); i){ cout *i ;}cout endl;//用 比较两个迭代器for (ivec1.begin(); i vec1.end(); i ){ cout *i ;}cout endl;//迭代器支持 整数 操作i vec1.begin();while(i vec1.end()){cout *i ;i 2; //间隔输出}cout endl; } 在举个例子 //创建一个 v list容器 listint v; //创建一个常量正向迭代器同样list也支持其他三种定义迭代器的方式。 listint::const_iterator i;#以下代码是合法的 for(i v.begin(); i ! v.end(); i)cout *i;#以下代码不合法 因为双向迭代器不支持用“”进行比较 for(i v.begin(); i v.end(); i)cout *i;#以下代码也不合法因为双向迭代器不支持用下标随机访问元素 for(int i0; iv.size(); i)cout v[i]; 2、 string 不属于STL,但是此处也整理出来便于后续查阅。 3、 STL序列式容器 3.0、什么是序列式容器 STL标准库中的序列式容器包括 array、vector、deque、list 和 foward_list 容器。所谓STL序列式容器即以线性排列(类似数组的存储方式)来存储某一指定类型的数据显然它不会对存储的元素进行排序元素排列的顺序只取决于存储时放置他们的顺序。 arrayT,N数组容器表示可以存储 N 个 T 类型的元素是 C 本身提供的一种容器。此类容器一旦建立其长度就是固定不变的这意味着不能增加或删除元素只能改变某个元素的值vectorT向量容器用来存放 T 类型的元素是一个长度可变的序列容器即在存储空间不足时会自动申请更多的内存。使用此容器在尾部增加或删除元素的效率最高时间复杂度为 O(1) 常数阶在其它位置插入或删除元素效率较差时间复杂度为 O(n) 线性阶其中 n 为容器中元素的个数dequeT双端队列容器和 vector 非常相似区别在于使用该容器不仅尾部插入和删除元素高效在头部插入或删除元素也同样高效时间复杂度都是 O(1) 常数阶但是在容器中某一位置处插入或删除元素时间复杂度为 O(n) 线性阶listT链表容器是一个长度可变的、由 T 类型元素组成的序列它以双向链表的形式组织元素在这个序列的任何地方都可以高效地增加或删除元素时间复杂度都为常数阶 O(1)但访问容器中任意元素的速度要比前三种容器慢这是因为 listT 必须从第一个元素或最后一个元素开始访问需要沿着链表移动直到到达想要的元素。forward_listT正向链表容器和 list 容器非常类似只不过它以单链表的形式组织元素它内部的元素只能从第一个元素开始访问是一类比链表容器快、更节省内存的容器。 如下图所示的操作都可以快速执行 3.1、array array容器是C11标准中新增的序列式容器。简单理解就是在C普通数据的基础上添加了一些成员函数和全局函数。在使用上比普通数据更安全些且效率没有因此变差。 #include array 表 1 array容器成员函数汇总 成员函数功能begin()返回指向容器中第一个元素的随机访问迭代器。end()返回指向容器最后一个元素之后一个位置的随机访问迭代器通常和 begin() 结合使用。rbegin()返回指向最后一个元素的随机访问迭代器。rend()返回指向第一个元素之前一个位置的随机访问迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。size()返回容器中当前元素的数量其值始终等于初始化 array 类的第二个模板参数 N。max_size()返回容器可容纳元素的最大数量其值始终等于初始化 array 类的第二个模板参数 N。empty()判断容器是否为空和通过 size()0 的判断条件功能相同但其效率可能更快。at(n)返回容器中 n 位置处元素的引用该函数自动检查 n 是否在有效的范围内如果不是则抛出 out_of_range 异常。front()返回容器中第一个元素的直接引用该函数不适用于空的 array 容器。back()返回容器中最后一个元素的直接应用该函数同样不适用于空的 array 容器。data()返回一个指向容器首个元素的指针。利用该指针可实现复制容器中所有元素等类似功能。fill(val)将 val 这个值赋值给容器中的每个元素。array1.swap(array2)交换 array1 和 array2 容器中的所有元素但前提是它们具有相同的长度和类型。 正是由于 array 容器中包含了 at() 这样的成员函数使得操作元素时比普通数组更安全。 array使用方式如下 #include iostream #include arrayusing namespace std;int main() {arrayint, 6 values{};//初始化value容器为{0,1,2,3,4,5}for (int i0; i values.size(); i){values.at(i) i;}//使用get() 重载函数输出指定位置的元素cout get3(values) endl;//使用迭代器输出容器所有元素if (!values.empty()){for (auto i values.begin(); i ! values.end(); i){cout *i ;}cout endl;} }3.2、 vector #includevector 3.2.1、向量容器简介 vector 容器是 STL 中最常用的容器之一它和 array 容器非常类似都可以看做是对 C 普通数组的“升级版”。不同之处在于array 实现的是静态数组容量固定的数组而 vector 实现的是一个动态数组即可以进行元素的插入和删除在此过程中vector 会动态调整所占用的内存空间整个过程无需人工干预。 vector 常被称为向量容器因为该容器擅长在尾部插入或删除元素在常量时间内就可以完成时间复杂度为O(1)而对于在容器头部或者中部插入或删除元素则花费时间要长一些移动元素需要耗费时间时间复杂度为线性阶O(n)。 需要注意的是如果调用 reserve() 来增加容器容量之前创建好的任何迭代器例如开始迭代器和结束迭代器都可能会失效这是因为为了增加容器的容量vectorT 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时最好重新生成一下。 3.2.2、vector容器的初始化 #创建一个存储double类型元素的vector容器 vectordouble values;#创建vector容器创建时指定初始值 vectorint num {1,2,3,4,5,6,7};#创建vector容器时指定元素个数;此时容器开始就有20个元素默认初始值都是0 vectorint values(20);#如果不想用0作为默认值,也可以指定其他(此处指定20个元素的值都是1.0) vectordouble value(20, 1.0);#上述圆括号的2个参数既可以是常量也可以用变量表示例如: int num 20; double value 1.0; vectordouble values(num, value);//注意圆括号 () 和大括号 {} 是有区别的前者例如 (20) 表示元素的个数而后者例如 {20} 则表示 vector 容器中只有一个元素 20。#也可以通过其他vector容器创建新的vector容器例如: std::vectorcharvalue1(5, c); std::vectorcharvalue2(value1);#如果不想赋值其他容器的所有元素也可以用迭代器或指针来指定范围 int array[] {1, 2, 3}; std::vectorintvalues(array, array2); //values将保存{1, 2} std::vectorintvalue1{1,2,3,4,5}; std::vectorintvalue2(std::begin(value1),std::begin(value1)3 ); //values将保存{1, 2, 3} 3.2.3、vector容器的成员函数 https://cplusplus.com/reference/vector/vector/ 相比 array 容器vector 提供了更多了成员函数供我们使用它们各自的功能如表 1 所示。   表 1 vector 容器的成员函数 函数成员函数功能begin()返回指向容器中第一个元素的迭代器。end()返回指向容器最后一个元素所在位置后一个位置的迭代器通常和 begin() 结合使用。rbegin()返回指向最后一个元素的迭代器。rend()返回指向第一个元素所在位置前一个位置的迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。size()返回实际元素个数。max_size()返回元素个数的最大值。这通常是一个很大的值一般是 232-1所以我们很少会用到这个函数。resize()改变实际元素的个数。capacity()返回当前容量。empty()判断容器中是否有元素若无元素则返回 true反之返回 false。reserve()增加容器的容量。shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。operator[ ]重载了 [ ] 运算符可以向访问数组中元素那样通过下标即可访问甚至修改 vector 容器中的元素。at()使用经过边界检查的索引访问元素。front()返回第一个元素的引用。back()返回最后一个元素的引用。data()返回指向容器中第一个元素的指针。assign()用新元素替换原有内容。push_back()在序列的尾部添加一个元素。pop_back()移出序列尾部的元素。insert()在指定的位置插入一个或多个元素。erase()移出一个元素或一段元素。clear()移出所有的元素容器大小变为 0。swap()交换两个容器的所有元素。emplace()在指定的位置直接生成一个元素。emplace_back()在序列尾部生成一个元素。 push_back 与 emplace_backemplace_back更快(减少一次构造、一次析构)。 底层实现机制不同。push_back()首先创建这个元素然后将元素拷贝或者移动到容器中(拷贝时自行销毁先前创建的元素); emplace_back直接在容器尾部创建元素省掉拷贝或移动的过程。 #对于push_back:vectorstring testVec; testVec.push_back(string(16, a));底层实现 首先string(16, ‘a’)会创建一个string类型的临时对象这涉及到一次string构造过程。 其次vector内会创建一个新的string对象这是第二次构造。 最后在push_back结束时最开始的临时对象会被析构。#对于emplace_backvectorstirng testVec; testVec.emplace_back(string(16, a));emplace_back可以直接在vector中构建一个对象而非创建一个临时对象再放进vector再销毁。 emplace_back可以省略一次构建和一次析构从而达到优化的目的。 除此之外C 11 标准库还新增加了 begin() 和 end() 这 2 个函数和 vector 容器包含的 begin() 和 end() 成员函数不同标准库提供的这 2 个函数的操作对象既可以是容器还可以是普通数组。当操作对象是容器时它和容器包含的 begin() 和 end() 成员函数的功能完全相同如果操作对象是普通数组则 begin() 函数返回的是指向数组第一个元素的指针同样 end() 返回指向数组中最后一个元素之后一个位置的指针注意不是最后一个元素。 vector 容器还有一个 std::swap(x , y) 非成员函数其中 x 和 y 是存储相同类型元素的  vector 容器它和 swap() 成员函数的功能完全相同仅使用语法上有差异。 #include iostream #include vectorusing namespace std;int main() {vectorchar value;value.emplace_back(S);value.emplace_back(T);value.emplace_back(L);cout value.size() value.size() endl;//使用迭代器遍历cout 循环输出: ;for (vectorchar::iterator iter value.begin(); iter ! value.end(); iter){cout *iter ;}cout endl;//向容器开头插入字符value.insert(value.begin(), C);cout value首个元素为: value.at(0) endl;//第二个位置插入字符Pvalue.insert(value.begin()1, P);cout 向第2个位置插入P endl;//第三个位置插入字符Pvalue.insert(value.begin()1, P);cout 向第3个位置插入P endl;//范围for语句输出(需要修改就加引用)cout 范围for语句输出: ;for (auto elem: value){cout elem ;}cout endl;//范围for语句中如果需要修改数据其中数据一定要用引用cout 范围for语句修改每个元素至A: ;for (auto elem: value){elem A;}for (auto elem: value){cout elem ;}cout endl;} 输出如下  value.size() 3 循环输出: S T L value首个元素为:C 向第2个位置插入P 向第3个位置插入P 范围for语句输出: C P P S T L 范围for语句修改每个元素至A: A A A A A A 3.2.4、容器迭代器用法 表 1 vector 支持迭代器的成员函数 成员函数功能begin()返回指向容器中第一个元素的正向迭代器如果是 const 类型容器在该函数返回的是常量正向迭代器。end()返回指向容器最后一个元素之后一个位置的正向迭代器如果是 const 类型容器在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。rbegin()返回指向最后一个元素的反向迭代器如果是 const 类型容器在该函数返回的是常量反向迭代器。rend()返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。cbegin()和 begin() 功能类似只不过其返回的迭代器类型为常量正向迭代器不能用于修改元素。cend()和 end() 功能相同只不过其返回的迭代器类型为常量正向迭代器不能用于修改元素。crbegin()和 rbegin() 功能相同只不过其返回的迭代器类型为常量反向迭代器不能用于修改元素。crend()和 rend() 功能相同只不过其返回的迭代器类型为常量反向迭代器不能用于修改元素。 迭代器的用法 #include iostream #include vectorusing namespace std;int main() {vectorint values{1,2,3,4,5};//使用成员函数begin/end获取容器迭代器/auto first values.begin();auto end values.end();///也可以使用全局的begin/end从容器中获取迭代器auto first std::begin(values);auto end std::end(values);while(first ! end){*first 10; //可以修改数据cout *first ;first ;}cout endl; }常量迭代器不可以用于修改容器中的元素 #include iostream #include vectorusing namespace std;int main() {vectorint values{1,2,3,4,5};//常量迭代器不可修改元素auto first values.cbegin();auto end values.cend();while(first ! end){// *first 10; //常量迭代器不可修改数据cout *first ;first ;}cout endl; }3.2.5、容器迭代器注意事项 1初始化容器时不能使用迭代器 记住一件事情先有容器然后才有的迭代器。 在容器为空的情况下尝试通过迭代器给容器填充元素是不可行的。 2vector容器扩容时之前的迭代器可能会失效 vector 容器在申请更多内存的同时容器中的所有元素可能会被复制或移动到新的内存地址这会导致之前创建的迭代器失效。切记不能用老迭代器。 #include iostream #include vectorusing namespace std;int main() {vectorint values{1,2,3};cout value容器首个元素地址: values.data() endl;auto beg std::begin(values);auto end std::end(values);cout values.size() values.size() endl;values.reserve(20);cout values.size() values.size() endl;values.emplace_back(4);values.emplace_back(5);values.emplace_back(6);cout reserve后value容器首个元素地址: values.data() endl;cout 老迭代器输出数据: ;while(beg ! end){cout *beg ;beg;}cout endl;cout 容器实际数据: ;for (auto elem: values){cout elem ;}cout endl;cout 结论: reverse后地址会变;且迭代器也随时失效(就迭代能输出旧数据是因为就空间没有被利用而已)! endl; } 3.2.6、vector容器访问元素的几种方式 #include iostream #include vector #include exceptionusing namespace std;int main() {vectorint values{1,2,3,4,5,6,7,8,9};//方式一:通过下标访问。需要自己确保下标不超过容器的容量,否则会发生越界访问错误。cout 通过下标访问! endl;cout values[0]: values[0] values[1]: values[1] endl;//方式二:通过成员函数 at() 访问。注cout 通过at访问! endl;cout 首个元素: values.at(0) endl;//修改容器中下标为0的元素的值values.at(0) values.at(1) values.at(2) values.at(3) values.at(4);cout 修改后的首个元素: values.at(0) endl;//越界时候回自动抛 out_of_range 异常//cout 第15个元素: values.at(15) endl;//通过front和back访问vector的首末元素cout 首个元素: values.front() endl;cout 末尾元素: values.back() endl;//方式三: data()成员函数;返回指向容器中首个元素的指针,通过该指针也可访问/修改容器中的元素cout 容器中的第3个元素: (values.data()2) endl;//修改容器中的第二个元素(values.data()1) 222;cout 容器中的第2个元素: *(values.data()1) endl;//二、访问多个元素//方式1: 借助size()循环遍历for(int i 0; i values.size(); i){cout values[i] ;}cout endl;//方式2: 范围for语句for(auto elem: values){cout elem ;}cout endl;//方式3: 迭代器for (auto iter values.begin(); iter values.end(); iter){cout iter ;}cout endl;}3.2.7、vector容器添加元素emplace_back/push_back emplace_back() 和 push_back() 的区别就在于底层实现的机制不同。push_back() 向容器尾部添加元素时首先会创建这个元素然后再将这个元素拷贝或者移动到容器中如果是拷贝的话事后会自行销毁先前创建的这个元素而 emplace_back() 在实现时则是直接在容器尾部创建这个元素省去了拷贝或移动元素的过程。建议后续都是用emplace_back。 #include vector #include iostream using namespace std; class testDemo { public:testDemo(int num):num(num){std::cout 调用构造函数 endl;}testDemo(const testDemo other) :num(other.num) {std::cout 调用拷贝构造函数 endl;}testDemo(testDemo other) :num(other.num) {std::cout 调用移动构造函数 endl;} private:int num; };int main() {cout emplace_back: endl;std::vectortestDemo demo1;demo1.emplace_back(2); cout push_back: endl;std::vectortestDemo demo2;demo2.push_back(2); } 输出如下 emplace_back: 调用构造函数 push_back: 调用构造函数 调用移动构造函数 显然完成同样的操作push_back() 的底层实现过程比 emplace_back() 更繁琐换句话说emplace_back() 的执行效率比 push_back() 高。因此在实际使用时建议大家优先选用 emplace_back()。 3.2.8、vector容器插入元素insert/emplace vector容器提供了 insert() 和 emplace() 这 2 个成员函数用来实现在容器指定位置处插入元素本节将对它们的用法做详细的讲解。 1insert() 函数的功能是在 vector 容器的指定位置前插入一个或多个元素。该函数的语法格式有多种如表 1 所示。 表 1 insert() 成员函数语法格式 语法格式用法说明iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem并返回表示新插入元素位置的迭代器。iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前插入其他容器不仅限于vector中位于 [first,last) 区域的所有元素并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,initlist)在迭代器 pos 指定的位置之前插入初始化列表用大括号{}括起来的多个元素中间有逗号隔开中所有的元素并返回表示第一个新插入元素位置的迭代器。 2emplace也是在vector容器指定位置之前插入一个新元素。注意每次只能插一个。 #include iostream #include vector #include arrayusing namespace std;void print_vec(vectorint vec){for(auto elem: vec){cout elem ;}cout endl; }int main() {vectorint values{1,3,5,7};print_vec(values);//insert第一种用法values.insert(values.begin()1, 2); //{1,2,3,5,7}print_vec(values);//insert第二种用法values.insert(values.end(), 3, 8); //{1,2,3,5,7,8,8,8}print_vec(values);//insert第三种用法std::arrayint, 3 arr{9,10,11};values.insert(values.end(), arr.begin(), arr.end()); //{1,2,3,5,7,8,8,8,9,10,11}print_vec(values);//insert第四种用法values.insert(values.end(), {12, 13});print_vec(values);//看看emplace的用法values.emplace(values.begin(),0);print_vec(values); }输出如下 1 3 5 7 1 2 3 5 7 1 2 3 5 7 8 8 8 1 2 3 5 7 8 8 8 9 10 11 1 2 3 5 7 8 8 8 9 10 11 12 13 0 1 2 3 5 7 8 8 8 9 10 11 12 13
   简单的理解就是 emplace() 在插入元素时是在容器的指定位置直接构造元素而不是先单独生成再将其复制或移动到容器中。因此在实际使用中推荐大家优先使用 emplace()。 3.2.9、vector容器删除容器的几种方式 表 1 删除 vector 容器元素的几种方式 函数功能pop_back()删除 vector 容器中最后一个元素该容器的大小size会减 1但容量capacity不会发生改变。erase(pos)删除 vector 容器中 pos 迭代器指定位置处的元素并返回指向被删除元素下一个位置元素的迭代器。该容器的大小size会减 1但容量capacity不会发生改变。swap(beg)、pop_back()先调用 swap() 函数交换要删除的目标元素和容器最后一个元素的位置然后使用 pop_back() 删除该目标元素。erase(beg,end)删除 vector 容器中位于迭代器 [beg,end)指定区域内的所有元素并返回指向被删除区域下一个位置元素的迭代器。该容器的大小size会减小但容量capacity不会发生改变。remove()删除容器中所有和指定元素值相等的元素并返回指向最后一个元素下一个位置的迭代器。值得一提的是调用该函数不会改变容器的大小和容量。clear()删除 vector 容器中所有的元素使其变成空的 vector 容器。该函数会改变 vector 的大小变为 0但不是改变其容量。 #include iostream #include vector #include array #include algorithmusing namespace std;void print_vec(vectorint vec){for(auto elem: vec){cout elem ;}cout endl; }int main() {vectorint values{1,2,3,4,5,6,7,8,9};print_vec(values);//方式1: 删除最后一个元素values.pop_back();print_vec(values);//方式2: 删除小标为1的元素values.erase(values.begin()1); //删除元素2print_vec(values);//方式3: swap pop_back 删除元素(不介意元素相对位置调整)swap((values.begin()), *(values.end()));values.pop_back();print_vec(values);//方式4: erase删除指定范围的元素values.erase(values.begin(), values.begin()2); //删除最开始的2个元素print_vec(values);//方式6: clear清空容器所有元素values.clear();print_vec(values);}注其中的remove比较有意思单独拎出来说下。 remove删除容器中指定值的元素(如删除值为3的元素)。 #include vector #include iostream #include algorithmusing namespace std;void print_vec(vectorint vec){for(auto elem: vec){cout elem ;}cout endl; }int main() {vectorint values{1,3,3,4,3,5};//删除值为3的元素auto iter std::remove(values.begin(), values.end(), 3);cout size is : values.size() endl;cout capacity is : values.capacity() endl;//输出剩余元素for (auto first values.begin(); first iter; first){cout *first ;}cout endl;//输出所有元素print_vec(values);//标准玩法是结合erase,在remove的同时在删掉后续无用数据,如下://values.erase(std::remove(values.begin(), values.end(), 3), values.end());vectorint values1{1,3,3,4,3,5};values1.erase(std::remove(values1.begin(), values1.end(), 3), values1.end());print_vec(values1);}remove() 的实现原理是在遍历容器中的元素时一旦遇到目标元素就做上标记然后继续遍历直到找到一个非目标元素即用此元素将最先做标记的位置覆盖掉同时将此非目标元素所在的位置也做上标记等待找到新的非目标元素将其覆盖。因此如果将上面程序中 demo 容器的元素全部输出得到的结果为 1 4 5 4 3 5。 remove()用于删除容器中指定元素时常和 erase() 成员函数搭配使用。 3.2.10、注意 vectorbool不是存储bool类型元素的vector容器 vectorbool并不是一个STL容器不是一个STL容器不是一个STL容器 正常情况下我们使用bool类型他的长度应该是一个字节即等效于uint8_t。 虽然我们知道bool只需要一个bit来表示但由于硬件无法直接对bit进行寻址C语法中也不存在使用指针指向bit的玩法。重点来了vectorbool中每个元素的长度真的是1bit而不是1字节于是就导致了很多匪夷所思的问题。 首先vector bool 并不是一个通常意义上的vector容器这个源自于历史遗留问题。 早在C98的时候就有vector bool这个类型了但是因为当时为了考虑到节省空间的想法所以vector bool里面不是一个Byte一个Byte储存的它是一个bit一个bit储存的         因为C没有直接去给一个bit来操作所以用operator[]的时候正常容器返回的应该是一个对应元素的引用但是对于vector bool实际上访问的是一个proxy reference而不是一个true reference返回的是std::vector bool:reference类型的对象。 而一般情况情况下 #include vector #include iostream #include algorithmusing namespace std;int main() {vector c{ false, true, false, true, false };bool b c[0];auto d c[0];cout b: b endl;cout d: d endl;d true;for (auto i:c){cout i ;}cout endl;}#输出如下: b:0 d:0 1 1 0 1 0
   对于b的初始化它其实暗含了一个隐式的类型转换。 而对于d它的类型并不是bool而是一个vector bool中的一个内部类。 而此时如果修改d的值c中的值也会跟着修改。 而如果c被销毁d就会变成一个悬垂指针再对d操作就属于未定义行为。 之所以说vectorint不是一个标准容器就是因为它不支持容器该有的基本操作。 3.3、 deque(double-ended queue) 双端队列容器 deque是 double-ended queue的缩写又称“双端队列容器”。  #includedequeusing namespace std; 3.3.1、deque介绍 deque 容器和 vecotr 容器有很多相似之处比如 deque 容器也擅长在序列尾部添加或删除元素时间复杂度为O(1)而不擅长在序列中间添加或删除元素。deque 容器也可以根据需要修改自身的容量和大小。 和 vector 不同的是deque 还擅长在序列头部添加或删除元素所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。 当需要向序列两端频繁的添加或删除元素时应首选 deque 容器。 3.3.3、deque成员函数 基于 deque 双端队列的特点该容器包含一些 array、vector 容器都没有的成员函数。 表 1 中罗列了 deque 容器提供的所有成员函数。   表 1 deque 容器的成员函数 函数成员函数功能begin()返回指向容器中第一个元素的迭代器。end()返回指向容器最后一个元素所在位置后一个位置的迭代器通常和 begin() 结合使用。rbegin()返回指向最后一个元素的迭代器。rend()返回指向第一个元素所在位置前一个位置的迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。size()返回实际元素个数。max_size()返回容器所能容纳元素个数的最大值。这通常是一个很大的值一般是 232-1我们很少会用到这个函数。resize()改变实际元素的个数。empty()判断容器中是否有元素若无元素则返回 true反之返回 false。shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。at()使用经过边界检查的索引访问元素。front()返回第一个元素的引用。back()返回最后一个元素的引用。assign()用新元素替换原有内容。push_back()在序列的尾部添加一个元素。push_front()在序列的头部添加一个元素。pop_back()移除容器尾部的元素。pop_front()移除容器头部的元素。insert()在指定的位置插入一个或多个元素。erase()移除一个元素或一段元素。clear()移出所有的元素容器大小变为 0。swap()交换两个容器的所有元素。emplace()在指定的位置直接生成一个元素。emplace_front()在容器头部生成一个元素。和 push_front() 的区别是该函数直接在容器头部构造元素省去了复制移动元素的过程。emplace_back()在容器尾部生成一个元素。和 push_back() 的区别是该函数直接在容器尾部构造元素省去了复制移动元素的过程。 和 vector 相比额外增加了实现在容器头部添加和删除元素的成员函数同时删除了 capacity()、reserve() 和 data() 成员函数。 #include deque #include iostream #include stringusing namespace std;int main() {//1、deque的创建//1.1、创建没有任何元素的空deque容器std::dequeint d;//1.2、创建一个具有 n 个元素的 deque 容器其中每个元素都采用对应类型的默认值std::dequeint d1(10);//1.3、创建一个具有 n 个元素的 deque 容器并为每个元素都指定初始值例如std::dequeint d2(10, 5);//1.4、在已有 deque 容器的情况下可以通过拷贝该容器创建一个新的 deque 容器例如std::dequeint d3(d2);//2、插入数据d.push_back(1);//{1}d.push_back(2);//{1,2}d.push_back(3);//{1,2,3}d.push_front(0); //{0,1,2,3,4}cout d.size(): d.size() endl;for(auto i d.begin(); i d.end(); i){cout *i ;}cout endl; } 3.3.4、deque迭代器用法 和vector看起来一样。 表 1 deque 支持迭代器的成员函数 成员函数功能begin()返回指向容器中第一个元素的正向迭代器如果是 const 类型容器在该函数返回的是常量正向迭代器。end()返回指向容器最后一个元素之后一个位置的正向迭代器如果是 const 类型容器在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。rbegin()返回指向最后一个元素的反向迭代器如果是 const 类型容器在该函数返回的是常量反向迭代器。rend()返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。cbegin()和 begin() 功能类似只不过其返回的迭代器类型为常量正向迭代器不能用于修改元素。cend()和 end() 功能相同只不过其返回的迭代器类型为常量正向迭代器不能用于修改元素。crbegin()和 rbegin() 功能相同只不过其返回的迭代器类型为常量反向迭代器不能用于修改元素。crend()和 rend() 功能相同只不过其返回的迭代器类型为常量反向迭代器不能用于修改元素。 迭代器用于遍历或修改容器中的元素不能用于初始化空的deque容器。 3.3.5、deque访问元素 #include deque #include iostream #include stringusing namespace std;int main() {//1、deque的创建//1.1、创建没有任何元素的空deque容器std::dequeint d;//1.2、创建一个具有 n 个元素的 deque 容器其中每个元素都采用对应类型的默认值std::dequeint d1(10);//1.3、创建一个具有 n 个元素的 deque 容器并为每个元素都指定初始值例如std::dequeint d2(10, 5);//1.4、在已有 deque 容器的情况下可以通过拷贝该容器创建一个新的 deque 容器例如std::dequeint d3(d2);//2、插入数据d.push_back(1);//{1}d.push_back(2);//{1,2}d.push_back(3);//{1,2,3}d.push_front(0); //{0,1,2,3,4}cout d.size(): d.size() endl;for(auto i d.begin(); i d.end(); i){cout *i ;}cout endl;//3、deque访问元素//3.1、下标访问cout 第一个元素: d[0] endl;//3.2、at访问cout 第一个元素: d.at(0) endl;//3.3、front()/back()访问第一个和最后一个元素(同样可以修改第一个or最后一个元素)cout 第一个元素: d.front() endl;cout 最后个元素: d.back() endl;d.front() 10;d.back() 20;//3.4、迭代器访问auto beg d.begin() 2;auto end d.end();while(beg end){cout *beg ;beg;}cout endl; } 3.3.6、deque删除元素 deque 容器中无论是添加元素还是删除元素都只能借助 deque 模板类提供的成员函数。表 1 中罗列的是所有和添加或删除容器内元素相关的 deque 模板类中的成员函数。   表 1 和添加或删除deque容器中元素相关的成员函数 成员函数功能push_back()在容器现有元素的尾部添加一个元素和 emplace_back() 不同该函数添加新元素的过程是先构造元素然后再将该元素移动或复制到容器的尾部。pop_back()移除容器尾部的一个元素。push_front()在容器现有元素的头部添加一个元素和 emplace_back() 不同该函数添加新元素的过程是先构造元素然后再将该元素移动或复制到容器的头部。pop_front()移除容器尾部的一个元素。emplace_back()C 11 新添加的成员函数其功能是在容器尾部生成一个元素。和 push_back() 不同该函数直接在容器头部构造元素省去了复制或移动元素的过程。emplace_front()C 11 新添加的成员函数其功能是在容器头部生成一个元素。和 push_front() 不同该函数直接在容器头部构造元素省去了复制或移动元素的过程。insert()在指定的位置直接生成一个元素。和 emplace() 不同的是该函数添加新元素的过程是先构造元素然后再将该元素移动或复制到容器的指定位置。emplace()C 11 新添加的成员函数其功能是 insert() 相同即在指定的位置直接生成一个元素。和 insert() 不同的是emplace() 直接在容器指定位置构造元素省去了复制或移动元素的过程。erase()移除一个元素或某一区域内的多个元素。clear()删除容器中所有的元素。 在实际应用中常用 emplace()、emplace_front() 和 emplace_back() 分别代替 insert()、push_front() 和 push_back()原因和vector一样即前者更快。 上述成员函数中insert()函数的语法格式比较多、erase()有两种语法格式其他函数都只有一种用法。下面程序演示使用。 关于insert()函数的用法如下 表 2 insert() 成员函数语法格式 语法格式功能iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem并返回表示新插入元素位置的迭代器。iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前插入其他容器不仅限于vector中位于 [first,last) 区域的所有元素并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,initlist)在迭代器 pos 指定的位置之前插入初始化列表用大括号{}括起来的多个元素中间有逗号隔开中所有的元素并返回表示第一个新插入元素位置的迭代器。 #include deque #include iostream #include string #include arrayusing namespace std;int main() {dequeint d;//调用push_back()向容器尾部添加数据d.push_back(11); //{11}//调用pop_back()移除容器尾部的数据d.pop_back(); //{}//调用push_front()向容器头部添加数据d.push_front(22); //{22}//调用pop_front()移除容器头部的数据d.pop_front(); //{}//调用emplace_back/emplace_front函数向容器中直接生成数据d.emplace_back(33); //{33}d.emplace_front(11); //{11}//emplace()需要两个参数,第一个指定插入位置,第二个是插入的数值d.emplace(d.begin()1, 22); //{11, 22, 33}//for循环语句输出for(auto i:d){cout i ;}cout endl;//erase()可以接受一个迭代器表示要输出元素所在的位置//也可以接受2个迭代器,表示要删除元素所在的区域。d.erase(d.begin()); //{22, 33}d.erase(d.begin(), d.end()); //全部清空,等同于 clear()cout d.size(): d.size() endl;//下面演示 insert 的四种用法dequeint dq{1,3};//第一种格式用法dq.insert(dq.begin() 1, 2); //{1, 2, 3}//第二种格式用法(插入2个4)dq.insert(dq.end(), 2, 4); //{1,2,3,4,4}//第三种格式用法arrayint, 3test{6,7,8};dq.insert(dq.end(), test.begin(), test.end()); //{1,2,3,4,4,6,7,8}//第四种格式用法dq.insert(dq.end(),{9,10}); //{1,2,3,4,4,6,7,8,9,10}for (auto i : dq){cout i ;}cout endl; }3.4、 list(双向链表) #includelistusing namespace std; 3.4.1、list简介 STL list(双向链表容器)该容器的底层以双向链表的形式实现的。这意味着list容器中的元素可以分散存储在内存空间里而不是必须存储在已真快连续的内存空间中。 可以看到list容器中各个元素的前后顺序都是靠指针来维系的每个元素都配备了2个指针分别指向他的前一个元素和后一个元素。其中第一个元素的前向指针为null因为其前面没有元素同理尾部元素的后向指针也为null。 基于这样的存储结构list容器具有一些其他容器(array/vector/deque)所不具备的优势即他可以在序列一直的任何位置快速插入或删除元素(时间复杂度为O(1))。而且在list容器中移动元素也比其他容器的效率更高。 当然其缺点也很明显即它不能像array、vector那样通过位置下标直接访问元素。举例来说如果需要访问第6个元素只能通过容器的第一个元素开始往后遍历直到找到该位置。 实际场景中如何需要对序列进行大量添加或删除元素的操作而直接访问元素的需求却很少这种情况建议使用 list 容器存储序列。 3.4.2、list可用成员函数 表 2 中罗列出了 list 模板类提供的所有成员函数以及各自的功能。 其实官网上都有  list - C Reference 表 2 list 容器可用的成员函数 成员函数功能begin()返回指向容器中第一个元素的双向迭代器。end()返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。rbegin()返回指向最后一个元素的反向双向迭代器。rend()返回指向第一个元素所在位置前一个位置的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crbegin() 和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改元素。empty()判断容器中是否有元素若无元素则返回 true反之返回 false。size()返回当前容器实际包含的元素个数。max_size()返回容器所能包含元素个数的最大值。这通常是一个很大的值一般是 232-1所以我们很少会用到这个函数。front()返回第一个元素的引用。back()返回最后一个元素的引用。assign()用新元素替换容器中原有内容。emplace_front()在容器头部生成一个元素。该函数和 push_front() 的功能相同但效率更高。push_front()在容器头部插入一个元素。pop_front()删除容器头部的一个元素。emplace_back()在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同但效率更高。push_back()在容器尾部插入一个元素。pop_back()删除容器尾部的一个元素。emplace()在容器中的指定位置插入元素。该函数和 insert() 功能相同但效率更高。insert() 在容器中的指定位置插入元素。erase()删除容器中一个或某区域内的元素。swap()交换两个容器中的元素必须保证这两个容器中存储的元素类型是相同的。resize()调整容器的大小。clear()删除容器存储的所有元素。splice()将一个 list 容器中的元素插入到另一个容器的指定位置。remove(val)删除容器中所有等于 val 的元素。remove_if()删除容器中满足条件的元素。unique()删除容器中相邻的重复元素只保留一个。merge()合并两个事先已排好序的 list 容器并且合并之后的 list 容器依然是有序的。sort()通过更改容器中元素的位置将它们进行排序。reverse()反转容器中元素的顺序。 除此之外C11标准库提供的 begin() 和 end()两个函数也是可用的效果与成员函数begin()/end()等效。 #include list #include array #include iostreamusing namespace std;int main() {//1、通过一下5种方式创建list容器的方式//1.1、创建一个没有任何元素的空list容器//listint values;//1.2、创建一个包含n个元素的list容器//listint values(10);//1.3、创建一个包含n个元素的list容器并为每个元素指定初始值//listint values(10,5);//1.4、在已有list容器的情况下拷贝改容器创建新的list容器listint value1(10);listint value2(value1);//1.5、拷贝其他容器类型中指定区域的元素创建新的list容器//拷贝普通数组创建list容器//int a[] { 1,2,3,4,5 };//std::listint values(a, a5);//拷贝其它类型的容器创建 list 容器//std::arrayint, 5arr{ 11,12,13,14,15 };//std::listintvalues(arr.begin()2, arr.end());//拷贝arr容器中的{13,14,15}//2、部分成员函数的用法//创建空的list容器listdouble values;//向容器中添加元素values.push_back(2.2);values.push_back(1.1);values.push_back(3.3);cout values.size(): values.size() endl;//对容器中的元素进行排序values.sort();//for循环遍历输出for (auto i: values){cout i ;}cout endl;//迭代器遍历输出for (listdouble::iterator iter values.begin(); iter ! values.end(); iter){cout *iter ;}cout endl;//auto迭代器输出for (auto iter values.begin(); iter!values.end(); iter){cout *iter ;}cout endl;} 3.4.3、list迭代器的用法 其对应的是双向迭代器可以、–、判等但是不可以比大小、不可以加数值(不可随机访问)。 前面章节已经详细介绍了 array、vector、deque 容器的迭代器和它们相比list 容器迭代器最大的不同在于其配备的迭代器类型为双向迭代器而不再是随机访问迭代器。 这意味着假设 p1 和 p2 都是双向迭代器则它们支持使用 p1、 p1、 p1–、 p1、 *p1、 p1p2 以及 p1!p2 运算符但不支持以下操作其中 i 为整数 p1[i]不能通过下标访问 list 容器中指定位置处的元素。p1-i、 p1i、 p1i 、p1-i双向迭代器 p1 不支持使用 -、、、- 运算符。p1p2、 p1p2、 p1p2、 p1p2双向迭代器 p1、p2 不支持使用 、 、 、 比较运算符。 注意程序中比较迭代器之间的关系用的是 ! 运算符因为它不支持 等运算符。另外在实际场景中所有迭代器函数的返回值都可以传给使用 auto 关键字定义的变量因为编译器可以自行判断出该迭代器的类型。 #include list #include array #include iostreamusing namespace std;int main() {//创建list容器listchar values{h,t,t,p,:,/,/,w,w,w,.,b,a,i,d,u,.,c,o,m};//使用正向迭代器for (auto iter values.begin(); iter ! values.end(); iter){cout *iter ;}cout endl;//使用反向迭代器for(auto iter values.rbegin(); iter ! values.rend(); iter){cout *iter ;}cout endl;cout endl;//创建begin()和end()迭代器listchar::iterator beg values.begin();listchar::iterator end values.end();while(beg!end){cout *beg ;beg;}cout endl;beg values.begin();end values.end();//头部和尾部插入字符values.insert(beg,1);values.insert(end,1);while(beg!end){cout *beg ;beg;}cout endl; }输出为 h t t p : / / w w w . b a i d u . c o m m o c . u d i a b . w w w / / : p t t h h t t p : / / w w w . b a i d u . c o m h t t p : / / w w w . b a i d u . c o m 1
   结论插入元素不会导致之前的迭代器失效(程序不会报错);但是由于插入元素位置的不同使用老迭代器可能会遗漏新插入元素。 3.4.4、访问list中的元素 不同于之前学过的 STL 容器访问 list 容器中存储元素的方式很有限即要么使用 front() 和 back() 成员函数要么使用 list 容器迭代器。 list 容器不支持随机访问未提供下标操作符 [] 和 at() 成员函数也没有提供 data() 成员函数。 #include list #include array #include iostreamusing namespace std;int main() {//创建list容器listint mylist{1,2,3,4};cout mylist.front(): mylist.front() endl;cout mylist.back(): mylist.back() endl;//注:front/back不进可以访问首末元素,还可以修改他们的值mylist.front() 11;mylist.back() 44;cout mylist.front(): mylist.front() endl;cout mylist.back(): mylist.back() endl;//其他访问方法就是迭代器了for (auto iter mylist.begin(); iter ! mylist.end(); iter){cout *iter ;}cout endl; } 3.4.5、list插入元素 list 模板类中与“添加或插入新元素”相关的成员方法有如下几个 push_front()向 list 容器首个元素前添加新元素push_back()向 list 容器最后一个元素后添加新元素emplace_front()在容器首个元素前直接生成新的元素emplace_back()在容器最后一个元素后直接生成新的元素emplace()在容器的指定位置直接生成新的元素insert()在指定位置插入新元素splice()将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。 读者有没有发现同样是实现插入元素的功能无论是 push_front()、push_back() 还是 insert()都有以 emplace 为名且功能和前者相同的成员函数。这是因为后者是 C 11 标准新添加的在大多数场景中都可以完全替代前者实现同样的功能。更重要的是实现同样的功能emplace 系列方法的执行效率更高。 以上这些成员方法中除了 insert() 和 splice() 方法有多种语法格式外其它成员方法都仅有 1 种语法格式。 #include list #include array #include iostreamusing namespace std;int main() {listint values{1, 2, 3};values.push_front(0); //{0,1,2,3}values.push_back(4); //{0,1,2,3,4}values.emplace_front(-1); //{-1,0,1,2,3,4}values.emplace_back(5); //{-1,0,1,2,3,4,5}//emplace(pos, value) pos表示插入的位置(用迭代器表示),value为待插入的元素values.emplace(values.end(), 6); //{-1,0,1,2,3,4,5,6}for(auto iter values.begin(); iter ! values.end(); iter){cout *iter ;}cout endl; } list的insert()成员函数。前面介绍的一样有四种方式如表 1 所示。 表 1 insert() 成员方法语法格式 语法格式用法说明iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素 elem并返回表示新插入元素位置的迭代器。iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前插入其他容器例如 array、vector、deque 等中位于 [first,last) 区域的所有元素并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,initlist)在迭代器 pos 指定的位置之前插入初始化列表用大括号 { } 括起来的多个元素中间有逗号隔开中所有的元素并返回表示第一个新插入元素位置的迭代器。 list的splice()成员函数。 splice功能是将其他list容器中的元素添加到当前list容器指定位置处。 splice: 粘接 英[splaɪs] splice() 成员方法的语法格式有 3 种如表 2 所示。   表 2 splice() 成员方法的用法 语法格式功能void splice (iterator position, list x);position 为迭代器用于指明插入位置x 为另一个 list 容器。 此格式的 splice() 方法的功能是将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。void splice (iterator position, list x, iterator i);position 为迭代器用于指明插入位置x 为另一个 list 容器i 也是一个迭代器用于指向 x 容器中某个元素。 此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。void splice (iterator position, list x, iterator first, iterator last);position 为迭代器用于指明插入位置x 为另一个 list 容器first 和 last 都是迭代器[fist,last) 用于指定 x 容器中的某个区域。 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。 #include list #include array #include iostreamusing namespace std;int main() {//创建两个list容器listint list1{1,2,3,4}, list2{10,20,30};auto it1 list1.begin(); //指向list1容器中的元素2//第一种语法:在list1的iter位置处splice list2list1.splice(it1, list2); //list1 {1,10,20,30,2,3,4}for(auto i: list1){cout i ;}cout endl;//第二种语法: 将list1迭代器it1指向的元素(2)移动到list2.begin位置处list2.splice(list2.begin(), list1, it1);cout list1:;for(auto i: list1){cout i ;}cout endl;cout list2:;for(auto i: list2){cout i ;}cout endl;//第三种语法: 将[list1.begin(),list1.end()]范围内的元素移动到list2.begin()位置处list2.splice(list2.begin(), list1, list1.begin(), list1.end());cout list1:;for(auto i: list1){cout i ;}cout endl;cout list2:;for(auto i: list2){cout i ;}cout endl; } 输出结果为 1 10 20 30 2 3 4 list1:1 10 20 30 3 4 list2:2 list1: list2:1 10 20 30 3 4 2 3.4.6、list删除元素 对 list 容器存储的元素执行删除操作需要借助该容器模板类提供的成员函数。幸运的是相比其它 STL 容器模板类list 模板类提供了更多用来实现此操作的成员函数如表 1 所示。   表 1 实现 list 容器删除元素的成员函数 成员函数功能pop_front()删除位于 list 容器头部的一个元素。pop_back()删除位于 list 容器尾部的一个元素。erase()该成员函数既可以删除 list 容器中指定位置处的元素也可以删除容器中某个区域内的多个元素。clear()删除 list 容器存储的所有元素。remove(val)删除容器中所有等于 val 的元素。unique()删除容器中相邻的重复元素只保留一份。remove_if()删除容器中满足条件的元素。 3.5、 forward_list(单向链表) #includeforward_listusing namespace std; 3.5.1、forward_list介绍 forward_list 是 C 11 新添加的一类容器其底层实现和 list 容器一样采用的也是链表结构只不过 forward_list 使用的是单链表而 list 使用的是双向链表如图 1 所示。 因此forward_list 容器具有和 list 容器相同的特性即擅长在序列的任何位置进行插入元素或删除元素的操作但对于访问存储的元素没有其它容器如 array、vector的效率高。 另外由于单链表没有双向链表那样灵活因此相比 list 容器forward_list 容器的功能受到了很多限制。比如由于单链表只能从前向后遍历而不支持反向遍历因此 forward_list 容器只提供前向迭代器而不是双向迭代器。这意味着forward_list 容器不具有 rbegin()、rend() 之类的成员函数。 那么既然 forward_list 容器具有和 list 容器相同的特性list 容器还可以提供更多的功能函数forward_list 容器有什么存在的必要呢   效率高是选用 forward_list 而弃用 list 容器最主要的原因换句话说只要是 list 容器和 forward_list 容器都能实现的操作应优先选择 forward_list 容器。 3.5.2、forward_list使用 #include forward_list #include iostream #include iterator using namespace std;int main() {forward_listint values{1,2,3,4,5};forward_listint value1{10};forward_listint value2(value1);values.emplace_front(0); //{0,1,2,3,4,5}values.emplace_after(values.begin(), 6); //{0,1,2,3,4,5,6}for(auto iter values.begin(); iter ! values.end(); iter){cout *iter ;}cout endl;values.reverse();for(auto iter values.begin(); iter ! values.end(); iter){cout *iter ;}cout endl;//forward_list不提供size()函数如果想要获取元素数可以通过 头文件iterator中的distance()函数。int count std::distance(std::begin(values), std::end(values));cout count: count endl;//forward_list除了吹用运算符单步移动,还能使用 advance() 函数多步移动auto it values.begin();cout *it: *it endl;advance(it, 2);cout *it: *it endl; }输出如下 0 6 1 2 3 4 5 5 4 3 2 1 6 0 count:7 *it:5 *it:3 4、STL有序关联容器(map/set/multimap/multiset) — 红黑树 4.0、关联容器介绍 前面序列式容器只存储各种类型的元素。关联式容器则大不一样此类容器在存储元素值的同时还会为各元素额外再配备一个“键”其本质也是一个 C 基础数据类型或自定义类型的元素它的功能是在使用关联式容器的过程中如果已知目标元素的键的值则直接通过该键就可以找到目标元素而无需再通过遍历整个容器的方式。 也就是说关联式容器存储的元素都是一个一个的“键值对” key,value 这是和序列式容器最大的不同。除此之外序列式容器中存储的元素默认都是未经过排序的而使用关联式容器存储的元素默认会根据各元素的键值的大小做升序排序。   注set的键值相等了而已也可以视为键值对 关联式容器所具备的这些特性归咎于 STL 标准库在实现该类型容器时底层选用了 「红黑树」这种数据结构来组织和存储各个键值对。 4.0.1、STL关联容器种类 C STL 标准库提供了 4 种关联式容器分别为 map、set、multimap、multiset其各自的特点如表 1 所示。 表 1 C STL关联式容器类别 关联式容器名称特点map定义在 map 头文件中使用该容器存储的数据其各个元素的键必须是唯一的即不能重复该容器会根据各元素键的大小默认进行升序排序调用 std::lessT。set定义在 set 头文件中使用该容器存储的数据各个元素键和值完全相同且各个元素的值不能重复保证了各元素键的唯一性。该容器会自动根据各个元素的键其实也就是元素值的大小进行升序排序调用 std::lessT。multimap定义在 map 头文件中和 map 容器唯一的不同在于multimap 容器中存储元素的键可以重复。multiset定义在 set 头文件中和 set 容器唯一的不同在于multiset 容器中存储元素的值可以重复一旦值重复则意味着键也是重复的。 除此之外C 11 还新增了 4 种哈希容器即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说它们也属于关联式容器但由于哈希容器底层采用的是哈希表而不是红黑树因此将它们分开进行讲解有关哈希容器将放在后续章节做详细讲解 4.0.2、 pair #includeutility#include iostream #include string #include utilityusing namespace std;int main() {//调用默认构造函数pairstring, double pair1;//调用第二种构造函数pairstring, string pair2(name,zhizhuo);//调用拷贝构造函数pairstring, string pair3(pair2);//make_pair构造pairstring, string pair4 make_pair(age, 20);auto pair5 make_pair(gender, man);//打印各paircout pair1: pair1.first pair1.second endl;cout pair2: pair2.first pair2.second endl;cout pair3: pair3.first pair3.second endl;cout pair4: pair4.first pair4.second endl;cout pair5: pair5.first pair5.second endl;//pair类模板还提供一个swap成员函数,能够互换两个pair的键值对;当然前提是类型相同。cout endl;pair2.swap(pair4);cout pair2: pair2.first pair2.second endl;cout pair4: pair4.first pair4.second endl; }输出为 pair1: 0 pair2: name zhizhuo pair3: name zhizhuo pair4: age 20 pair5: gender manpair2: age 20 pair4: name zhizhuo 4.1、 map #includemapusing namespace std; 4.1.1、map简介 map容器的模板定义如下 template class Key, // 指定键key的类型class T, // 指定值value的类型class Compare lessKey, // 指定排序规则class Alloc allocatorpairconst Key,T // 指定分配器对象的类型 class map; 可以看到map 容器模板有 4 个参数其中后 2 个参数都设有默认值。大多数场景中我们只需要设定前 2 个参数的值有些场景可能会用到第 3 个参数但最后一个参数几乎不会用到。   在使用map容器存储多个键值对的时候map会自动根据各键值对的键的大小按照既定规则进行排序。默认情况下map容器选用 std::lessT 排序规则此时会根据键的大小对所有键值对做升序排序。当然根据实际情况的需要我们可以手动指定map容器的排序规则既可以选用STL标准库提供的其他排序规则(比如 std::greaterT)也可以自定义排序规则。 #include iostream #include string #include utility #include mapusing namespace std;int main() {//调用map默认构造函数创建一个空的map容器std::mapstring, int map1;//在创建map容器的同事进行初始化mapstring, int map2{{math, 100}, {english, 97}};mapstring, int map3{make_pair(chinese, 92), make_pair(physics, 99)};//基于已有map创建新的mapmapstring, int map4(map3);//手动修改map容器的排序规则。默认情况下map容器调用std::lessT规则此时按照键做升序排列mapstring, int, std::lessstring map5{{chemistry, 94}, {physical culture, 96}};//范围for语句遍历for (auto iter: map5){cout iter.first : iter.second endl;}cout endl;//手动修改排序规则为降序mapstring, int, std::greaterstring map6{{chemistry, 94}, {physical culture, 96}};//范围for语句遍历for (auto iter: map6){cout iter.first : iter.second endl;} }输出如下 chemistry:94 physical culture:96physical culture:96 chemistry:94 4.1.2、map成员函数 表 1 列出了 map 容器提供的常用成员方法以及各自的功能。   表 1 C map容器常用成员方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个键值对的双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend()返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。find(key)在 map 容器中查找键为 key 的键值对如果成功找到则返回指向该键值对的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(key)返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(key)返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(key)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含的键为 key 的键值对map 容器键值对唯一因此该范围最多包含一个键值对。empty() 若容器为空则返回 true否则 false。size()返回当前 map 容器中存有键值对的个数。max_size()返回 map 容器所能容纳键值对的最大个数不同的操作系统其返回值亦不相同。operator[]map容器重载了 [] 运算符只要知道 map 容器中某个键值对的键的值就可以向获取数组中元素那样通过键直接获取对应的值。at(key)找到 map 容器中 key 键对应的值如果找不到该函数会引发 out_of_range 异常。insert()向 map 容器中插入键值对。erase()删除 map 容器指定位置、指定键key值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。swap()交换 2 个 map 容器中存储的键值对这意味着操作的 2 个键值对的类型必须相同。clear()清空 map 容器中所有的键值对即使 map 容器的 size() 为 0。emplace()在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样但效率更高。emplace_hint()在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的不同之处在于使用者必须为该方法提供一个指示键值对生成位置的迭代器并作为该方法的第一个参数。count(key)在当前 map 容器中查找键为 key 的键值对的个数并返回。注意由于 map 容器中各键值对的键的值是唯一的因此该函数的返回值最大为 1。 #include iostream #include string #include utility #include mapusing namespace std;int main() {//调用map默认构造函数创建一个空的map容器std::mapstring, int, std::greaterstring map1;//插入元素map1.emplace(math, 100);map1.emplace(chinese, 92);map1.emplace(english, 97);map1[physics] 99;map1[chemistry] 94;//输出当前map容器存储键值对的个数cout map1.size(): map1.size() endl;cout map1[math]: map1.at(math) endl; cout map1[physics]: map1.at(physics) endl; cout endl;//判断当前容器是否为空if (!map1.empty()){//借助迭代器进行遍历for (auto iter map1.begin(); iter ! map1.end(); iter){cout iter-first : iter-second endl;}}cout endl;//查找某个key是否存在string key math;if (map1.find(key) map1.end()){cout no key key endl; }else{cout has key key endl;} } 输出结果 map1.size():5 map1[math]:100 map1[physics]:99physics:99 math:100 english:97 chinese:92 chemistry:94has key math 4.1.3、map迭代器用法 C STL 标准库为 map 容器配备的是双向迭代器bidirectional iterator。这意味着map 容器迭代器只能进行 p、p、–p、p–、p 操作并且迭代器之间只能使用 或者 ! 运算符进行比较。   值得一提的是相比序列式容器map 容器提供了更多的成员方法如表 1 所示通过调用它们我们可以轻松获取具有指定含义的迭代器。   表 1 map 容器迭代器相关成员方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个键值对的双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend() 返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。cend() 和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crbegin() 和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crend() 和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。find(key)在 map 容器中查找键为 key 的键值对如果成功找到则返回指向该键值对的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(key)返回一个指向当前 map 容器中第一个大于等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(key) 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(key)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含的键为 key 的键值对map 容器键值对唯一因此该范围最多包含一个键值对。 同时map 类模板中还提供有 lower_bound(key) 和 upper_bound(key) 成员方法它们的功能是类似的唯一的区别在于 lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器 #include iostream #include string #include utility #include mapusing namespace std;int main() {//调用map默认构造函数创建一个空的map容器std::mapstring, string map1;//插入元素map1[a] aa;map1[b] bb;map1[c] cc;map1[d] dd;map1[e] ee;for (auto elem: map1){cout elem.first elem.second endl;}cout endl;auto iter1 map1.upper_bound(b);cout upper_bound(b): iter1-first iter1-second endl;auto iter2 map1.lower_bound(b);cout lower_bound(b): iter2-first iter2-second endl;cout endl;//创建一个pair对象,来接受equal_range()的返回值pairmapstring, string::iterator, mapstring, string::iterator mypair map1.equal_range(d);for(auto iter mypair.first; iter!mypair.second; iter){cout iter-first iter-second endl;}} 输出如下 a aa b bb c cc d dd e eeupper_bound(b):c cc lower_bound(b):b bbd dd lower_bound(key) 和 upper_bound(key) 更多用于 multimap 容器在 map 容器中很少用到。         和 lower_bound(key)、upper_bound(key) 一样该equal_range也更常用于 multimap 容器因为 map 容器中各键值对的键的值都是唯一的因此通过 map 容器调用此方法其返回的范围内最多也只有 1 个键值对。 equal_range(key) 成员方法可以看做是 lower_bound(key) 和 upper_bound(key) 的结合体该方法会返回一个 pair 对象其中的 2 个元素都是迭代器类型其中 pair.first 实际上就是 lower_bound(key) 的返回值而 pair.second 则等同于 upper_bound(key) 的返回值。 显然equal_range(key) 成员方法表示的一个范围位于此范围中的键值对其键的值都为 key。 4.1.4、map获取键对应值的方法 主要有三种方法 1重载[]运算符下标法访问   2at()成员方法  3) find()成员函数 #include iostream #include string #include utility #include mapusing namespace std;int main() {//调用map默认构造函数创建一个空的map容器std::mapstring, string map1;//插入元素map1[a] aa;map1[b] bb;map1[c] cc;map1[d] dd;map1[e] ee;for (auto elem: map1){cout elem.first elem.second endl;}cout endl;// 方法一: 通过下标访问// map 容器中确实存有包含该指定键的键值对借助重载的 [ ] 运算符才能成功获取该键对应的值// 反之若当前 map 容器中没有包含该指定键的键值对则此时使用 [ ] 运算符将不再是访问容器中的元素而变成了向该 map 容器中增添一个键值对。其中该键值对的键用 [ ] 运算符中指定的键其对应的值取决于 map 容器规定键值对中值的数据类型如果是基本数据类型则值为 0如果是 string 类型其值为 即空字符串即使用该类型的默认值作为键值对的值。string str_f map1[f];//可以看到上述指令等效于添加了一项 f, for (auto elem: map1){cout elem.first elem.second endl;}cout endl;//方法二通过at()成员函数访问 / string str_g map1.at(g); //抛异常cout str_g: str_g endl;for (auto elem: map1){cout elem.first elem.second endl;}cout endl; ///方法三通过find()成员函数访问string key h;if (map1.find(key) map1.end()){cout no key key endl;}else{cout has key key endl;} } 输出为 a aa b bb c cc d dd e eea aa b bb c cc d dd e ee f has key f 本节所介绍的几种方法中仅从“在 map 容器存储的键值对中获取指定键对应的值”的角度出发更推荐使用 at() 成员方法因为该方法既简单又安全。 4.1.5、map insert成员函数的几种用法 #include iostream #include string #include utility #include mapusing namespace std;int main() {//insert插入数据的四种方式mapstring, string map1;//默认方式借助[]运算符map1[aa] aaaa;cout map1[aa]: map1[aa] endl;map1[bb] bbbb;for (auto elem: map1){cout elem.first elem.second endl;}cout endl;//insert()方式1 无需指定插入位置pairstring, string mypair {cc, cccc}; //创建一个pairpairmapstring, string::iterator, bool ret; //创建一个接受insert()方法返回值的pair对象ret map1.insert(mypair);cout ret.iter { ret.first-first , ret.first-second }, ret.second endl;//以右值引用的方式传递临时的键值对变量ret map1.insert({dd, dddd});cout ret.iter { ret.first-first , ret.first-second }, ret.second endl;//看看插入失败的例子(前面已经有cc了)ret map1.insert({cc, cccc});cout ret.iter { ret.first-first , ret.first-second }, ret.second endl;/ 总结:从上述执行结果可以看到程序总共执行了3次插入操作其中成功2次失败1次(1)对于插入成功的caseinsert返回的pair对象指向新插入键值对的迭代器和值为1的bool变量(2)对于插入失败的baseinsert返回想要插入的键值对 和 值为0的bool变量。*///insert()方式2 支持向map容器的指定位置插入新键值对//注: 我觉得这个没啥意义因为map依然会自动排序cout endl;mapstring, string::iterator it map1.begin();pairstring, string pair2 {ee, eeee};auto iter1 map1.insert(it, pair2);cout iter1-first iter1-second endl;cout endl;for (auto iter map1.begin(); iter ! map1.end(); iter){cout iter-first iter-second endl;}//下面insert的其他用法也就不看了,没啥意思}输出结果如下 map1[aa]:aaaa aa aaaa bb bbbbret.iter {cc, cccc}, 1 ret.iter {dd, dddd}, 1 ret.iter {cc, cccc}, 0ee eeeeaa aaaa bb bbbb cc cccc dd dddd ee eeee 4.1.6、map emplace/emplace_hint方法 值得一提的是实现相同的插入操作无论是用 emplace() 还是 emplace_hont()都比 insert() 方法的效率高后续章节会详细讲解。 和 insert() 方法相比emplace() 和 emplace_hint() 方法的使用要简单很多因为它们各自只有一种语法格式。其中emplace() 方法的语法格式如下 template class… Argspairiterator,bool emplace (Args… args); 参数 (Args… args) 指的是这里只需要将创建新键值对所需的数据作为参数直接传入即可此方法可以自行利用这些数据构建出指定的键值对。另外该方法的返回值也是一个 pair 对象其中 pair.first 为一个迭代器pair.second 为一个 bool 类型变量 当该方法将键值对成功插入到 map 容器中时其返回的迭代器指向该新插入的键值对同时 bool 变量的值为 true当插入失败时则表明 map 容器中存在具有相同键的键值对此时返回的迭代器指向此具有相同键的键值对同时 bool 变量的值为 false。 #include iostream #include string #include utility #include mapusing namespace std;int main() {mapstring, string map1;//构造emplace返回pairmapstring, string::iterator, bool ret;//插入键值对ret map1.emplace(aa,aaaa);cout 1、ret.iter{ ret.first-first , ret.first-second }, ret.second endl;//新插入键值对ret map1.emplace(bb,bbbb);cout 2、ret.iter{ ret.first-first , ret.first-second }, ret.second endl;//插入失败样例ret map1.emplace(aa,aaaa);cout 3、ret.iter{ ret.first-first , ret.first-second }, ret.second endl;/可以看到程序中共执行了 3 次向 map 容器插入键值对的操作其中前 2 次都成功了第 3 次由于要插入的键值对的键和 map 容器中已存在的键值对的键相同因此插入失败。///emplace_hint()方法//我觉得这个东西没啥意义 虽然可以指定位置插入但是map容器为了保持存储键值对的有序状态还是会移动其位置。}输出结果如下 1、ret.iter{aa, aaaa}, 1 2、ret.iter{bb, bbbb}, 1 3、ret.iter{aa, aaaa}, 0 4.1.7、为什么emplace/emplace_hint的效率更高 原因很简单它们向 map 容器插入键值对时底层的实现方式不同 使用 insert() 向 map 容器中插入键值对的过程是先创建该键值对然后再将该键值对复制或者移动到 map 容器中的指定位置使用 emplace() 或 emplace_hint() 插入键值对的过程是直接在 map 容器中的指定位置构造该键值对。 也就是说向 map 容器中插入键值对时emplace() 和 emplace_hint() 方法都省略了移动键值对的过程因此执行效率更高。 因此在实现向 map 容器中插入键值对时应优先考虑使用 emplace() 或者 emplace_hint()。 4.2、 multimap 和map的区别在于multimap容器可以存储多个键相同的键值对其他特性相同。 #includemapusing namespace std; multimap容器类模板的定义如下 template class Key, // 指定键key的类型class T, // 指定值value的类型class Compare lessKey, // 指定排序规则class Alloc allocatorpairconst Key,T // 指定分配器对象的类型 class multimap; 可以看到multimap容器模板有4个参数其中后两个参数都有默认值。 和map一样multimap通常只需要设定前两个参数有些场景可能用到第三个参数地4个参数几乎不会用到。 表 1 列出了 multimap 类模板提供的常用成员方法及各自的功能。   表 1 C multimap 容器常用成员方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个键值对的双向迭代器。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend()返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的键值对。find(key)在 multimap 容器中查找首个键为 key 的键值对如果成功找到则返回指向该键值对的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 multimap 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(key)返回一个指向当前 multimap 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(key)返回一个指向当前 multimap 容器中第一个大于 key 的键值对的迭代器。如果 multimap 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(key)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含的键为 key 的键值对。empty() 若容器为空则返回 true否则 false。size()返回当前 multimap 容器中存有键值对的个数。max_size()返回 multimap 容器所能容纳键值对的最大个数不同的操作系统其返回值亦不相同。insert()向 multimap 容器中插入键值对。erase()删除 multimap 容器指定位置、指定键key值或者指定区域内的键值对。swap()交换 2 个 multimap 容器中存储的键值对这意味着操作的 2 个键值对的类型必须相同。clear()清空 multimap 容器中所有的键值对使 multimap 容器的 size() 为 0。emplace()在当前 multimap 容器中的指定位置处构造新键值对。其效果和插入键值对一样但效率更高。emplace_hint()在本质上和 emplace() 在 multimap 容器中构造新键值对的方式是一样的不同之处在于使用者必须为该方法提供一个指示键值对生成位置的迭代器并作为该方法的第一个参数。count(key)在当前 multimap 容器中查找键为 key 的键值对的个数并返回。 和 map 容器相比multimap 未提供 at() 成员方法也没有重载 [] 运算符。这意味着map 容器中通过指定键获取指定指定键值对的方式将不再适用于 multimap 容器。其实这很好理解因为 multimap 容器中指定的键可能对应多个键值对而不再是 1 个。 #include iostream #include mapusing namespace std;void print_multimap(std::multimapstring, string mmap){for(auto iter mmap.begin(); iter ! mmap.end(); iter){cout iter-first iter-second endl;}cout endl; }int main() {//1、multimap 容器的创建方法(总的来说有5种)//1.1、调用multimap类模板的默认构造函数 创建一个空的multimap容器std::multimapstring, string mmap1;cout mmap1(use less order): endl; print_multimap(mmap1);//1.2、创建multimap容器的同时 初始化之//这种方式会将每个{key,value}对创建成pair类型的键值对然后用各个键值对初始化multimap容器。std::multimapstring, string mmap2{ {aa, aaaa},{bb, bbbb},{bb, bbbb},{cc, cccc},{dd, dddd} };cout mmap2(use less order): endl; print_multimap(mmap2);//实际上先创建pair然后在初始化效果也是一样的std::multimapstring, string mmap3{ pairstring, string{aa, aaaa},pairstring, string{bb, bbbb},make_pair(bb, bbbb),make_pair(cc, cccc),make_pair(dd, dddd),};cout mmap3(use less order): endl; print_multimap(mmap3);//1.3、通过类模板的拷贝来构造函数std::multimapstring, string mmap4(mmap3);cout mmap4(use less order): endl; print_multimap(mmap4);//1.4、支持从已有multimap容器中选定某块区域内的所有键值对,用作初始化新multimap容器//multimap的迭代器用法和map完全相同,此处不做过多介绍std::multimapstring, string mmap5(mmap4.begin(), mmap4.end());cout mmap5(use less order): endl;print_multimap(mmap5);//1.5、第三个参数默认是std::less表示升序排序,也可以指定std::greater降序排列std::multimapstring, string, std::greaterstring mmap6{{aa, aaaa},{bb, bbbb},{cc, cccc}};cout mmap6(use greater order): endl;for(auto elem: mmap6){cout elem.first elem.second endl;}} 输出如下 mmap1(use less order):mmap2(use less order): aa aaaa bb bbbb bb bbbb cc cccc dd ddddmmap3(use less order): aa aaaa bb bbbb bb bbbb cc cccc dd ddddmmap4(use less order): aa aaaa bb bbbb bb bbbb cc cccc dd ddddmmap5(use less order): bb bbbb bb bbbb cc cccc dd ddddmmap6(use greater order): cc cccc bb bbbb aa aaaa 如下演示multimap部分成员函数的使用 #include iostream #include mapusing namespace std;void print_multimap(std::multimapstring, string mmap){for(auto iter mmap.begin(); iter ! mmap.end(); iter){cout iter-first iter-second endl;}cout endl; }int main() {std::multimapstring, string mmap2{ {aa, aaaa},{bb, bbbb},{bb, bbbb},{cc, cccc},{dd, dddd} };cout mmap2(use less order): endl; print_multimap(mmap2);//如下演示multimap部分成员函数的用法//输出 multimap 容器存储键值对的数量cout mmap2.size(): mmap2.size() endl;//输出 multimap 容器中存储键为 bb 的键值对的数量cout mmap2.count(bb): mmap2.count(bb) endl;cout endl;for (auto iter mmap2.begin(); iter! mmap2.end(); iter){cout iter-first iter-second endl;} }输出结果 mmap2(use less order): aa aaaa bb bbbb bb bbbb cc cccc dd ddddmmap2.size():5 mmap2.count(bb):2aa aaaa bb bbbb bb bbbb cc cccc dd dddd 4.3、 set 4.3.1、set简介 C STL除了map、multimap还提供有set和multiset两个关联式容器。set/multiset也会像map一样根据键的大小对存储的键值进行排队。只不过set/multiset容器中各键值对的键key和值value是相等的。同理set 容器存储的元素互不相等、multiset则是元素可以相等的set。 #includesetusing namespace std; set容器的类模板定义如下 template class T, // 键 key 和值 value 的类型class Compare lessT, // 指定 set 容器内部的排序规则class Alloc allocatorT // 指定分配器对象的类型 class set; 注意由于 set 容器存储的各个键值对其键和值完全相同也就意味着它们的类型相同因此 set 容器类模板的定义中仅有第 1 个参数用于设定存储数据的类型。 对于 set 类模板中的 3 个参数后 2 个参数自带默认值且几乎所有场景中只需使用前 2 个参数第 3 个参数不会用到。 4.3.2、创建set容器的5种方法 #include iostream #include setusing namespace std;templateclass T void print_set(setT set){for(auto iter set.begin(); iter ! set.end(); iter){cout *iter endl;}cout endl; }templateclass T void print_set(setT, std::greaterT set){for(auto iter set.begin(); iter ! set.end(); iter){cout *iter endl;}cout endl; }int main() {//1、常见的创建set容器的方法//1.1、默认构造函数 创建空的set容器setstring set1;print_set(set1);//1.2、创建set的同时,对其初始化setstring set2{aa,bb,cc};print_set(set2);//1.3、拷贝构造函数,利用已有set进行拷贝创建setstring set3(set2);print_set(set3);//1.4、取已有set容器中的部分元素初始化新的set容器setstring set4(set2.begin(), set2.end()); print_set(set4);//1.5、默认采用std::lessT规则,也可以指定排序顺序为 std::greaterTsetstring, std::greaterstring set5{aa,bb,cc,dd,ee};print_set(set5); } 输出如下 aa bb ccaa bb ccbb ccee dd cc bb aa 4.3.3、set容器的成员函数 表 1 列出了 set 容器提供的常用成员方法以及各自的功能。   表 1 C set 容器常用成员方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个元素的双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend()返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。find(val)在 set 容器中查找值为 val 的元素如果成功找到则返回指向该元素的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(val)返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(val)返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(val)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含的值为 val 的元素set 容器中各个元素是唯一的因此该范围最多包含一个元素。empty()若容器为空则返回 true否则 false。size()返回当前 set 容器中存有元素的个数。max_size()返回 set 容器所能容纳元素的最大个数不同的操作系统其返回值亦不相同。insert()向 set 容器中插入元素。erase()删除 set 容器中存储的元素。swap()交换 2 个 set 容器中存储的所有元素。这意味着操作的 2 个 set 容器的类型必须相同。clear()清空 set 容器中所有的元素即令 set 容器的 size() 为 0。emplace()在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样但效率更高。emplace_hint()在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的不同之处在于使用者必须为该方法提供一个指示新元素生成位置的迭代器并作为该方法的第一个参数。count(val)在当前 set 容器中查找值为 val 的元素的个数并返回。注意由于 set 容器中各元素的值是唯一的因此该函数的返回值最大为 1。 部分成员函数使用 #include iostream #include setusing namespace std;templateclass T void print_set(setT set){for(auto iter set.begin(); iter ! set.end(); iter){cout *iter endl;}cout endl; }templateclass T void print_set(setT, std::greaterT set){for(auto iter set.begin(); iter ! set.end(); iter){cout *iter endl;}cout endl; }int main() {setstring myset;cout 1、myset.size(): myset.size() endl;//向set中插入新元素myset.insert(aa);myset.insert(bb);myset.emplace(cc);myset.emplace(dd);cout 2、myset.size(): myset.size() endl;//使用双向迭代器遍历setfor (auto iter myset.begin(); iter ! myset.end(); iter){cout *iter endl;} }输出如下 1、myset.size():0 2、myset.size():4 aa bb cc dd 4.3.4、set的迭代器 和 map 容器不同C STL 中的 set 容器类模板中未提供 at() 成员函数也未对 [] 运算符进行重载。因此要想访问 set 容器中存储的元素只能借助 set 容器的迭代器。         C STL 标准库为 set 容器配置的迭代器类型为双向迭代器。这意味着假设 p 为此类型的迭代器则其只能进行 p、p、–p、p–、*p 操作并且 2 个双向迭代器之间做比较也只能使用 或者 ! 运算符。 在 set 容器类模板提供的所有成员函数中返回迭代器的成员函数如表 1 所示。   表 1 C set 容器迭代器方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个元素的双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend()返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。通常和 rbegin() 结合使用。如果 set 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。find(val)在 set 容器中查找值为 val 的元素如果成功找到则返回指向该元素的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(val)返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(val)返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(val)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含的值为 val 的元素set 容器中各个元素是唯一的因此该范围最多包含一个元素。 注意以上成员函数返回的迭代器指向的只是 set 容器中存储的元素而不再是键值对。另外以上成员方法返回的迭代器无论是 const 类型还是非 const 类型都不能用于修改 set 容器中的值。 值得一提的是虽然 C STL 标准中set 类模板中包含 lower_bound()、upper_bound()、equal_range() 这 3 个成员函数但它们更适用于 multiset 容器几乎不会用于操作 set 容器。 4.3.5、set insert()方法 #include set #include string #include iostreamusing namespace std;int main() {//insert方式像set插入数据//1、只要给定目标元素的值,insert()方法就可以将元素添加到容器/普通引用方式传参和右值引用方式传参格式的 insert() 方法返回的都是 pair 类型的值其包含 2 个数据一个迭代器和一个 bool 值当向 set 容器添加元素成功时该迭代器指向 set 容器新添加的元素bool 类型的值为 true如果添加失败即证明原 set 容器中已存有相同的元素此时返回的迭代器就指向容器中相同的此元素同时 bool 类型的值为 false。/std::setstring myset;//insert的返回值pairsetstring::iterator, bool retpair;retpair myset.insert(aa);cout iter- *(retpair.first) bool retpair.second endl;string str bb;retpair myset.insert(str);cout iter- *(retpair.first) bool retpair.second endl;//搞一个插入失败的例子retpair myset.insert(bb);cout iter- (retpair.first) bool retpair.second endl;//2、insert()还可以将新元素插入到set容器的具体位置//注不演示了,没啥意义(还是会自动排序的)//3、insert() 方法支持向当前 set 容器中插入其它 set 容器指定区域内的所有元素只要这 2 个 set 容器存储的元素类型相同即可。/ 此时语法格式如下:template class InputIteratorvoid insert (InputIterator first, InputIterator last);*/cout endl;std::setstring set1{aa,bb,cc, dd};std::setstring set2;set2.insert(set1.begin(), set1.end());for(auto iter set2.begin(); iter ! set2.end(); iter){cout iter endl;}//4、一次向set中insert多个元素cout endl;std::setstring set3;set3.insert({aa,bb,cc,dd});for (auto elem: set3){cout elem endl;} } 除了insert外C11还另外提供了2个成员函数 emplace() 和 emplace_hint()同样实现插入的效果而且效率更高。 4.3.6、emplace()方法 emplace() 和 emplace_hint() 是 C 11 标准加入到 set 类模板中的相比具有同样功能的 insert() 方法完成同样的任务emplace() 和 emplace_hint() 的效率会更高。   注意和 insert() 方法一样虽然 emplace_hint() 方法中指定了添加新元素的位置但 set 容器为了保持数据的有序状态可能会移动其位置。个人觉得没啥意义 #include set #include string #include iostreamusing namespace std;int main() {//1、emplace()方法插入数据/ 语法格式如下template class… Argspairiterator,bool emplace (Args… args);另外该方法的返回值类型为 pair 类型其包含 2 个元素一个迭代器和一个 bool 值当该方法将目标元素成功添加到 set 容器中时其返回的迭代器指向新插入的元素同时 bool 值为 true当添加失败时则表明原 set 容器中已存在相同值的元素此时返回的迭代器指向容器中具有相同键的这个元素同时 bool 值为 false。*/std::setstring myset;pairsetstring,string::iterator, bool ret myset.emplace(aa);cout ret.first- *(ret.first) , ret.second- ret.second endl;cout myset.size(): myset.size() endl;//2、emplace_hint()的用法//注: 注意和 insert() 方法一样虽然 emplace_hint() 方法中指定了添加新元素的位置但 set 容器为了保持数据的有序状态可能会移动其位置。所以没啥意义/语法格式如下template class… Argsiterator emplace_hint (const_iterator position, Args… args);和emplace()相比有一下2点不同:该方法需要额外传入一个迭代器用来指明新元素添加到 set 容器的具体位置新元素会添加到该迭代器指向元素的前面返回值是一个迭代器而不再是 pair 对象。当成功添加元素时返回的迭代器指向新添加的元素反之如果添加失败则迭代器就指向 set 容器和要添加元素的值相同的元素。/cout endl;setstring::iterator iter myset.emplace_hint(myset.begin(), gg);cout *iter endl;cout myset.size() myset.size() endl;for(auto elem: myset){cout elem endl;} } 4.3.7、set删除数据erase()/clear() 如果想删除 set 容器存储的元素可以选择用 erase() 或者 clear() 成员方法。   1、set 类模板中erase() 方法有 3 种语法格式分别如下 1删除 set 容器中值为 val 的元素 size_type erase (const value_type val); 2删除 position 迭代器指向的元素 iterator  erase (const_iterator position); 3删除 [first,last) 区间内的所有元素 iterator  erase (const_iterator first, const_iterator last); 其中第 1 种格式的 erase() 方法其返回值为一个整数表示成功删除的元素个数 后 2 种格式的 erase() 方法返回值都是迭代器其指向的是 set 容器中删除元素之后的第一个元素。 注意如果要删除的元素就是 set 容器最后一个元素则 erase() 方法返回的迭代器就指向新 set 容器中最后一个元素之后的位置等价于 end() 方法返回的迭代器。 2、如果要清空整个set使用clear()方法 #include set #include string #include iostreamusing namespace std;void print_set(setstring myset){for(auto elem: myset){cout elem endl;}cout endl; }int main() {//一、set的erase方法删除数据setstring myset;myset.emplace(aa);myset.emplace(bb);myset.emplace(cc);myset.emplace(dd);myset.emplace(dd);myset.emplace(ee);myset.emplace(ff);myset.emplace(gg);cout myset.size: myset.size() endl; print_set(myset);//1、删除set容器中值为val的元素/删除 set 容器中值为 val 的元素size_type erase (const value_type val);返回: 返回值为一个整数表示成功删除的元素个数/int num myset.erase(cc);cout num: num endl;cout 1.myset.size: myset.size() endl;cout endl;//print_set(myset);//2、删除pos迭代器指向的元素/删除 position 迭代器指向的元素iterator erase (const_iterator position);返回: 返回值都是迭代器其指向的是 set 容器中删除元素之后的第一个元素/setstring::iterator iter1 myset.erase(myset.begin());cout 2.myset.size(): myset.size() endl;cout 2.*iter1 *iter1 endl;cout endl;//print_set(myset);//3、删除[first,last]区间内的所有元素/删除 [first,last) 区间内的所有元素iterator erase (const_iterator first, const_iterator last);返回: 返回值都是迭代器其指向的是 set 容器中删除元素之后的第一个元素/setstring::iterator iter2 myset.erase(myset.begin(), –myset.end());cout 3.myset.size(): myset.size() endl;cout *iter2 *iter2 endl;cout endl;//print_set(myset);//二、set的clear方法情况所有元素myset.clear();cout 4.myset.size(): myset.size() endl; } 输出如下 myset.size:7 aa bb cc dd ee ff ggnum:1 1.myset.size:62.myset.size():5 2.*iter1bb3.myset.size():1 *iter2gg4.myset.size():0 4.4、 multiset 前面章节中对 set 容器做了详细的讲解。回忆一下set 容器具有以下几个特性 不再以键值对的方式存储数据因为 set 容器专门用于存储键和值相等的键值对因此该容器中真正存储的是各个键值对的值valueset 容器在存储数据时会根据各元素值的大小对存储的元素进行排序默认做升序排序存储到 set 容器中的元素虽然其类型没有明确用 const 修饰但正常情况下它们的值是无法被修改的set 容器存储的元素必须互不相等。 在此基础上C STL 标准库中还提供有一个和 set 容器相似的关联式容器即 multiset 容器。所谓“相似”是指 multiset 容器遵循 set 容器的前 3 个特性仅在第 4 条特性上有差异。和 set 容器不同的是multiset 容器可以存储多个值相同的元素。 也就是说multiset 容器和 set 容器唯一的差别在于 multiset 容器允许存储多个值相同的元素而 set 容器中只能存储互不相同的元素。 #include set 4.4.1、multiset构造函数 multiset 类模板提供的构造函数和 set 类模板中提供创建 set 容器的构造函数是完全相同的。这意味着创建 set 容器的方式也同样适用于创建 multiset 容器。 4.4.2、multiset常用成员函数 multiset 容器提供的成员方法和 set 容器提供的完全一样如表 1 所示。   表 1 C multiset 容器常用成员方法 成员方法功能begin()返回指向容器中第一个注意是已排好序的第一个元素的双向迭代器。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。end()返回指向容器最后一个元素注意是已排好序的最后一个所在位置后一个位置的双向迭代器通常和 begin() 结合使用。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。rbegin()返回指向最后一个注意是已排好序的最后一个元素的反向双向迭代器。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。rend()返回指向第一个注意是已排好序的第一个元素所在位置前一个位置的反向双向迭代器。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的反向双向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。cend()和 end() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crbegin()和 rbegin() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。crend()和 rend() 功能相同只不过在其基础上增加了 const 属性不能用于修改容器内存储的元素值。find(val)在 multiset 容器中查找值为 val 的元素如果成功找到则返回指向该元素的双向迭代器反之则返回和 end() 方法一样的迭代器。另外如果 multiset 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。lower_bound(val)返回一个指向当前 multiset 容器中第一个大于或等于 val 的元素的双向迭代器。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。upper_bound(val)返回一个指向当前 multiset 容器中第一个大于 val 的元素的迭代器。如果 multiset 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。equal_range(val)该方法返回一个 pair 对象包含 2 个双向迭代器其中 pair.first 和 lower_bound() 方法的返回值等价pair.second 和 upper_bound() 方法的返回值等价。也就是说该方法将返回一个范围该范围中包含所有值为 val 的元素。empty()若容器为空则返回 true否则 false。size()返回当前 multiset 容器中存有元素的个数。max_size()返回 multiset 容器所能容纳元素的最大个数不同的操作系统其返回值亦不相同。insert()向 multiset 容器中插入元素。erase()删除 multiset 容器中存储的指定元素。swap()交换 2 个 multiset 容器中存储的所有元素。这意味着操作的 2 个 multiset 容器的类型必须相同。clear()清空 multiset 容器中所有的元素即令 multiset 容器的 size() 为 0。emplace()在当前 multiset 容器中的指定位置直接构造新元素。其效果和 insert() 一样但效率更高。emplace_hint()本质上和 emplace() 在 multiset 容器中构造新元素的方式是一样的不同之处在于使用者必须为该方法提供一个指示新元素生成位置的迭代器并作为该方法的第一个参数。count(val)在当前 multiset 容器中查找值为 val 的元素的个数并返回。 注意虽然 multiset 容器和 set 容器拥有的成员方法完全相同但由于 multiset 容器允许存储多个值相同的元素因此诸如 count()、find()、lower_bound()、upper_bound()、equal_range()等方法更常用于 multiset 容器。 #include set #include iostream #include stringusing namespace std;void print_multiset(multisetstring mymultiset){for(auto elem:mymultiset){cout elem ;}cout endl; }int main() {//一、multiset构造函数//1默认构造函数(默认采用 std::lessT 规则,升序排列)std::multisetstring mymultiset1;//2)创建变量的同时初始化std::multisetstring mymultiset2{aa,bb,cc,dd,ee,cc};cout mymultiset2:;print_multiset(mymultiset2);//3) 还提供了拷贝(复制)构造函数std::multisetstring mymultiset3(mymultiset2);cout mymultiset3:;print_multiset(mymultiset3);//4)在3的基础上,multiset还支持利用已有multiset容器的部元素来初始化multiset容器std::multisetstring mymultiset4(mymultiset3.begin(), mymultiset3.end());cout mymultiset4:;print_multiset(mymultiset4);//5)修改排序规则为 std::greaterTstd::multisetstring, std::greaterstring mymultiset5{aa,bb,cc,dd,dd,ee};cout mymultiset5:;for(auto elem: mymultiset5){cout elem ;}cout endl;//二、multiset常用成员函数cout mymultiset5.size(): mymultiset5.size() endl;cout mymultiset5.count(dd): mymultiset5.count(dd) endl;//添加元素ffmymultiset5.emplace(ff);//删除所有值为dd的元素int num mymultiset5.erase(dd);cout 删除了 num 个值为 dd 的元素 endl;for (auto iter mymultiset5.begin(); iter ! mymultiset5.end(); iter){cout *iter ;}cout endl; } 输出如下 mymultiset2:aa bb cc cc dd ee mymultiset3:aa bb cc cc dd ee mymultiset4:bb cc cc dd ee mymultiset5:ee dd dd cc bb aa mymultiset5.size():6 mymultiset5.count(dd):2 删除了 2 个值为 dd 的元素 ff ee cc bb aa 4.5、 C STL关联容器排序规则 4.5.0、函数对象(仿函数)   1概念 重载函数调用操作符()的类其对象称为函数对象 函数对象使用重载时的行为类似于函数调用,所以也叫仿函数。 注关于这块看个具体的例子就知道了。 简单来说就是有一个类将 () 运算符重载为成员函数了那么这个类就称为函数对象类、这个类的对象就是函数对象。函数对象本质上是一个对象但是使用的形式看起来特别像是函数调用因此也被称为仿函数。 本质 函数对象(仿函数)实际上是类、是对象不是一个函数。 2函数对象使用举例   case1函数对象基本使用举例   #include iostream #include stringusing namespace std;class CAverage { public://重载 () 运算符double operator() (int a, int b, int c){return (double)(a b c)/3;} };int main() {CAverage average;cout average(1, 2, 4): average(1, 2, 4) endl; }可以看到 (1) 函数对象在使用时,可以像普通函数那样调用,可以有参数,可以有返回值 (2) average(3, 2, 3)这种用法,使得average看上去像函数的名字,所以称其为函数对象。 case2函数对象在sort算法中的应用 STL中sort能将区间从小到大排序。sort算法有两个版本一个是默认、另一个是自定义排序规则。 template class_Randlt void sort(_Randlt first, _RandIt last); 该模板可以用来将区间 [first, last) 中的元素从小到大排序要求 first、last 是随机访问迭代器。元素比较大小是用进行的。如果表达式ab的值为 true则 a 排在 b 前面如果ab的值为 false则 b 未必排在 a 前面还要看ba是否成立成立的话 b 才排在 a 前面。要使用这个版本的 sort 算法待排序的对象必须能用运算符进行比较。 template class_Randlt, class Pred void sort(_Randlt first, _RandIt last, Pred op); 这个版本和第一个版本的差别在于元素 a、b 比较大小是通过表达式op(a, b)进行的。如果该表达式的值为 true则 a 比 b 小如果该表达式的值为 false也不能认为 b 比 a 小还要看op(b, a)的值。总之op 定义了元素比较大小的规则。下面是一个使用 sort 算法的例子。   #include iostream #include algorithm #include string #include ostreamusing namespace std;//首先定义一个打印函数,用模板实现 templatetypename T void PrintInterval(T first, T last){//用以输出[first, last)区间的元素for(; first!last; first){cout first ;}cout endl; }//定义一个类A class CTest { public://成员函数int v;//定义构造函数CTest(int n):v(n) {} };//重载 操作符 bool operator (const CTest o1, const CTest o2){return o1.v o2.v; }//为sort定义一个排序规则 bool GreaterRule(const CTest o1, const CTest o2){//v值大的元素作为较小的数return (o1.v o2.v); }//定义一个函数对象 struct LessTest {bool operator() (const CTest o1, const CTest o2){//v个位数小的元素就作为较小的数return (o1.v % 10) (o2.v % 10);} };//重载()运算符;此处用于在自定义类中方便输出对象内容 ostream operator (ostream o, const CTest obj) {o obj.v;return o; }int main() {CTest obj[5] {5, 8, 10, 3, 6};sort(obj, obj5);cout 1); PrintInterval(obj, obj 5); sort(obj, obj5, GreaterRule);cout 2); PrintInterval(obj, obj 5); sort(obj, obj5, LessTest());cout 3); PrintInterval(obj, obj 5); } 输出如下 1)3 5 6 8 10 2)3 5 6 8 10 3)10 3 5 6 8 编译至第 2 个sort时编译器将 sort 实例化得到的函数原型如下 void sort(A first, A* last, bool (op)(const A , const A ) ); 该函数在执行过程中当要比较两个元素 a、b 的大小时就是看 op(a, b) 和 op(b, a) 的返回值。本程序中 op 指向 GreaterA,因此就用 GreaterA 定义的规则来比较大小。 编译至第 3 个sort时编译器将 sort 实例化得到的函数原型如下 void sort( A first, A* last, LessA op); 该函数在执行过程中当要比较两个元素 a、b 的大小时就是看 op(a, b) 和 op(b, a) 的返回值。本程序中op(a, b) 等价于 op.opeartor(a, b)因此就用 LessA 定义的规则来比较大小。 4.5.1、使用函数对象自定义关联容器的排序规则   #include iostream #include set #include stringusing namespace std;//1、定义函数对象类 class cmp1{public://重载()运算符bool operator() (const string a, const string b){//按照字符长度进行排序return (a.length() b.length());} };//2、定义函数对象类(struct关键字) struct cmp2{bool operator() (const string a, const string b){//按照字符串的长度进行排序return (a.length() b.length());} };//3、模板类 templatetypename T class cmp3{public:bool operator() (const T a, const T b){//按照值的大小进行排序return a b;} };int main() {std::setstring, cmp1 myset1{aa,bbbbbbb,c,ddd};cout 1、class函数对象类按照字符长度排序: ;for (auto iter myset1.begin(); iter! myset1.end(); iter){cout *iter ;}cout endl;std::setstring, cmp2 myset2{aa,bbbbbbb,c,ddd};cout 2、struct函数对象类按照字符长度排序:;for (auto iter myset1.begin(); iter! myset1.end(); iter){cout *iter ;}cout endl;std::setstring, cmp3string myset3{aa,bbbbbb,c,ddd};cout 3、模板函数对象类按照值大小排序;for (auto iter myset3.begin(); iter ! myset3.end(); iter){cout *iter ;}cout endl;} 输出如下 1、class函数对象类按照字符长度排序:c aa ddd bbbbbbb 2、struct函数对象类按照字符长度排序:c aa ddd bbbbbbb 3、模板函数对象类按照值大小排序aa bbbbbb c ddd 4.5.2、重载关系运算符实现自定义排序 在STL标准库中本身就包含几个内置的排序规则如下表所示 排序规则功能std::less底层采用 运算符实现升序排序各关联式容器默认采用的排序规则。std::greater底层采用 运算符实现降序排序同样适用于各个关联式容器。std::less_equal底层采用 运算符实现升序排序多用于 multimap 和 multiset 容器。std::greater_equal底层采用 运算符实现降序排序多用于 multimap 和 multiset 容器。 值得注意的是表中的这些排序规则其底层也是采用函数对象的方式实现的。以 std::less 为例其底层实现为 template typename T struct less {//定义新的排序规则bool operator()(const T _lhs, const T _rhs) const {return _lhs _rhs;} }在此基础上当关联式容器中存储的数据类型为自定义的结构体变量或者类对象时通过对现有排序规则中所用的关系运算符进行重载也能实现自定义排序规则的目的。 注意当关联式容器中存储的元素类型为结构体指针变量或者类的指针对象时只能使用函数对象的方式自定义排序规则此方法不再适用。 对于如下程序  #include iostream #include string #include setusing namespace std;class myString{ public:myString(string tmpStr): str(tmpStr){};string getStr() const; private:string str; };string myString::getStr() const{return this-str; }bool operator (const myString str1, const myString str2){//以字符串长度为标准进行排序return (str1.getStr().length() str2.getStr().length()); }int main() {std::setmyString myset;//插入后会自动调用myString类的构造函数myset.emplace(aaaaa);myset.emplace(bbbb);myset.emplace(dd);myset.emplace(eeeeeeee);for(auto iter myset.begin(); iter! myset.end(); iter){cout iter-getStr() endl;} } 输出如下 dd bbbb aaaaa eeeeeeee 分析 在这个程序中虽然myset容器表面扔采用默认的 std::less 排序规则但是由于我们对于所使用的 运算符进行重载是的myset容器内部实则是以字符串的长度为基准对各个myString类对象进行排序。 4.6、 如何修改关联式容器中键值对的键 通过前面的学习已经掌握了所有关联式容器包括 map、multimap、set 和 multiset的特性和用法。其中需要指出的是对于如何修改容器中某个键值对的键所有关联式容器可以采用同一种解决思路即先删除该键值对然后再向容器中添加修改之后的新键值对。 那么是否可以不删除目标键值对而直接修改它的键呢接下来就围绕此问题给读者展开详细的讲解。 4.6.1、map/multimap不可修改键值对的键 首先可以明确的是map 和 multimap 容器只能采用“先删除再添加”的方式修改某个键值对的键。原因很简单C STL 标准中明确规定map 和 multimap 容器用于存储类型为 pairconst K, V 的键值对。显然只要目标键值对存储在当前容器中键的值就无法被修改。 mapint, int mymap{ {1,10},{2,20} }; //map 容器的键为 const 类型不能被修改 mymap.begin()-first 100; multimapint, int mymultimap{ {10,100},{20,200} }; //multimap 容器的键为 const 类型同样不能被修改 mymultimap.begin()-first 100;上述第3行和第7行尝试修改键的程序都是不能通过编译的。 4.6.2、set/multiset借助const_cast可以修改键 和 map、multimap 不同C STL 标准中并没有用 const 限定 set 和 multiset 容器中存储元素的类型。换句话说对于 set 或者 multiset 类型的容器其存储元素的类型是 T 而不是 const T。 事实上对 set 和 multiset 容器中的元素类型作 const 修饰是违背常理的。举个例子假设我们使用 set 容器存储多个学生信息如下是一个表示学生的类 class student { public:student(string name, int id, int age) :name(name), id(id), age(age) {}const int getid() const {return id;}void setname(const string name){this-name name;}string getname() const{return name;}void setage(int age){this-age age;}int getage() const{return age;} private:string name;int id;int age; };在创建 set 容器之前我们还需要为其设计一个排序规则这里假定以每个学生的 id 做升序排序其排序规则如下 class cmp { public:bool operator ()(const student stua, const student stub) {//按照字符串的长度做升序排序(即存储的字符串从短到长)return stua.getid() stub.getid();} };做完以上所有的准备工作后就可以创建一个可存储 student 对象的 set 容器了比如 setstudent, cmp myset{ {zhangsan,10,20},{lisi,20,21},{wangwu,15,19} };实际存储数据如下 {“zhangsan”,10,20} {“wangwu”,15,19} {“lisi”,20,21} 注意set 容器中每个元素也可以看做是键和值相等的键值对但对于这里的 myset 容器来说其实每个 student 对象的 id 才是真正的键其它信息name 和 age只不过是和 id 绑定在一起而已。因此在不破坏 myset 容器中元素的有序性的前提下即不修改每个学生的 id学生的其它信息是应该允许修改的但有一个前提即 myset 容器中存储的各个 student 对象不能被 const 修饰这也是 set 容器中的元素类型不能被 const 修饰的原因。 例如在已创建好的 myset 容器的基础上如下代码尝试修改 myset 容器中某个学生的 name 名字 setstudent::iterator iter mymap.begin(); (*iter).setname(xiaoming);注意如果读者运行代码会发现它也是无法通过编译的。 虽然 C STL 标准没有用 const 修饰 set 或者 multiset 容器中元素的类型但也做了其它工作来限制用户修改容器的元素。例如上面代码中iter 会调用 operator其返回的是一个 const T 类型元素。这意味着C STL 标准不允许用户借助迭代器来直接修改 set 或者 multiset 容器中的元素。 那么如何才能正确修改 set 或 multiset 容器中的元素呢最直接的方式就是借助 const_cast 运算符该运算符可以去掉指针或者引用的 const 限定符。 比如我们只需要借助 const_cast 运算符对上面程序稍作修改就可以运行成功 setstudent::iterator iter mymap.begin(); const_caststudent(*iter).setname(xiaoming);5、无序关联式容器(unordered_map/set/multimap/multiset)-哈希表 5.0、无序关联式容器介绍 5.0.1、什么是无序关联式容器 继 map、multimap、set、multiset 关联式容器之后本节再讲解一类“特殊”的关联式容器它们常被称为“无序容器”、“哈希容器”或者“无序关联容器”。 和关联式容器一样无序容器也使用键值对pair 类型的方式存储数据。不过本教程将二者分开进行讲解因为它们有本质上的不同 关联式容器的底层实现采用的树存储结构更确切的说是红黑树结构无序容器的底层实现采用的是哈希表的存储结构。 C STL 底层采用哈希表实现无序容器时会将所有数据存储到一整块连续的内存空间中并且当数据存储位置发生冲突时解决方法选用的是“链地址法”又称“开链法”。有关哈希表存储结构读者可阅读《哈希表(散列表)详解》一文做详细了解。 基于底层实现采用了不同的数据结构因此和关联式容器相比无序容器具有以下 2 个特点 无序容器内部存储的键值对是无序的各键值对的存储位置取决于该键值对中的键和关联式容器相比无序容器擅长通过指定键查找对应的值平均时间复杂度为 O(1)但对于使用迭代器遍历容器中存储的元素无序容器的执行效率则不如关联式容器。 和关联式容器一样无序容器只是一类容器的统称其包含有 4 个具体容器分别为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。 表 1 对这 4 种无序容器的功能做了详细的介绍。   表 1 无序容器种类 无序容器功能unordered_map 存储键值对 key, value 类型的元素其中各个键值对键的值不允许重复且该容器中存储的键值对是无序的。unordered_multimap和 unordered_map 唯一的区别在于该容器允许存储多个键相同的键值对。unordered_set不再以键值对的形式存储数据而是直接存储数据元素本身当然也可以理解为该容器存储的全部都是键 key 和值 value 相等的键值对正因为它们相等因此只存储 value 即可。另外该容器存储的元素不能重复且容器内部存储的元素也是无序的。unordered_multiset和 unordered_set 唯一的区别在于该容器允许存储值相同的元素。 可以看到实际上就是前面学过的 map、multimap、set、multiset前面在加上unordered。 5.0.2、如何选择无序容器和关联式容器 总的来说如果实际场景涉及大量遍历容器的操作首选关联式容器反之如果如果更多是根据键获取对应的值则应首选无序容器。 5.1、 unordered_map 5.1.1、unordered_map简介 不废话就理解成无序的map容器。 ps unordered_map和map一样键也是不能相等的(注:能相等就是 multimap 了)。 #include unordered_map unordered_map容器模板的定义如下所示 template class Key, //键值对中键的类型class T, //键值对中值的类型class Hash hashKey, //容器内部存储键值对所用的哈希函数class Pred equal_toKey, //判断各个键值对键相同的规则class Alloc allocator pairconst Key,T // 指定分配器对象的类型 class unordered_map; 以上 5 个参数中必须显式给前 2 个参数传值并且除特殊情况外最多只需要使用前 4 个参数各自的含义和功能如表 1 所示。   表 1 unordered_map 容器模板类的常用参数 参数含义key,T前 2 个参数分别用于确定键值对中键和值的类型也就是存储键值对的类型。Hash hashKey用于指明容器在存储各个键值对时要使用的哈希函数默认使用 STL 标准库提供的 hashkey 哈希函数。注意默认哈希函数只适用于基本数据类型包括 string 类型而不适用于自定义的结构体或者类。Pred equal_toKey要知道unordered_map 容器中存储的各个键值对的键是不能相等的而判断是否相等的规则就由此参数指定。默认情况下使用 STL 标准库中提供的 equal_tokey 规则该规则仅支持可直接用 运算符做比较的数据类型。 总的来说当无序容器中存储键值对的键为自定义类型时默认的哈希函数 hash 以及比较函数 equal_to 将不再适用只能自己设计适用该类型的哈希函数和比较函数并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义后续章节会做详细讲解。 5.1.2、创建unordered_map容器的方法 #include unordered_map #include string #include iostreamusing namespace std;void print_umap(unordered_mapstring, string umap) {for (auto elem : umap){cout elem.first : elem.second endl;}cout endl; }int main() {//一、看看创建 unordered_map 容器的几种方法//1. 调用unordered_map的默认构造函数,创建空的 unordered_map 容器。std::unordered_mapstring, string umap1;print_umap(umap1);//2. 在创建unordered_map的同时完成是实话std::unordered_mapstring, string umap2{{chinese, 97},{math, 100},{english, 93},{pe, 100}};//注:我觉得这个最好用umap2[chemistry] 92;print_umap(umap2);//3. 拷贝构造函数初始化std::unordered_mapstring, string umap3(umap2);print_umap(umap3);//4. 如果不想全拷贝可以使用unordered_map提供的迭代器,选择现有umap容器中的部分区域内的键值对初始化新的umapstd::unordered_mapstring, string umap4(umap2.begin(), umap2.end());print_umap(umap4);//输出 umpa 存储键值对的数量cout umap4 size: umap4.size() endl;for (unordered_mapstring, string::iterator iter umap4.begin(); iter ! umap4.end(); iter){cout iter-first : iter-second endl;}cout endl;//find()的用法string target_key chinese;unordered_mapstring, string::iterator iter umap4.find(target_key);if (iter umap4.end()){cout no target_key endl;}else{cout have target_key endl;} }5.1.3、unordered_map容器成员函数 unordered_map 既可以看做是关联式容器更属于自成一脉的无序容器。因此在该容器模板类中既包含一些在学习关联式容器时常见的成员方法还有一些属于无序容器特有的成员方法。 表 2 列出了 unordered_map 类模板提供的所有常用的成员方法以及各自的功能。   表 2 unordered_map类模板成员方法 成员方法功能begin()返回指向容器中第一个键值对的正向迭代器。end() 返回指向容器中最后一个键值对之后位置的正向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。cend()和 end() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。empty()若容器为空则返回 true否则 false。size()返回当前容器中存有键值对的个数。max_size()返回容器所能容纳键值对的最大个数不同的操作系统其返回值亦不相同。operator[key]该模板类中重载了 [] 运算符其功能是可以向访问数组中元素那样只要给定某个键值对的键 key就可以获取该键对应的值。注意如果当前容器中没有以 key 为键的键值对则其会使用该键向当前容器中插入一个新键值对。at(key)返回容器中存储的键 key 对应的值如果 key 不存在则会抛出 out_of_range 异常。 find(key)查找以 key 为键的键值对如果找到则返回一个指向该键值对的正向迭代器反之则返回一个指向容器中最后一个键值对之后位置的迭代器如果 end() 方法返回的迭代器。count(key)在容器中查找以 key 键的键值对的个数。equal_range(key)返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中键为 key 的键值对所在的范围。emplace()向容器中添加新键值对效率比 insert() 方法高。emplace_hint()向容器中添加新键值对效率比 insert() 方法高。insert() 向容器中添加新键值对。erase()删除指定键值对。clear() 清空容器即删除容器中存储的所有键值对。swap()交换 2 个 unordered_map 容器存储的键值对前提是必须保证这 2 个容器的类型完全相等。bucket_count()返回当前容器底层存储键值对时使用桶一个线性链表代表一个桶的数量。max_bucket_count()返回当前系统中unordered_map 容器底层最多可以使用多少桶。bucket_size(n)返回第 n 个桶中存储键值对的数量。bucket(key)返回以 key 为键的键值对所在桶的编号。load_factor()返回 unordered_map 容器中当前的负载因子。负载因子指的是的当前容器中存储键值对的数量size()和使用桶数bucket_count()的比值即 load_factor() size() / bucket_count()。max_load_factor()返回或者设置当前 unordered_map 容器的负载因子。rehash(n)将当前容器底层使用桶的数量设置为 n。reserve()将存储桶的数量也就是 bucket_count() 方法的返回值设置为至少容纳count个元不超过最大负载因子所需的数量并重新整理容器。hash_function()返回当前容器使用的哈希函数对象。 5.1.4、unordered_map迭代器的用法 C STL 标准库中unordered_map 容器迭代器的类型为前向迭代器又称正向迭代器。这意味着假设 p 是一个前向迭代器则其只能进行 *p、p、p 操作且 2 个前向迭代器之间只能用 和 ! 运算符做比较。 在 unordered_map 容器模板中提供了表 1 所示的成员方法可用来获取指向指定位置的前向迭代器。   表 1 C unordered_map迭代器相关成员方法 成员方法功能begin()返回指向容器中第一个键值对的正向迭代器。end() 返回指向容器中最后一个键值对之后位置的正向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。cend()和 end() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。find(key)查找以 key 为键的键值对如果找到则返回一个指向该键值对的正向迭代器反之则返回一个指向容器中最后一个键值对之后位置的迭代器如果 end() 方法返回的迭代器。equal_range(key)返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中键为 key 的键值对所在的范围。 值得一提的是equal_range(key) 很少用于 unordered_map 容器因为该容器中存储的都是键不相等的键值对即便调用该成员方法得到的 2 个迭代器所表示的范围中最多只包含 1 个键值对。事实上该成员方法更适用于 unordered_multimap 容器该容器后续章节会做详细讲解。 5.1.5、unordered_map获取元素的四种方法 ①[] ②at() ③find() ④begin()/end()完整遍历 #include unordered_map #include string #include iostreamusing namespace std;void print_umap(unordered_mapstring, string umap) {for (auto elem : umap){cout elem.first : elem.second endl;}cout endl; }int main() {// unordered_map获取元素的四种方法 ①[] ②at() ③find() ④begin()/end()完整遍历std::unordered_mapstring, string umap{{chinese, 97},{math, 100},{english, 93},{pe, 100}};umap[chemistry] 92;print_umap(umap);//①[]cout umap[\math]: umap[math] endl;//②at()cout umap.at(\math): umap.at(math) endl;//③find()//前面演示过了,此处不在演示//④begin()/end()或cbegin()/cend() 完整遍历//没啥意思,不在演示 }5.1.6、unordered_map删除元素的方法 C STL 标准库为了方便用户可以随时删除 unordered_map 容器中存储的键值对unordered_map 容器类模板中提供了以下 2 个成员方法 erase()删除 unordered_map 容器中指定的键值对clear()删除 unordered_map 容器中所有的键值对即清空容器。 为了满足不同场景删除 unordered_map 容器中键值对的需要此容器的类模板中提供了 3 种语法格式的 erase() 方法。 1erase() 方法可以接受一个正向迭代器并删除该迭代器指向的键值对。该方法的语法格式如下 iterator erase ( const_iterator position ); 其中 position 为指向容器中某个键值对的迭代器该方法会返回一个指向被删除键值对之后位置的迭代器。 2我们还可以直接将要删除键值对的键作为参数直接传给 erase() 方法该方法会自行去 unordered_map 容器中找和给定键相同的键值对将其删除。erase() 方法的语法格式如下 size_type erase ( const key_type k ); 其中k 表示目标键值对的键的值该方法会返回一个整数其表示成功删除的键值对的数量。 3除了支持删除 unordered_map 容器中指定的某个键值对erase() 方法还支持一次删除指定范围内的所有键值对其语法格式如下 iterator erase ( const_iterator first, const_iterator last ); 其中 first 和 last 都是正向迭代器[first, last) 范围内的所有键值对都会被 erase() 方法删除同时该方法会返回一个指向被删除的最后一个键值对之后一个位置的迭代器。 #include unordered_map #include string #include iostreamusing namespace std;void print_umap(unordered_mapstring, string umap) {for (auto elem : umap){cout elem.first : elem.second endl;}cout endl; }int main() {/unordered_map删除元素。1、erase()删除 unordered_map 容器中指定的键值对2、clear()删除 unordered_map 容器中所有的键值对即清空容器。/std::unordered_mapstring, string umap{{chinese, 97},{math, 100},{english, 93},{pe, 100}};umap[chemistry] 92;print_umap(umap);//第一种erase()方法: 指定迭代器进行删除//定义一个接受erase()方法的迭代器unordered_mapstring, string::iterator ret;//删除容器中的第一个键值对ret umap.erase(umap.begin());//输出下retcout ret ret-first ret-second endl;cout endl;cout after erase(umap.begin()) endl endl;print_umap(umap);//第二种erase()方法: 将要删除的键值对的键作为参数直接传给erase()方法int delNum umap.erase(math);cout delNum: delNum endl;print_umap(umap);//第三种erase()方法: 根据迭代器范围删除auto iter umap.erase(umap.begin(), umap.end());cout umap.size(): umap.size() endl;print_umap(umap);//2、clear()方法umap.clear();cout after clear, umap.size(): umap.size() endl; }5.1.2、unordered_map成员函数 5.2、 unordered_multimap 5.2.1、unordered_multimap简介 C STL 标准库中除了提供有 unordered_map 无序关联容器还提供有和 unordered_map 容器非常相似的 unordered_multimap 无序关联容器。 和 unordered_map 容器一样unordered_multimap 容器也以键值对的形式存储数据且底层也采用哈希表结构存储各个键值对。两者唯一的不同之处在于unordered_multimap 容器可以存储多个键相等的键值对而 unordered_map 容器不行。 另外值得一提得是STL 标准库中实现 unordered_multimap 容器的模板类并没有定义在以自己名称命名的头文件中而是和 unordered_map 容器一样定义在unordered_map头文件且位于 std 命名空间中。因此在使用 unordered_multimap 容器之前程序中应包含如下 2 行代码 #include unordered_mapusing namespace std; unordered_multimap 容器模板的定义如下所示 template class Key, //键key的类型class T, //值value的类型class Hash hashKey, //底层存储键值对时采用的哈希函数class Pred equal_toKey, //判断各个键值对的键相等的规则class Alloc allocator pairconst Key,T // 指定分配器对象的类型 class unordered_multimap; 以上 5 个参数中必须显式给前 2 个参数传值且除极个别的情况外最多只使用前 4 个参数它们各自的含义和功能如表 1 所示。   表 1 unordered_multimap 容器模板类的常用参数 参数含义key,T前 2 个参数分别用于确定键值对中键和值的类型也就是存储键值对的类型。Hash hashKey用于指明容器在存储各个键值对时要使用的哈希函数默认使用 STL 标准库提供的 hashkey 哈希函数。注意默认哈希函数只适用于基本数据类型包括 string 类型而不适用于自定义的结构体或者类。Pred equal_toKeyunordered_multimap 容器可以存储多个键相等的键值对而判断是否相等的规则由此参数指定。默认情况下使用 STL 标准库中提供的 equal_tokey 规则该规则仅支持可直接用 运算符做比较的数据类型。 注意当 unordered_multimap 容器中存储键值对的键为自定义类型时默认的哈希函数 hashkey 以及比较函数 equal_tokey 将不再适用这种情况下需要我们自定义适用的哈希函数和比较函数并分别显式传递给 Hash 参数和 Pred 参数。 #include unordered_map #include string #include iostreamusing namespace std;void print_ummap( std::unordered_multimapstring, string ummap){for(auto iter ummap.begin(); iter ! ummap.end(); iter){cout iter-first : iter-second endl;}cout endl; }int main() {//一、创建 unordered_multimap 容器//其实和 unordered_map 的几种方法一样//1、std::unordered_multimapstring, string ummap1;ummap1.insert({aa, 11});ummap1.insert({aa, 11});ummap1.insert({bb, 22});print_ummap(ummap1);//2、std::unordered_multimapstring, string ummap2{{aaa, 111},{bbb, 222},{ccc, 333}};print_ummap(ummap2);//3、std::unordered_multimapstring, string ummap3(ummap2);print_ummap(ummap3);//4、std::unordered_multimapstring, string ummap4(ummap3.begin(), ummap3.end());print_ummap(ummap4);} 5.2.2、unordered_multimap成员函数 和 unordered_map 容器相比unordered_multimap 容器的类模板中没有重载 [ ] 运算符也没有提供 at() 成员方法除此之外它们完全一致。 没有提供 [ ] 运算符和 at() 成员方法意味着 unordered_multimap 容器无法通过指定键获取该键对应的值因为该容器允许存储多个键相等的键值对每个指定的键可能对应多个不同的值。 unordered_multimap 类模板提供的成员方法如表 2 所示。     表 2 unordered_multimap类模板成员方法 成员方法功能begin()返回指向容器中第一个键值对的正向迭代器。end() 返回指向容器中最后一个键值对之后位置的正向迭代器。cbegin()和 begin() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。cend()和 end() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。empty()若容器为空则返回 true否则 false。size()返回当前容器中存有键值对的个数。max_size()返回容器所能容纳键值对的最大个数不同的操作系统其返回值亦不相同。find(key)查找以 key 为键的键值对如果找到则返回一个指向该键值对的正向迭代器反之则返回一个指向容器中最后一个键值对之后位置的迭代器如果 end() 方法返回的迭代器。count(key)在容器中查找以 key 键的键值对的个数。equal_range(key)返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中键为 key 的键值对所在的范围。emplace()向容器中添加新键值对效率比 insert() 方法高。emplace_hint()向容器中添加新键值对效率比 insert() 方法高。insert() 向容器中添加新键值对。erase()删除指定键值对。clear() 清空容器即删除容器中存储的所有键值对。swap()交换 2 个 unordered_multimap 容器存储的键值对前提是必须保证这 2 个容器的类型完全相等。bucket_count()返回当前容器底层存储键值对时使用桶一个线性链表代表一个桶的数量。max_bucket_count()返回当前系统中unordered_multimap 容器底层最多可以使用多少桶。bucket_size(n)返回第 n 个桶中存储键值对的数量。bucket(key)返回以 key 为键的键值对所在桶的编号。load_factor()返回 unordered_multimap 容器中当前的负载因子。负载因子指的是的当前容器中存储键值对的数量size()和使用桶数bucket_count()的比值即 load_factor() size() / bucket_count()。max_load_factor()返回或者设置当前 unordered_multimap 容器的负载因子。rehash(n)将当前容器底层使用桶的数量设置为 n。reserve()将存储桶的数量也就是 bucket_count() 方法的返回值设置为至少容纳count个元不超过最大负载因子所需的数量并重新整理容器。hash_function()返回当前容器使用的哈希函数对象。 #include unordered_map #include string #include iostreamusing namespace std;int main() {std::unordered_multimapstring, string ummap1;ummap1.emplace(aaa, 111);ummap1.emplace(bbb, 222);ummap1.emplace(ccc, 333);ummap1.emplace(aaa, 111111);// 输出ummap的cout ummap1.size(): ummap1.size() endl;//范围for语句输出for (auto elem: ummap1){cout elem.first : elem.second endl;} } 输出如下 ummap1.size():4 ccc: 333 aaa: 111 aaa: 111111 bbb: 222 5.3、 unordered_set 5.3.1、unordered_set简介 unordered_set 容器可直译为“无序 set 容器”即 unordered_set 容器和 set 容器很像唯一的区别就在于 set 容器会自行对存储的数据进行排序而 unordered_set 容器不会。 总的来说unordered_set 容器具有以下几个特性 不再以键值对的形式存储数据而是直接存储数据的值容器内部存储的各个元素的值都互不相等且不能被修改。不会对内部存储的数据进行排序这和该容器底层采用哈希表结构存储数据有关可阅读《C STL无序容器底层实现原理》一文做详细了解 对于 unordered_set 容器不以键值对的形式存储数据读者也可以这样认为即 unordered_set 存储的都是键和值相等的键值对为了节省存储空间该类容器在实际存储时选择只存储每个键值对的值。 #include unordered_set using namespace std; unordered_set 容器的类模板定义如下 template class Key, //容器中存储元素的类型class Hash hashKey, //确定元素存储位置所用的哈希函数class Pred equal_toKey, //判断各个元素是否相等所用的函数class Alloc allocatorKey //指定分配器对象的类型 class unordered_set; 可以看到以上 4 个参数中只有第一个参数没有默认值这意味着如果我们想创建一个 unordered_set 容器至少需要手动传递 1 个参数。事实上在 99% 的实际场景中最多只需要使用前 3 个参数各自含义如表 1 所示最后一个参数保持默认值即可。   表 1 unordered_set模板类定义 参数含义Key确定容器存储元素的类型如果读者将 unordered_set 看做是存储键和值相同的键值对的容器则此参数则用于确定各个键值对的键和值的类型因为它们是完全相同的因此一定是同一数据类型的数据。Hash hashKey指定 unordered_set 容器底层存储各个元素时所使用的哈希函数。需要注意的是默认哈希函数 hashKey 只适用于基本数据类型包括 string 类型而不适用于自定义的结构体或者类。Pred equal_toKeyunordered_set 容器内部不能存储相等的元素而衡量 2 个元素是否相等的标准取决于该参数指定的函数。 默认情况下使用 STL 标准库中提供的 equal_tokey 规则该规则仅支持可直接用 运算符做比较的数据类型。 注意如果 unordered_set 容器中存储的元素为自定义的数据类型则默认的哈希函数 hashkey 以及比较函数 equal_tokey 将不再适用只能自己设计适用该类型的哈希函数和比较函数并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义后续章节会做详细讲解。 #include unordered_set #include string #include iostreamusing namespace std;void print_uset(std::unordered_setstring uset){for (std::unordered_setstring::iterator iter uset.begin(); iter ! uset.end(); iter){cout *iter endl;}cout endl; }int main() {//一、创建 unordered_set 容器的几张方法//注: 都差不多//1、std::unordered_setstring uset1;uset1.emplace(aaa);uset1.emplace(bbb);print_uset(uset1);//2、std::unordered_setstring uset2{111,222,333,444};print_uset(uset2);//3、std::unordered_setstring uset3(uset2);print_uset(uset3);//4、std::unordered_setstring uset4(uset3.begin(), uset3.end());print_uset(uset4);//cout uset2.size(): uset2.size() endl; } 注意此容器模板类中没有重载 [ ] 运算符也没有提供 at() 成员方法。不仅如此由于 unordered_set 容器内部存储的元素值不能被修改因此无论使用那个迭代器方法获得的迭代器都不能用于修改容器中元素的值。   输出如下 aaa bbb111 222 333 444444 333 222 111222 333 444uset2.size():4 5.3.2、unordered_set成员函数 unordered_set 类模板中提供了如表 2 所示的成员方法。   表 2 unordered_set 类模板成员方法 成员方法功能begin()返回指向容器中第一个元素的正向迭代器。end();返回指向容器中最后一个元素之后位置的正向迭代器。cbegin()和 begin() 功能相同只不过其返回的是 const 类型的正向迭代器。cend()和 end() 功能相同只不过其返回的是 const 类型的正向迭代器。empty()若容器为空则返回 true否则 false。size()返回当前容器中存有元素的个数。max_size()返回容器所能容纳元素的最大个数不同的操作系统其返回值亦不相同。find(key)查找以值为 key 的元素如果找到则返回一个指向该元素的正向迭代器反之则返回一个指向容器中最后一个元素之后位置的迭代器如果 end() 方法返回的迭代器。count(key)在容器中查找值为 key 的元素的个数。equal_range(key)返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中值为 key 的元素所在的范围。emplace()向容器中添加新元素效率比 insert() 方法高。emplace_hint()向容器中添加新元素效率比 insert() 方法高。insert()向容器中添加新元素。erase()删除指定元素。clear()清空容器即删除容器中存储的所有元素。swap()交换 2 个 unordered_set 容器存储的元素前提是必须保证这 2 个容器的类型完全相等。bucket_count()返回当前容器底层存储元素时使用桶一个线性链表代表一个桶的数量。max_bucket_count()返回当前系统中unordered_set 容器底层最多可以使用多少桶。bucket_size(n)返回第 n 个桶中存储元素的数量。bucket(key)返回值为 key 的元素所在桶的编号。load_factor()返回 unordered_set 容器中当前的负载因子。负载因子指的是的当前容器中存储元素的数量size()和使用桶数bucket_count()的比值即 load_factor() size() / bucket_count()。max_load_factor()返回或者设置当前 unordered_set 容器的负载因子。rehash(n)将当前容器底层使用桶的数量设置为 n。reserve()将存储桶的数量也就是 bucket_count() 方法的返回值设置为至少容纳 count 个元不超过最大负载因子所需的数量并重新整理容器。hash_function()返回当前容器使用的哈希函数对象。 5.4、 unordered_multiset 5.4.1、unordered_multiset简介 所谓“类似”指的是 unordered_multiset 容器大部分的特性都和 unordered_set 容器相同包括 unordered_multiset 不以键值对的形式存储数据而是直接存储数据的值该类型容器底层采用的也是哈希表存储结构可阅读《C STL无序容器底层实现原理》一文做详细了解它不会对内部存储的数据进行排序unordered_multiset 容器内部存储的元素其值不能被修改。 和 unordered_set 容器不同的是unordered_multiset 容器可以同时存储多个值相同的元素且这些元素会存储到哈希表中同一个桶本质就是链表上。 读者可以这样认为unordered_multiset 除了能存储相同值的元素外它和 unordered_set 容器完全相同。 另外值得一提的是实现 unordered_multiset 容器的模板类并没有定义在以该容器名命名的文件中而是和 unordered_set 容器共用同一个unordered_set头文件并且也位于 std 命名空间。因此如果程序中需要使用该类型容器应包含如下代码 #include unordered_set using namespace std; unordered_multiset 容器类模板的定义如下 template class Key, //容器中存储元素的类型class Hash hashKey, //确定元素存储位置所用的哈希函数class Pred equal_toKey, //判断各个元素是否相等所用的函数class Alloc allocatorKey //指定分配器对象的类型 class unordered_multiset; 需要说明的是在 99% 的实际场景中最多只需要使用前 3 个参数各自含义如表 1 所示最后一个参数保持默认值即可。 表 1 unordered_multiset 模板类定义 参数含义Key确定容器存储元素的类型如果读者将 unordered_multiset 看做是存储键和值相同的键值对的容器则此参数则用于确定各个键值对的键和值的类型因为它们是完全相同的因此一定是同一数据类型的数据。Hash hashKey指定 unordered_multiset 容器底层存储各个元素时所使用的哈希函数。需要注意的是默认哈希函数 hashKey 只适用于基本数据类型包括 string 类型而不适用于自定义的结构体或者类。Pred equal_toKey用于指定 unordered_multiset 容器判断元素值相等的规则。默认情况下使用 STL 标准库中提供的 equal_tokey 规则该规则仅支持可直接用 运算符做比较的数据类型。 总之如果 unordered_multiset 容器中存储的元素为自定义的数据类型则默认的哈希函数 hashkey 以及比较函数 equal_tokey 将不再适用只能自己设计适用该类型的哈希函数和比较函数并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义后续章节会做详细讲解。 5.4.2、unordered_multiset成员函数 值得一提的是unordered_multiset 模板类中提供的成员方法无论是种类还是数量都和 unordered_set 类模板一样如表 2 所示。   表 2 unordered_multiset 类模板成员方法 成员方法功能begin()返回指向容器中第一个元素的正向迭代器。end();返回指向容器中最后一个元素之后位置的正向迭代器。cbegin()和 begin() 功能相同只不过其返回的是 const 类型的正向迭代器。cend()和 end() 功能相同只不过其返回的是 const 类型的正向迭代器。empty()若容器为空则返回 true否则 false。size()返回当前容器中存有元素的个数。max_size()返回容器所能容纳元素的最大个数不同的操作系统其返回值亦不相同。find(key)查找以值为 key 的元素如果找到则返回一个指向该元素的正向迭代器反之则返回一个指向容器中最后一个元素之后位置的迭代器如果 end() 方法返回的迭代器。count(key)在容器中查找值为 key 的元素的个数。equal_range(key)返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中值为 key 的元素所在的范围。emplace()向容器中添加新元素效率比 insert() 方法高。emplace_hint()向容器中添加新元素效率比 insert() 方法高。insert()向容器中添加新元素。erase()删除指定元素。clear()清空容器即删除容器中存储的所有元素。swap()交换 2 个 unordered_multiset 容器存储的元素前提是必须保证这 2 个容器的类型完全相等。bucket_count()返回当前容器底层存储元素时使用桶一个线性链表代表一个桶的数量。max_bucket_count()返回当前系统中容器底层最多可以使用多少桶。bucket_size(n)返回第 n 个桶中存储元素的数量。bucket(key)返回值为 key 的元素所在桶的编号。load_factor()返回容器当前的负载因子。所谓负载因子指的是的当前容器中存储元素的数量size()和使用桶数bucket_count()的比值即 load_factor() size() / bucket_count()。max_load_factor()返回或者设置当前 unordered_multiset 容器的负载因子。rehash(n)将当前容器底层使用桶的数量设置为 n。reserve()将存储桶的数量也就是 bucket_count() 方法的返回值设置为至少容纳count个元不超过最大负载因子所需的数量并重新整理容器。hash_function()返回当前容器使用的哈希函数对象。 6、 stl容器适配器 6.0、容器适配器介绍 6.0.1、容器适配器概念介绍 容器适配器是一个封装了序列容器的类模板它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类是因为它可以通过适配容器现有的接口来提供不同的功能。 本章将介绍 3 种容器适配器分别是 stack、queue、priority_queue stackT是一个封装了 dequeT 容器的适配器类模板默认实现的是一个后入先出Last-In-First-OutLIFO的压入栈。stackT 模板定义在头文件 stack 中。queueT是一个封装了 dequeT 容器的适配器类模板默认实现的是一个先入先出First-In-First-OutLIFO的队列。可以为它指定一个符合确定条件的基础容器。queueT 模板定义在头文件 queue 中。priority_queueT是一个封装了 vectorT 容器的适配器类模板默认实现的是一个会对元素排序从而保证最大元素总在队列最前面的队列。priority_queueT 模板定义在头文件 queue 中。 在详解什么是容器适配器之前初学者首先要理解适配器的含义。其实容器适配器中的“适配器”和生活中常见的电源适配器中“适配器”的含义非常接近。我们知道无论是电脑、手机还是其它电器充电时都无法直接使用 220V 的交流电为了方便用户使用各个电器厂商都会提供一个适用于自己产品的电源线它可以将 220V 的交流电转换成适合电器使用的低压直流电。         从用户的角度看电源线扮演的角色就是将原本不适用的交流电变得适用因此其又被称为电源适配器。 再举个例子。假设一个代码模块A的构成如下 class A{ public:void f1(){}void f2(){}void f3(){}void f4(){} }; 现在我们需要设计一个模板 B但发现其实只需要组合一下模块 A 中的 f1()、f2()、f3()就可以实现模板 B 需要的功能。其中 f1() 单独使用即可而 f2() 和 f3() 需要组合起来使用如下所示 class B{ private:A * a; public:void g1(){a-f1();}void g2(){a-f2();a-f3();} }; 可以看到就如同是电源适配器将不适用的交流电变得适用一样模板 B 将不适合直接拿来用的模板 A 变得适用了因此我们可以将模板 B 称为 B 适配器。 容器适配器也是同样的道理简单的理解容器适配器其就是将不适用的序列式容器包括 vector、deque 和 list变得适用。容器适配器的底层实现和模板 A、B 的关系是完全相同的即通过封装某个序列式容器并重新组合该容器中包含的成员函数使其满足某些特定场景的需要。 容器适配器本质上还是容器只不过此容器模板类的实现利用了大量其它基础容器模板类中已经写好的成员函数。当然如果必要的话容器适配器中也可以自创新的成员函数。 6.0.2、三种容器适配器 STL 提供了 3 种容器适配器分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。其中各适配器所使用的默认基础容器以及可供用户选择的基础容器如表 1 所示。 表 1 STL 容器适配器及其基础容器 容器适配器基础容器筛选条件默认使用的基础容器stack 基础容器需包含以下成员函数 empty()size()back()push_back()pop_back() 满足条件的基础容器有 vector、deque、list。dequequeue基础容器需包含以下成员函数 empty()size()front()back()push_back()pop_front() 满足条件的基础容器有 deque、list。dequepriority_queue基础容器需包含以下成员函数 empty()size()front()push_back()pop_back() 满足条件的基础容器有vector、deque。vector 不同场景下由于不同的序列式容器其底层采用的数据结构不同因此容器适配器的执行效率也不尽相同。但通常情况下使用默认的基础容器即可。当然我们也可以手动修改具体的修改容器适配器基础容器的方法后续讲解具体的容器适配器会详细介绍。 6.1、 stack 栈适配器 关于堆栈的概念这里就不介绍了知道后入先出即可。 由于 stack 适配器以模板类 stackT,ContainerdequeT其中 T 为存储元素的类型Container 表示底层容器的类型的形式位于stack头文件中并定义在 std 命名空间里。因此在创建该容器之前程序中应包含以下 2 行代码  #include stack using namespace std; 6.2、stack适配器成员函数 和其他序列容器相比stack 是一类存储机制简单、提供成员函数较少的容器。表 1 列出了 stack 容器支持的全部成员函数。 表 1 stack容器适配器支持的成员函数 成员函数功能empty()当 stack 栈中没有元素时该成员函数返回 true反之返回 false。size()返回 stack 栈中存储元素的个数。top()返回一个栈顶元素的引用类型为 T。如果栈为空程序会报错。push(const T val)先复制 val再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。push(T obj)以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。pop()弹出栈顶元素。emplace(arg…)arg… 可以是一个参数也可以是多个参数但它们都只用于构造一个对象并在栈顶直接生成该对象作为新的栈顶元素。swap(stackT other_stack)将两个 stack 适配器中的元素进行互换需要注意的是进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型都必须相同。 #include stack #include list #include iostream using namespace std;int main() {//1、创建stack适配器//方法1:创建一个不包含任何元素的stack适配器,并采用默认的deque//上面这行代码就成功创建了一个可存储 int 类型元素底层采用 deque 基础容器的 stack 适配器。std::stackint s1;//方法2:上面提到stackT,ContainerdequeT 模板类提供了 2 个参数通过指定第二个模板类型参数我们可以使用出 deque 容器外的其它序列式容器只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可。//在介绍适配器时提到序列式容器中同时包含这 5 个成员函数的有 vector、deque 和 list 这 3 个容器。因此stack 适配器的基础容器可以是它们 3 个中任何一个。例如下面展示了如何定义一个使用 list 基础容器的 stack 适配器std::stackint, std::listint s2;//方法3:也可以用一个基础容器来初始化stack适配器,只要该容器的类型和stack底层使用的基础容器类型相同即可。std::listint list1{1, 2, 3};std::stackint, std::listint s3(list1);//方法4:用一个stack容器初始化另一个stack容器std::stackint s4(s1);//2、常用成员函数用法cout size of s3 is: s3.size() endl;//将s3中存储的元素一次弹出,直到为空while(!s3.empty()){cout s3.top() endl;s3.pop();} } 6.2、 queue 队列适配器 队列(queue)是典型的 FIFO(先入先出)的数据结构。 https://cplusplus.com/reference/queue/queue/ 表 2 queue容器适配器支持的成员函数 成员函数功能empty()当 queue 中没有元素时该成员函数返回 true反之返回 false。size()返回 queue 队列中存储元素的个数。front()返回队列头部元素。如果队列为空程序会报错。back()返回队列尾部元素。如果对了为空程序会报错push在队列尾部插入一个元素emplace()在队列尾部插入一个元素pop()移除队列头部的元素 6.3、 priority_queue 优先权队列适配器 基础容器需包含以下成员函数     empty()     size()     front()     push_back()     pop_back()     满足条件的基础容器有vector、deque。 默认使用的基础容器是vector。 7. 迭代器适配器 本章将介绍 5 种迭代器适配器分别是反向迭代器适配器、插入型迭代器适配器、流迭代器适配器、流缓冲区迭代器适配器、移动迭代器适配器。 初学者完全可以将迭代器适配器视为普通迭代器。之所以称为迭代器适配器是因为这些迭代器是在输入迭代器、输出迭代器、正向迭代器、双向迭代器或者随机访问迭代器这些基础迭代器的基础上实现的。也就是说使用迭代器适配器的过程中其本质就是在操作某种基础迭代器。 不同的迭代器适配器其功能大不相同这些知识都会在本章中做详细讲解。 8、常用算法 8.1、C排序算法 8.1.0、C STL标准库提供的排序函数 C STL 标准库提供有很多实用的排序函数如表 1 所示。通过调用它们我们可以很轻松地实现对普通数组或者容器中指定范围内的元素进行排序。   表 1 C STL 排序函数 函数名用法sort (first, last)对容器或普通数组中 [first, last) 范围内的元素进行排序默认进行升序排序。stable_sort (first, last)和 sort() 函数功能相似不同之处在于对于 [first, last) 范围内值相同的元素该函数不会改变它们的相对位置。partial_sort (first, middle, last)从 [first,last) 范围内筛选出 muddle-first 个最小的元素并排序存放在 [firstmiddle) 区间中。partial_sort_copy (first, last, result_first, result_last)从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。is_sorted (first, last)检测 [first, last) 范围内是否已经排好序默认检测是否按升序排序。is_sorted_until (first, last)和 is_sorted() 函数功能类似唯一的区别在于如果 [first, last) 范围的元素没有排好序则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。void nth_element (first, nth, last)找到 [first, last) 范围内按照排序规则默认按照升序排序应该位于第 nth 个位置处的元素并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小该位置右侧的所有元素都比其存放的元素大。 对于表 1 中罗列的这些函数本教程会一一进行讲解这里先介绍 sort() 函数。 8.1.1、C sort()排序函数 #include algorithmusing namespace std; sort() 函数是基于快速排序实现的有关快速排序的具体实现过程。 需要注意的是sort() 函数受到底层实现方式的限制它仅适用于普通数组和部分类型的容器。换句话说只有普通数组和具备以下条件的容器才能使用 sort() 函数 容器支持的迭代器类型必须为随机访问迭代器。这意味着sort() 只对 array、vector、deque 这 3 个容器提供支持。如果对容器中指定区域的元素做默认升序排序则元素类型必须支持小于运算符同样如果选用标准库提供的其它排序规则元素类型也必须支持该规则底层实现所用的比较运算符sort() 函数在实现排序时需要交换容器中元素的存储位置。这种情况下如果容器中存储的是自定义的类对象则该类的内部必须提供移动构造函数和移动赋值运算符。 另外还需要注意的一点是对于指定区域内值相等的元素sort() 函数无法保证它们的相对位置不发生改变。 sort() 函数有 2 种用法其语法格式分别为 //对 [first, last) 区域内的元素做默认的升序排序 void sort (RandomAccessIterator first, RandomAccessIterator last); //按照指定的 comp 排序规则对 [first, last) 区域内的元素进行排序 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); #include iostream #include algorithm #include vectorusing namespace std;void print_vec(std::vectorint vec){for(auto elem: vec){cout elem ;}cout endl; }//以普通函数的方式实现自定义排序规则 bool mycomp(int i, int j){return (i j); }//以函数对象的方式实现自定义排序规则 class mycomp2{public:bool operator() (int i, int j){return (i j);} };int main() {std::vectorint myvec{77,66,55,44,33,22,11};print_vec(myvec);//调用第一种格式对前五个元素进行排序std::sort(myvec.begin(), myvec.begin() 4);print_vec(myvec);//调用第二种语法格式通过调用自定义比较规则进行排序//std::sort(myvec.begin(), myvec.end(), mycomp());std::sort(myvec.begin(), myvec.end(), mycomp2());print_vec(myvec); } 输出如下 77 66 55 44 33 22 11 44 55 66 77 33 22 11 11 22 33 44 55 66 77 8.1.2、C stable_sort() #include algorithm using namespace std; 当指定范围内包含多个相等的元素时sort() 排序函数无法保证不改变它们的相对位置。那么如果既要完成排序又要保证相等元素的相对位置该怎么办呢可以使用 stable_sort() 函数。 有些场景是需要保证相等元素的相对位置的。例如对于一个保存某种事务比如银行账户的容器在处理这些事务之前为了能够有序更新这些账户需要按照账号对它们进行排序。而这时就很有可能出现相等的账号即同一账号在某段时间做多次的存取钱操作它们的相对顺序意味着添加到容器的时间顺序此顺序不能修改否则很可能出现账户透支的情况。 值得一提的是stable_sort() 函数完全可以看作是 sort() 函数在功能方面的升级版。换句话说stable_sort() 和 sort() 具有相同的使用场景就连语法格式也是相同的后续会讲只不过前者在功能上除了可以实现排序还可以保证不改变相等元素的相对位置。 并且table_sort() 函数的用法也有 2 种其语法格式和 sort() 函数完全相同仅函数名不同 //对 [first, last) 区域内的元素做默认的升序排序 void stable_sort ( RandomAccessIterator first, RandomAccessIterator last ); //按照指定的 comp 排序规则对 [first, last) 区域内的元素进行排序 void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); 其中first 和 last 都为随机访问迭代器它们的组合 [first, last) 用来指定要排序的目标区域另外在第 2 种格式中comp 可以是 C STL 标准库提供的排序规则比如 std::greaterT也可以是自定义的排序规则。 8.1.3、C partial_sort()排序 #include algorithm using namespace std; 假设这样一种情境有一个存有 100 万个元素的容器但我们只想从中提取出值最小的 10 个元素该如何实现呢     通过前面的学习读者可能会想到使用 sort() 或者 stable_sort() 排序函数即通过对容器中存储的 100 万个元素进行排序就可以成功筛选出最小的 10 个元素。但仅仅为了提取 10 个元素却要先对 100 万个元素进行排序可想而知这种实现方式的效率是非常低的。     对于解决类似的问题C STL 标准库提供了更高效的解决方案即使用 partial_sort() 或者 partial_sort_copy() 函数本节就对这 2 个排序函数的功能和用法做详细的讲解。 要知道一个函数的功能往往可以从它的函数名中体现出来以 partial_sort() 函数为例partial sort 可直译为“部分排序”。partial_sort() 函数的功能确是如此即该函数可以从指定区域中提取出部分数据并对它们进行排序。 //按照默认的升序排序规则对 [first, last) 范围的数据进行筛选并排序 void partial_sort (RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last); //按照 comp 排序规则对 [first, last) 范围的数据进行筛选并排序 void partial_sort (RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last,Compare comp); 其中first、middle 和 last 都是随机访问迭代器comp 参数用于自定义排序规则。 partial_sort() 函数会以交换元素存储位置的方式实现部分排序的。具体来说partial_sort() 会将 [first, last) 范围内最小或最大的 middle-first 个元素移动到 [first, middle) 区域中并对这部分元素做升序或降序排序。          需要注意的是partial_sort() 函数受到底层实现方式的限制它仅适用于普通数组和部分类型的容器。换句话说只有普通数组和具备以下条件的容器才能使用 partial_sort() 函数 容器支持的迭代器类型必须为随机访问迭代器。这意味着partial_sort() 函数只适用于 array、vector、deque 这 3 个容器。当选用默认的升序排序规则时容器中存储的元素类型必须支持 小于运算符同样如果选用标准库提供的其它排序规则元素类型也必须支持该规则底层实现所用的比较运算符partial_sort() 函数在实现过程中需要交换某些元素的存储位置。因此如果容器中存储的是自定义的类对象则该类的内部必须提供移动构造函数和移动赋值运算符。 #include iostream #include algorithm #include vectorusing namespace std;void print_vec(std::vectorint vec){for(auto elem: vec){cout elem ;}cout endl; }//以普通函数的方式实现自定义排序规则 bool mycomp(int i, int j){return (i j); }//以函数对象的方式实现自定义排序规则 class mycomp2{public:bool operator() (int i, int j){return (i j);} };int main() {std::vectorint myvec{9,7,5,3,1,2,4,6,8};print_vec(myvec);//以默认的升序排序作为排序规则,将myvec中最小的5个元素移动到开头位置并排好序std::partial_sort(myvec.begin(), myvec.begin()5, myvec.end());print_vec(myvec);//以指定的mycomp2作为排序规则将myvec中最大的5个元素移动到开头位置并排好序std::partial_sort(myvec.begin(), myvec.begin()5, myvec.end(), mycomp2());print_vec(myvec);} 8.1.4、C partial_sort_copy()排序 partial_sort_copy() 函数的功能和 partial_sort() 类似唯一的区别在于前者不会对原有数据做任何变动而是先将选定的部分元素拷贝到另外指定的数组或容器中然后再对这部分元素进行排序。   8.1.5、C nth_element()用法 #include nth_element using namespace std; 前面章节中已经给大家介绍了 sort()、stable_sort()、partial_sort() 这些函数的功能和用法本节再介绍一个排序函数即 nth_element() 函数。 不过在系统讲解 nth_element() 函数之前我们先形成一个共识即在有序序列中我们可以称第 n 个元素为整个序列中“第 n 大”的元素。比如下面是一个升序序列 2 4 6 8 10 在这个序列中我们可以称元素 6 为整个序列中“第 3 小”的元素并位于第 3 的位置处同样元素 8 为整个序列中“第 4 小”的元素并位于第 4 的位置处。 简单的理解 nth_element() 函数的功能当采用默认的升序排序规则std::lessT时该函数可以从某个序列中找到第 n 小的元素 K并将 K 移动到序列中第 n 的位置处。不仅如此整个序列经过 nth_element() 函数处理后所有位于 K 之前的元素都比 K 小所有位于 K 之后的元素都比 K 大。 举个例子对于如下序列         3  4  1  2  5 假设按照升序排序并通过nth_element()函数查找此序列中第3小的元素则最终得到的序列可能如下         2  1  3  4  5 显然nth_element() 函数找到了第 3 小的元素 3 并将其位于第 3 的位置同时元素 3 之前的所有元素都比该元素小元素 3 之后的所有元素都比该元素大。 nth_element() 函数有以下 2 种语法格式 //排序规则采用默认的升序排序 void nth_element (RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last); //排序规则为自定义的 comp 排序规则 void nth_element (RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last,Compare comp); 其中各个参数的含义如下 first 和 last都是随机访问迭代器[first, last) 用于指定该函数的作用范围即要处理哪些数据nth也是随机访问迭代器其功能是令函数查找“第 nth 大”的元素并将其移动到 nth 指向的位置comp用于自定义排序规则。 注意鉴于 nth_element() 函数中各个参数的类型其只能对普通数组或者部分容器进行排序。换句话说只有普通数组和符合以下全部条件的容器才能使用使用 nth_element() 函数 容器支持的迭代器类型必须为随机访问迭代器。这意味着nth_element() 函数只适用于 array、vector、deque 这 3 个容器。当选用默认的升序排序规则时容器中存储的元素类型必须支持 小于运算符同样如果选用标准库提供的其它排序规则元素类型也必须支持该规则底层实现所用的比较运算符nth_element() 函数在实现过程中需要交换某些元素的存储位置。因此如果容器中存储的是自定义的类对象则该类的内部必须提供移动构造函数和移动赋值运算符。 参考 STL教程C STL快速入门非常详细