【C++】STL理解【容器】
1. STL概念引入
长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复运用的东西”的方法，从函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)、各种组件，从模块化设计，到面向对象(object oriented )，为的就是复用性的提升。
复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦的来源。
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在 c++中，但是在引入 c++之前该技术已经存在很长时间了。
STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)。
容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。
STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以上。
1.1 STL六大组件
既然存在建立数据结构和算法的一套标准这个美好的愿想，就必须存在支撑起体系的工具，在STL中，这些工具就是STL组件——
容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器
分别进行简介：
容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template，即类别模板，可以简单理解为模板化、工具化了学习过的栈、队列等数据结构
算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte，即函数模板，体现了问题参数化的思维模式
参数化：
将具体的数据，做成参数，去解决不同数据的问题。
将具体的数据类型，做成参数，去解决不同数据类型的问题。
迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器
迭代器（iterator）是一种可以遍历容器元素的数据类型。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。C++更趋向于使用迭代器而不是
数组下标操作，因为标准库为每一种标准容器（如vector、map和list等）定义了一种迭代器类型，而只有少数容器（如vector）支持数组下标操作访问容
器元素。可以通过迭代器指向你想访问容器的元素地址，通过*x打印出元素值。这和我们所熟知的指针极其类似。
迭代器和容器是密不可分的、紧密相连的的关系。不同的容器，它们的迭代器也是不同的，但是它们的迭代器功能是一样的。假如没有迭代器，由于
不同容器间不同的的存储特点，你需要多种算法去实现遍历容器的功能，复杂且低效。有了迭代器，遍历容器的效率会大大提高。
仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template
适配器（配接器）：一种用来修饰容器或者仿函数或迭代器接口的东西
适配器（Adapter）模式：将一个类的接口转换为客户希望的另一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template
由于整个STL的操作对象都存放在容器中，而容器又需要配置空间以置放资料，所以就STL实现角度而言，空间配置器的介绍应排在第一位
总结STL六大组件的交互关系：
容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数
由于笔者能力有限，目前只能介绍浅显的理解，就不一一展开详解了。
1.2 STL优势
-
STL 是 C++的一部分，不用额外安装什么，它就被内建在你的编译器之内。
-
STL 的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作
-
程序员可以不用思考 STL 具体的实现过程，只要能够熟练使用 STL 就 OK 了。这样他们就可以把精力放在程序开发的别的方面。
-
STL 具有高可重用性，高性能，高移植性，跨平台的优点。
- 高可重用性：STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
- 高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。
- 高移植性：如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。
2. 容器概念引入
2.1 容器粗略理解
在先前数据结构的学习中，我们不难总结出：
在数据存储上，有一种对象类型，它可以持有其它对象或指向其它对像的指针，这种对象类型就叫做容器。很简单，容器就是保存其它对象的对象，当然这是一个朴素的理解，这种“对象”还包含了一系列处理“其它对象”的方法
几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。
常用的数据结构：数组(array) , 链表(list), 树(tree)，栈(stack), 队列(queue), 集合(set),映射表(map), 根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容器两种。
- 序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。
- 关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。Set/multiset容器 Map/multimap容器
2.2 容器分类
C++中，容器就是类模板,大致分为顺序容器,适配器容器和关联容器
顺序容器(vector,string,deque,list)
关联容器(set(集合容器)/multlist(多重集合容器)),(map(映射容器)/multimap(多重映射容器))
适配器容器(stack(栈容器)/queue(队列容器)/priority_queue(优先队列容器))
- 顺序容器：是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。顺序容器包括：vector(向量)、list（列表）、deque（队列）。
- 关联容器：关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。元素是有序的集合，默认在插入的时候按升序排列。关联容器包括：map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）。
- 容器适配器：本质上，适配器是使一种不同的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。STL 中包含三种适配器：栈stack 、队列queue 和优先级队列priority_queue 。
3. 常用容器
3.1 string
3.1.1 string基本概念
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件。
String和c风格字符串对比：
- Char是一个指针，String是一个类
string封装了char，管理这个字符串，是一个char*型的容器。- String封装了很多实用的成员方法
查找find，拷贝copy，删除delete 替换replace，插入insert- 不用考虑内存释放和越界
string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
3.1.2 string构造操作
string对象的初始化和普通类型变量的初始化基本相同，只是string作为类，还有类的一些特性：使用构造函数初始化。如下表，第2 4 6条是作为类才有的初始化方式
也可以用以下方法初始化：
string st1 = string("hello");
string st2(string(2,'b'));
3.1.3 string容量操作
string基础的的容量操作如下：
| 函数名称 | 功能说明 |
|---|---|
| size（重点） | 返回字符串有效字符长度 |
| length | 返回字符串有效字符长度 |
| capacity | 返回空间总大小 |
| empty （重点） | 检测字符串释放为空串，是返回true，否则返回false |
| clear （重点） | 清空有效字符 |
| reserve （重点） | 为字符串预留空间 |
| resize （重点） | 将有效字符的个数改成n个，多出的空间用字符c填充 |
void Test2()
{
// 注意：string类对象支持直接用cin和cout进行输入和输出
string s("hello, you!!!");
cout << s.size() << endl;
cout << s.length() << endl;
cout << s.capacity() << endl;
cout << s << endl;
// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
s.clear();
cout << s.size() << endl;
cout << s.capacity() << endl;
// 将s中有效字符个数增加到10个，多出位置用'a'进行填充
// “aaaaaaaaaa”
s.resize(10, 'a');
cout << s.size() << endl;
cout << s.capacity() << endl;
// 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
// "aaaaaaaaaa\0\0\0\0\0"
// 注意此时s中有效字符个数已经增加到15个
s.resize(15);
cout << s.size() << endl;
cout << s.capacity() << endl;
cout << s << endl;
// 将s中有效字符个数缩小到5个
s.resize(5);
cout << s.size() << endl;
cout << s.capacity() << endl;
cout << s << endl;
}
输出：
void Test3()
{
string s;
// 测试reserve是否会改变string中有效元素个数
s.reserve(100);
cout << s.size() << endl;
cout << s.capacity() << endl;
// 测试reserve参数小于string的底层空间大小时，是否会将空间缩小
s.reserve(50);
cout << s.size() << endl;
cout << s.capacity() << endl;
// 利用reserve提高插入数据的效率，避免增容带来的开销
}
输出：
3.1.4 string访问遍历操作
| 函数名称 | 功能说明 |
|---|---|
| operator[] | 返回pos位置的字符，const string类对象调用 |
| begin + end | begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭 代器 |
| rbegin + rend | begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭 代器 |
| 范围for | C++11支持更简洁的范围for的新遍历方式 |
先介绍迭代器的使用
迭代器（[iterator]）是一种可以遍历容器元素的数据类型。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。
相较于C语言，C++更趋向于使用迭代器而不是数组下标操作，因为标准库为每一种标准容器（如vector、map和list等）定义了一种迭代器类型，而只有少数容器（如vector）支持数组下标操作访问容器元素。可以通过迭代器指向你想访问容器的元素地址，通过*x打印出元素值。这和我们所熟知的指针极其类似。
我们这里关注访问遍历操作，即用迭代器遍历string类对象：
1）正向迭代器
void Test4()
{
string s1 = "hello,world";
string::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it;
++it;
}
cout << endl;
}
运行结果：
注意：
begin是返回字符串第一个字符的迭代器，而end则是返回一个指向字符串后一个字符的迭代器。
end返回的是指向字符的下一个字符的迭代器。C++中的迭代器一般是左闭右开区间
2）反向迭代器
void Test5()
{
string st1 = "hello,you!";
string :: reverse_iterator it = st1.rbegin();
while(it != st1.rend())
{
cout << *it << " ";
++it;
}
cout << endl;
}
运行结果：
反向迭代器输出的是正向迭代器相反的结果。在反向迭代器中，rbegin指向字符串的最后一个字符(即字符串的反向开头)。rend返回一个反向迭代器，指向字符串第一个字符(被认为是字符串的反向端)前面的理论元素。正向迭代器与反向迭代器的不同还在于，正向迭代器的++是向尾部走的，而反向迭代器则向头部走。
3）迭代器读写
void Test6()
{
string s1 = "hello,world";
string::iterator it = s1.begin();
while (it != s1.end())
{
*it='a';
cout << *it;
++it;
}
cout << endl;
}
运行结果：
其余的操作不一一举例，下文代码会有所体现
3.1.5 string修改操作
| 函数名称 | 功能说明 |
|---|---|
| push back | 在字符串后尾插字符c |
| append | 在字符串后追加一个字符串 |
| operator+= | 在字符串后追加字符串str |
| c str | 返回C格式字符串 |
| find + npos | 从字符串pos位置开始往后找字符c，返回该字符在字符串中的位置 |
| rfind | 从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置 |
| substr | 在str中从pos位置开始，截取n个字符，然后将其返回 |
1） string赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
具体案例：
#include<iostream>
using namespace std;
#include<string.h>
void test1()
{
string st1 = "hello";
string st2 = st1;
cout << "st1 = " << st1 << endl;
cout << "st2 = " << st2 << endl;
string st3;
st3.assign("hello");
cout << "st3 = " << st3 << endl;
string st4;
st4.assign("hello c++", 5);
cout << "st4 = " << st4 << endl;
string st5;
st5.assign(st4);
cout << "st5 = " << st5 << endl;
}
int main()
{
test1();
system("pause");
return 0;
}
运行结果：
要区分初始化与赋值操作，首先要明确先后关系：赋值是在初始化之后给对象值，比如：
string st1,string st2("hello");
st1 = st2;
2） string字符存取
string中单个字符存取方式有两种：
char &operator[](int n);//通过[ ]方式取字符char &at(int n);//通过at方法取字符
举例演示：
#include<iostream>
using namespace std;
#include<string.h>
void test1()
{
string st1 = "hello,goodbye";
cout << st1.size() << endl;
//使用[]获取字符
for(int i = 0;i < st1.size();i++)
{
cout << st1[i] << " ";
}
cout << endl;
//使用at获取字符
for(int j = 0;j < st1.size();j++)
{
cout << st1.at(j) <<" ";
}
cout << endl;
st1[0] = 'H';
st1.at(6) = 'G';
cout << st1 << endl;
}
int main()
{
test1();
system("pause");
return 0;
}
运行结果：
3） string拼接操作
void Test7()
{
string str;
str.push_back(' '); // 在str后插入空格
str.append("hello"); // 在str后追加一个字符"hello"
str += 'd'; // 在str后追加一个字符'd'
str += "y"; // 在str后追加一个字符串"y"
cout << str << endl;
cout << str.c_str() << endl; // 以C语言的方式打印字符串
// 获取file的后缀
string file("string.cpp");
size_t pos = file.rfind('.');
string suffix(file.substr(pos, file.size() - pos));
cout << suffix << endl;
// npos是string里面的一个静态成员变量
// static const size_t npos = -1;
// 取出url中的域名
string url("http://www.cplusplus.com/reference/string/string/find/");
cout << url << endl;
size_t start = url.find("://");
if (start == string::npos)
{
cout << "invalid url" << endl;
return;
}
start += 3;
size_t finish = url.find('/', start);
string address = url.substr(start, finish - start);
cout << address << endl;
// 删除url的协议前缀
pos = url.find("://");
url.erase(0, pos + 3);
cout << url << endl;
}
运行结果：
注意：
- 在string尾部追加字符时，s.push_back© / s.append(1, c) / s += 'c’三种的实现方式差不多，一般 情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
- 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好。
对npos的理解：
string::npos作为string的成员函数的一个长度参数时，表示“直到字符串结束（until the end of the string）”
string 类将 npos 定义为保证大于任何有效下标的值。
3.1.6 string接口使用
| 函数 | 功能说明 |
|---|---|
| operator+ | 传值返回，导致深拷贝效率低 |
| operator>> | 输入运算符重载 |
| operator<< | 输出运算符重载 |
| getline | 获取一行字符串 |
| relational operators | 大小比较简单介绍： |
运算符重载已经讲过，这里简单介绍getline
getline的函数格式：getline(cin,string对象)
getline的作用是读取一整行，直到遇到换行符才停止读取，期间能读取像空格、Tab等的空白符。
string s1;
getline(cin, s1);
cout << s1 << endl;
3.2 vector
3.2.1 vector基本概念
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。
- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
- 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。
3.2.2 vector迭代器
Vector维护一个线性空间，所以不论元素的型别如何，普通指针都可以作为vector的迭代器，因为vector迭代器所需要的操作行为，如operaroe*, operator->, operator++, operator–, operator+, operator-, operator+=, operator-=, 普通指针天生具备。
Vector支持随机存取，而普通指针正有着这样的能力。所以vector提供的是随机访问迭代器(Random Access Iterators)
看如下代码：
Vector<int>::iterator a1;
Vector<Bus>::iterator a2;
//a1的类别是int*，a2的类型是Bus*
3.2.3 vector数据结构
Vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst、_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。
所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。
扩容的过程需要经历以下 3 步：——> 解释了vector容器扩容后，与其相关的指针、引用以及迭代器可能会失效的原因。- 完全弃用现有的内存空间，重新申请更大的内存空间；
- 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
- 最后将旧的内存空间释放。
3.2.4 vector接口操作
1）vector构造
对于这一数据结构，我们使用的构造函数（constructor）如下：
| 构造函数声明 | 接口说明 |
|---|---|
| vector | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
测试代码如下：
int TestVector1()
{
// constructors used in the same order as described above:
vector<int> first; // empty vector of ints
vector<int> second(4, 100); // four ints with value 100
vector<int> third(second.begin(), second.end()); // iterating through second
vector<int> fourth(third); // a copy of third
// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
// the iterator constructor can also be used to construct from arrays:
int myints[] = { 16,2,77,29 };
vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
cout << "The contents of fifth are:";
for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
运行结果如下：
2）vector赋值
assign()
vector成员assign()负责分配新内容至vector中，代替现有内容并相应修改大小，本文介绍两种调用方法：
-
Range用法:range是迭代器调用版本，新内容是由 first 和 last 范围内的每个元素以相同的顺序构造的。使用的范围是 [first，last)
-
Fill用法:用 n 个值为 val 的元素填充目的容器
说来也不是很复杂，以代码展示用法：
//Range
int TestVector2()
{
vector<double> first{ 1.9, 2.9, 3.9, 4.9, 5.9 }; /*初始化源数组*/
vector<double> second; /*声明空数组*/
vector<int> third;
vector<string> forth;
vector<double>::iterator it;
it = first.begin();
second.assign(it, first.end());
cout << "Size of second: " << int(second.size()) << '\n';
for (int i = 0; i < second.size(); i++)
cout << second[i] << " ";
cout << endl;
//结果：
//Size of second: 5
//1.9 2.9 3.9 4.9 5.9
second.assign(it + 1, first.end() - 1);
cout << "Size of second: " << int(second.size()) << '\n';
for (int i = 0; i < second.size(); i++)
cout << second[i] << " ";
cout << endl;
//Size of second: 3
//2.9 3.9 4.9
third.assign(it, first.end());
cout << "Size of third: " << int(third.size()) << '\n';
for (int i = 0; i < third.size(); i++)
cout << third[i] << " ";
cout << endl;
//Size of third: 5
//1 2 3 4 5
int myints[] = {1776,7,4};
third.assign (myints,myints+3); /* assign with array*/
cout << "Size of third: " << int(third.size()) << '\n';
for (int i = 0; i < third.size(); i++)
cout << third[i] << " ";
cout << endl;
//Size of third: 3
//1776 7 4
//third.assign (myints,myints+4); /*error usage，有结果但是行为错误*/
//1776 7 4 787800
// third = first; /*error usage*/
// forth.assign(it,first.end()); /*error usage*/
return 0;
}
//Fill
int TestVector3()
{
vector<int> first(7); /*fill版构造,无初值*/
vector<int> second(7,1); /*fill版构造，给定初值*/
vector<int> third;
third.assign(7,2); /*fill版 assign */
vector<int> forth;
//forth.assign(7); /*error usage, fill版assign必须给初值*/
for (int i = 0; i < first.size(); i++)
cout << first[i] << " ";
cout << endl;
for (int i = 0; i < second.size(); i++)
cout << second[i] << " ";
cout << endl;
for (int i = 0; i < third.size(); i++)
cout << third[i] << " ";
cout << endl;
//结果:
//0 0 0 0 0 0 0
//1 1 1 1 1 1 1
//2 2 2 2 2 2 2
return 0;
}
swap()
swap(vec);// 将vec与本身的元素互换
3）vector空间
| 容量空间 | 接口说明 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
- capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义 的。vs是PJ版本STL，g++是SGI版本STL。
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问 题。
- resize在开空间的同时还会进行初始化，影响size。
操作简介：
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
reserve用法：
void TestVector5()
{
vector<int> v;
//预先开辟空间
v.reserve(100000);
int* pStart = NULL;
int count = 0;
for (int i = 0; i < 100000; i++) {
v.push_back(i);
if (pStart != &v[i]) {
pStart = &v[i];
count++;
}
}
cout << "count:" << count << endl;
}
运行结果:
resize用法：
void TestVector4()
{
// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，增多时，多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
vector<int> v;
for (int i = 1; i < 10; i++)
v.push_back(i);
v.resize(5);
v.resize(8, 100);
v.resize(12);
cout << "v contains:";
for (size_t i = 0; i < v.size(); i++)
cout << ' ' << v[i];
cout << '\n';
}
运行结果：
4）vector增删查改
| 增删查改操作 | 接口说明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找 |
| insert | position前插入val |
| erase | 删除position位置数据 |
| swap | 交换两vector数据空间 |
| operator[] | 像数组一样访问 |
用法：
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素
3.3 List
3.3.1 List基本概念
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高 效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
优缺点如下：
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外耗费较大
3.3.2 List迭代器
不像vector，list容器不能以普通指针为迭代器，因为其节点不能保证在同一块连续内存空间上。
List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
3.3.2.1 迭代器失效
可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
//错误版本
void TestListIterator1()
{
int array[] = {1,2,3,4,5,6,7,8,9};
list<int> l1(array,array + sizeof(array)/sizeof(array[0]));
auto it = l1.begin();
while(it != l1.end())
{
l1.erase(it);
++it;//erase()函数执行后，it所指向节点被删除，因此it无效，下一次使用it时，必须先给其赋值
}
}
//正确版本
void TestListIterator2()
{
int array[] = {1,2,3,4,5,6,7,8,9};
list<int> l1(array,array + sizeof(array)/sizeof(array[0]));
auto it = l1.begin();
while(it != l1.end())
{
l1.erase(it++);// it = l.erase(it);
}
}
3.3.3 List数据结构
list是个循环的双向链表
双向循环链表的循环方式是其尾结点的后继指针指向头结点(表头)，而头结点的前置指针指向尾结点，达到双向循环的目的，这样不仅使得对链表尾部的操作更为简单，也减少了对NULL指针的引用。
3.3.4 List接口操作
1）list构造
| constructor | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
代码演示：
void TestList1()
{
list<int> l1; // 构造空的l1
list<int> l2(4, 100); // l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l4(l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = { 16,2,77,29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
// 列表格式初始化C++11
list<int> l6{ 1,2,3,4,5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " ";
cout << endl;
}
运行结果：
2）list迭代器
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
代码演示：
list<int> l1{1,2,3,4,5};
//正向迭代器
list<int>::iterator it = l1.begin();
for(it;it != l1.end();it++)
{
cout << *it << " ";
}
cout << endl;//结果：1 2 3 4 5
//反向迭代器
list<int>::reverse_iterator rit = l1.rbegin();
for (rit; rit != l1.rend(); rit++)
{
cout << *rit << " ";
}
cout << endl;//结果：5 4 3 2 1
3）list大小操作
| 函数声明 | 接口说明 |
|---|---|
| size | 返回容器中元素的个数 |
| empty | 判断容器是否为空 |
| resize() | 重新指定容器长度 |
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
4）list增删存取
| 函数声明 | 接口说明 |
|---|---|
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
front();//返回第一个元素。
back();//返回最后一个元素。
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。
3.4 vector/list 对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素 效率O(N) |
| 插入/删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂 度为O(N)，插入时有可能需要增容，增容：开辟新空 间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不 需要搬移元素，时间复杂度为 O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率 高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针（节点指针）进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删 除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量删除及插入操作，不关心随机访问 |
3.5 stack
3.5.1 stack基本概念
stack是一种**先进后出(First In Last Out,FILO)**的数据结构，它只有一个出口，形式如图所示。
stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。
有元素推入栈的操作称为:push,将元素推出stack的操作称为pop
3.5.2 stack无迭代器
Stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。Stack不提供遍历功能，也不提供迭代器。
3.5.3 stack数据结构
限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
3.5.4 stack接口操作
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测栈是否为空 |
| size() | 返回栈中元素个数 |
| top() | 返回栈顶元素引用 |
| push() | 将元素val压入栈中 |
| pop() | 将栈中尾部元素弹出 |
3.6 queue
3.6.1 queue基本概念
Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。
3.6.2 queue无迭代器
Queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。Queue不提供遍历功能，也不提供迭代器。
3.6.3 queue数据结构
队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3.6.4 queue接口操作
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回true，否则返回false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
3.7 deque
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
3.7.1 deque基本概念
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上
(1) 申请更大空间
(2)原数据复制新空间
(3)释放原空间
三步骤，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
3.7.2deque缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
为什么选择deque作为stack和queue的底层默认容器？
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可 以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有 push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和 queue默认选择deque作为其底层容器，主要是因为：
stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
3.7.3 deque接口操作
1）deque构造
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。
2）deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换
3）deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。
4）deque数据增删存取
//双端
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
4.容器使用场景
| vector | deque | list | set | multiset | map | multimap | |
|---|---|---|---|---|---|---|---|
| 典型内存结构 | 单端数组 | 双端数组 | 双向链表 | 二叉树 | 二叉树 | 二叉树 | 二叉树 |
| 可随机存取 | 是 | 是 | 否 | 否 | 否 | 对key而言：不是 | 否 |
| 元素搜寻速度 | 慢 | 慢 | 非常慢 | 快 | 快 | 对key而言：快 | 对key而言：快 |
| 元素安插移除 | 尾端 | 头尾两端 | 任何位置 | - | - | - | - |
vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。
vector与deque的比较：
一：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
二：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
三：deque支持头部的快速插入与快速移除，这是deque的优点。
list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。
