前言

今天，我们继续踏入追寻C++的冒险历程。上一章我们简单介绍并且了解了C++中的模板，并且在最后提到了C++的标准模板库也叫做STL，那么本章将为大家讲解这一重要的部分：STL。下面让我们一起来进入STL的学习。

1. STL简介

STL(standard template libaray)叫做标准模板库，是C++标准库的重要组成部分。上一章我们讲解了模板，那么通过这个名字我们可以知道STL里面是一些模板，STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这样当我们在需要用到顺序表、链表、堆、栈等数据结构时不需要自己去写，而是直接调用库中的即可。STL不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

STL 将“在数据上执行的操作”与“要执行操作的数据分开”，分别以如下概念指代：

• 容器：包含、放置数据的地方。
• 迭代器：在容器中指出一个位置、或成对使用以划定一个区域，用来限定操作所涉及到的数据范围。
• 算法：要执行的操作。

STL有六大组件，如下图所示：

下面我们会一一进行了解。

STL是C++中的优秀作品，有了它的陪伴，许多底层的数据结构以及算法都不需要自己重新造轮子，站在前人的肩膀上，健步如飞的快速开发。 本章为大家讲解一下常见的STL容器的使用。

2. auto和范围for

在这里补充2个C++11的小语法，方便我们后面的学习。

2.1 auto关键字

在早期C/C++中auto的含义是：使用auto修饰的变量，是具有自动存储器的局部变量，后来这个不重要了。C++11中，标准委员会变废为宝赋予了auto全新的含义即：auto不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。

• 用auto声明指针类型时，用auto和auto*没有任何区别，但用auto声明引用类型时则必须加&。
• 当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。
• auto不能作为函数的参数，可以做返回值，但是建议谨慎使用。
• auto不能直接用来声明数组。

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
	std::map<std::string, std::string> dict = { { "apple", "苹果" },{ "orange","橙子" }, {"pear","梨"}};
	// auto的用武之地
	//std::map<std::string, std::string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	return 0;
}

在上述代码中我们可以看到，it的类型名字很长，在我们写程序会不经意间出现写错等小错误，而且浪费时间，这时，我们就可以使用auto关键字去自动推导类型。

2.2 范围for

对于一个有范围的集合而言，由程序员来说明循环的范围是多余的，有时候还会容易犯错误。因此C++11中引入了基于范围的for循环。for循环后的括号由冒号“ ：”分为两部分：第一部分是范围内用于迭代的变量，第二部分则表示被迭代的范围，自动迭代，自动取数据，自动判断结束。

• 范围for可以作用到数组和容器对象上进行遍历。
• 范围for的底层很简单，容器遍历实际就是替换为迭代器，这个从汇编层也可以看到。

#include<iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
	int array[] = { 1, 2, 3, 4, 5 };
	// C++98的遍历
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
	{
	array[i] *= 2;
	} 
    for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
	{
	cout << array[i] << endl;
	} 
    // C++11的遍历
	for (auto& e : array)
		e *= 2;
    
	for (auto e : array)
		cout << e << " " << endl;
    
	string str("hello world");
	for (auto ch : str)
	{
		cout << ch << " ";
	} 
    cout << endl;
	return 0;
}

在使用范围for时需要注意，当我们在循环的过程时需要用到下标时，那么就不能使用范围for。因为使用范围for我们在循环中得到的直接是下标对应的值，而没有具体的下标。

3. string类

C语言中，字符串是以’\0’结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。 在OJ中，有关字符串的题目基本以string类的形式出现，而且在常规工作中，为了简单、方便、快捷，基本都使用string类，很少有人去使用C库中的字符串操作函数。

使用string类时，必须包含头文件#include<string>和using namespace std;（不展开命名空间的话需要在使用时指定类域）。

string是一个类，并不是我们上面所说的模板，这是因为string类出现的时间要比STL的时间早，因此与我们其他的容器不同，它的定义不需要再传模板参数。

看上图可知，string类是由basic_string<char> typedef出来的（了解即可），下面我们来看看string类的常用接口：

3.1 string类对象的常见构造

(constructor)函数名称	功能说明
string() （重点）	构造空的string类对象，即空字符串
string(const char* s) （重点）	用C-string来构造string类对象
string(size_t n, char c)	string类对象中包含n个字符c
string(const string&s) （重点）	拷贝构造函数

void Teststring()
{
	string s1; // 构造空的string类对象s1
	string s2("hello world"); // 用C格式字符串构造string类对象s2
	string s3(s2); // 拷贝构造s3
}

3.2 string类对象的容量操作

函数名称	功能说明
size（重点）	返回字符串有效字符长度
length	返回字符串有效字符长度
capacity	返回空间总大小
empty （重点）	检测字符串释放为空串，是返回true，否则返回false
clear （重点）	清空有效字符
reserve （重点）	为字符串预留空间**
resize （重点）	将有效字符的个数该成n个，多出的空间用字符c填充

// 测试string容量相关的接口
// size/clear/resize
void Test()
{
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello, wrold!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << 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;
    
	// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;
    
	// 测试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;
}

注意：

• size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。
• clear()只是将string中有效字符清空，不改变底层空间大小。
• resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
• reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参数小于string的底层空间总大小时，reserver不会改变容量大小。

3.3 string类对象的访问及遍历操作

函数名称	功能说明
operator[] （重点）	返回pos位置的字符，const string类对象调用
begin+ end	begin获取第一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器
rbegin + rend（反向迭代器）	rbegin获取最后一个字符的迭代器 + rend获取第一个字符位置之前的迭代器
范围for	C++11支持更简洁的范围for的新遍历方式

对于string类的遍历：

// string的遍历
// begin()+end()   for+[]  范围for
// 注意：string遍历时使用最多的还是for+下标 或者 范围for(C++11后才支持)
// begin()+end()大多数使用在需要使用STL提供的算法操作string时，比如：采用reverse逆置string
void Test()
{
	string s("hello World");
	// 3种遍历方式：
	// 需要注意的以下三种方式除了遍历string对象，还可以遍历是修改string中的字符，
	// 另外以下三种方式对于string而言，第一种使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定义迭代器，让编译器推到迭代器的类型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范围for
	for (auto ch : s)
		cout << ch << endl;
}

3.4 string类对象的修改操作

函数名称	功能说明
push_back	在字符串后尾插字符c
append	在字符串后追加一个字符串
operator+= (重点)	在字符串后追加字符串str
c_str(重点)	返回C格式字符串
find (重点)	从字符串pos位置开始往后找字符c，返回该字符在字符串中的位置
rfind	从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置
substr	在str中从pos位置开始，截取n个字符，然后将其返回
npos(静态成员常量值)	当此值用作字符串成员函数中 len （或 sublen） 参数的值时，表示*“直到字符串的末尾”。*

// 测试string：
// 1. 插入(拼接)方式：push_back  append  operator+= 
// 2. 正向和反向查找：find() + rfind()
// 3. 截取子串：substr()
// 4. 删除：erase
void Test()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一个字符"hello"
	str += 'w';           // 在str后追加一个字符'w'   
	str += "orld";          // 在str后追加一个字符串"orld"
	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(c) / s.append(1, c) / s += 'c'三种的实现方式差不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
• 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好

3.4 string类非成员函数

函数	功能说明
operator+	尽量少用，因为传值返回，导致深拷贝效率低
getline （重点）	获取一行字符串

#include <iostream>
#include <string>
//getline的使用
int main ()
{
  std::string name;

  std::cout << "Please, enter your full name: ";
  std::getline (std::cin, name);
  std::cout << "Hello, " << name << "!\n";

  return 0;
}

3.6 vs下string的结构

下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义string中字符串的存储空间：

• 当字符串长度小于16时，使用内部固定的字符数组来存放。
• 当字符串长度大于等于16时，从堆上开辟空间。

union _Bxty
{ 	// storage for small buffer or pointer to larger one
	value_type _Buf[_BUF_SIZE];
	pointer _Ptr;
	char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;

这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。其次：还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的容量最后：还有一个指针做一些其他事情。故总共占16+4+4+4=28个字节。

4. vector

vector是序列容器，表示大小可以变化的数组。就像数组一样，vector对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问它们的元素，并且与在数组中一样高效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。

4.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);	使用迭代器进行初始化构造

//vector的构造
void Test()
{
    // 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
    
    cout << "first:";
	for (int x : first)
    	cout << x << ' ';
	cout << endl;

	cout << "second:";
	for (int x : second)
    	cout << x << ' ';
	cout << endl;

	cout << "third:";
	for (int x : third)
    	cout << x << ' ';
	cout << endl;

	cout << "fourth:";
	for (int x : fourth)
    	cout << x << ' ';
	cout << endl;
}

4.2 vector iterator (迭代器)的使用

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

void Test()
{
	vector<int> v(4, 1);

	// 使用迭代器进行遍历打印
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用迭代器进行修改
	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}

	// 使用反向迭代器进行遍历再打印
	// vector<int>::reverse_iterator rit = v.rbegin();
	auto rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

vector的遍历使用operator[]+下标和范围for+auto两种方式是比较方便的。

void Test()
{
	vector<int> v{ 1, 2, 3, 4 };

	// 通过[]读写第0个位置。
	v[0] = 10;
	cout << v[0] << endl;

	// 1. 使用for+[]小标方式遍历
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;

	vector<int> swapv;
	swapv.swap(v);

	cout << "v data:";
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;

	// 2. 使用迭代器遍历
	cout << "swapv data:";
	auto it = swapv.begin();
	while (it != swapv.end())
	{
		cout << *it << " ";
		++it;
	}

	// 3. 使用范围for遍历
	for (auto x : v)
		cout << x << " ";
	cout << endl;
}

4.3 vector的空间使用

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity

// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
void TestVector3()
{
	vector<int> v;

	// set some initial content:
	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';
	
	// 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
	// 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
}

注意：

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
• reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
• resize在开空间的同时还会进行初始化，影响size。

4.4 vector的增删查改

vector增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问

//  vector的增删改查
// 尾插和尾删：push_back/pop_back
void Test1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	auto it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	v.pop_back();
	v.pop_back();

	it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

// 任意位置插入：insert和erase，以及查找find
// 注意find不是vector自身提供的方法，是STL提供的算法
void Test2()
{
	// 使用列表方式初始化，C++11新语法
	vector<int> v{ 1, 2, 3, 4 };

	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
	// 1. 先使用find查找3所在位置
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		// 2. 在pos位置之前插入30
		v.insert(pos, 30);
	}

	vector<int>::iterator it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);

	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

4.6 vector迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。*

对于vector可能会导致其迭代器失效的操作有：

• 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

  #include <iostream>
  using namespace std;
  #include <vector>
  int main()
  {
  	vector<int> v{1,2,3,4,5,6};
  	auto it = v.begin();
      
  	// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
  	// v.resize(100, 8);
      
  	// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
  	// v.reserve(100);
      
  	// 插入元素期间，可能会引起扩容，而导致原空间被释放
  	// v.insert(v.begin(), 0);
  	// v.push_back(8);
      
  	// 给vector重新赋值，可能会引起底层容量改变
  	v.assign(100, 8);
      
  	/*
  	出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释
  	放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块
  	已经被释放的空间，而引起代码运行时崩溃。
  	解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给
  	it重新赋值即可。
  	*/
  	while(it != v.end())
  	{
  		cout<< *it << " " ;
  		++it;
  	}
      cout<<endl;
  	return 0;
  }
  

• 指定位置元素的删除操作–>erase

  #include <iostream>
  #include <vector>
  using namespace std;
  int main()
  {
  	int a[] = { 1, 2, 3, 4 };
  	vector<int> v(a, a + sizeof(a) / sizeof(int));
      
  	// 使用find查找3所在位置的iterator
  	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
      
  	// 删除pos位置的数据，导致pos迭代器失效。
  	v.erase(pos);
  	cout << *pos << endl; // 此处会导致非法访问
  	return 0;
  }
  

  erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

• 与vector类似，string在insert + 扩容操作 + erase之后，迭代器也会失效

  #include <string>
  using namespace std;
  void Test()
  {
  	string s("hello");
  	auto it = s.begin();
      
  	// 放开之后代码会崩溃，因为resize到20会string会进行扩容
  	// 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
  	// 后序打印时，再访问it指向的空间程序就会崩溃
  	//s.resize(20, '!');
  	while (it != s.end())
  	{
  		cout << *it;
  		++it;
  	} 
      cout << endl;
      
  	it = s.begin();
  	while (it != s.end())
  	{
  		it = s.erase(it);
  		// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
  		// it位置的迭代器就失效了
  		// s.erase(it);
  		++it;
  	}
  }
  

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

5. list

list是序列容器，允许对序列中任意位置的恒定时间插入和删除操作，以及双向迭代。list容器实现为双向循环链表（对于双向循环链表详情可看）;双向循环链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序在内部通过与指向其前面的元素的链接和指向其后元素的链接的每个元素的关联来保持。

它们与 forward_list 非常相似：主要区别在于 forward_list 对象是单链表，因此它们只能向后迭代，这里涉及到了迭代器的分类，对于不同的容器类型，迭代器也分为几类，其中最为常见的有三类：分别是单向迭代器、双向迭代器、随机迭代器：

• 单向迭代器（Forward iterators）：只能向后走，也就是只能进行++操作，例如forward_list、unordered_xxx。
• 双向迭代器（Bidirectional iterator）：可以向后也可以向前走，也就是可以进行++和–操作，例如list。
• 随机迭代器（RandomAccessIterator）：即可以跨越的向前和向后走，也就是可以进行+和-操作，例如string、vector。

5.1 sort函数

在c++的算法库中有一个排序函数，也就是sort，它可以对迭代器类型为随机迭代器的容器的数据进行排序：

使用它时需要包含头文件<algorithm>，库中的sort函数的底层使用的是快速排序（详情可看），我们知道在使用快排时我们需要能够随机访问到数组中的任何一个元素。因此在库函数sort中我们需要传入随机迭代器才能完成我们的排序。那么对于我们的list的排序该怎么呢？从上面我们知道list的迭代器是双向迭代器，不符合要求。其实，为了解决这个问题，list中有自己的成员函数sort：

当我们需要对list进行排序时，直接调用即可。在这两个sort函数中我们可以看到都有一个模板参数Compare，这也就是我们所说的仿函数，它的实际类型为一个类，里面重载了（）运算符，这样在使用时与函数的使用看起来是一样的（主要目的是代码实现方便）。该参数的作用也很简单，是用来控制我们排序是升序还是降序，默认为升序。下面拿list中的sort函数举个例子：

// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>

// comparison, not case sensitive.
bool compare_nocase (const std::string& first, const std::string& second)
{
  	unsigned int i=0;
  	while ( (i<first.length()) && (i<second.length()) )
  	{
    	if (tolower(first[i])<tolower(second[i])) return true;
    	else if (tolower(first[i])>tolower(second[i])) return false;
    	++i;
  	}
  	return ( first.length() < second.length() );
}

int main ()
{
  	//list中每个节点存储的值为字符串
  	std::list<std::string> mylist;
  	std::list<std::string>::iterator it;
  	mylist.push_back ("one");
  	mylist.push_back ("two");
  	mylist.push_back ("Three");

  	mylist.sort();

  	std::cout << "mylist contains:";
  	for (it=mylist.begin(); it!=mylist.end(); ++it)
    	std::cout << ' ' << *it;
  	std::cout << '\n';

  	//传入compare_nocase类,使排序按照降序
  	mylist.sort(compare_nocase);

  	std::cout << "mylist contains:";
  	for (it=mylist.begin(); it!=mylist.end(); ++it)
    	std::cout << ' ' << *it;
  	std::cout << '\n';

  	return 0;
}

5.2 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

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

5.3 list iterator的使用

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for，因为不支持下标访问
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过，因为是const对象
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中语法
    auto it = l.begin();                     // C++11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

注意：

• begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
• rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

5.4 list的常用类成员函数

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回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中的有效元素

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList1()
{
    int array[] = { 1, 2, 3 };
    list<int> L(array, array + sizeof(array) / sizeof(array[0]));

    // 在list的尾部插入4，头部插入0
    L.push_back(4);
    L.push_front(0);
    PrintList(L);

    // 删除list尾部节点和头部节点
    L.pop_back();
    L.pop_front();
    PrintList(L);
}

// insert /erase 
void TestList2()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
}

// resize/swap/clear
void TestList3()
{
    // 用数组来构造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

    // 交换l1和l2中的元素
    list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 将l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

5.5 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{ 
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
} 
// 改正
void TestListIterator()
{ 
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it++);
	}
}

5.6 list与vector的比较

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

	vector	list
底 层 结 构	动态顺序表，一段连续空间	带头结点的双向循环链表
随 机 访 问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插 入 和 删 除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针（节点指针）进行封装
迭 代 器 失 效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使 用 场 景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

6.stack和queue

stack和queue也就是数据结构中的栈和队列，与vector、list等不同，它们在STL中它们并不是以容器的形式存在的，而是容器适配器，简单来说就是同队堆其他的容器的接口进行包装后形成的。

6.1 容器适配器

我们先了解一下容器适配器到底是什么。

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

像我们的笔记本电脑都会有自己的电源适配器，它的作用就是将不同的电压和电流转换为支持我们笔记本最适合的电压电流。容器适配器也是如此，通过已有的常用容器来将它们的接口进行封装从而得到特定的我们想要的接口。

可以看到，stack和queue的模板参数中第二个就是容器，代表我们要用什么容器去实现，缺省值为deque(双端队列)。虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。当然我们也可以通过具体要求去选择更加合适的底层数据结构。下面我们简单了解一下deque。

6.2 deque

deque可以看作是vector与list的结合产物。

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，每一个位置存放的是指向一块地址的指针，当这块空间存满后再开辟一块空间，然后把指向这块空间的指针放入deque中，当deque满后，再对其进行扩容。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，这里不再赘述。

缺陷

• 与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作为底层数据结构结合了deque的优点，而完美的避开了其缺陷。

6.3 stack的使用

• stack是一种容器适配器，专门用于在FILO上下文(先进后出)中操作，其中从容器一端（称为栈顶）插入元素且提取元素。
• stack作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，stack提供一组特定的成员函数来访问其元素。元素从栈顶入栈，从栈顶出栈。
• 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

• 标准容器类deque和vector满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

栈的使用较为简单，这里通过一道 题目来看一下stack的使用：

class Solution 
{
public:
	bool IsPopOrder(vector<int> pushV,vector<int> popV) 
    {
		//入栈和出栈的元素个数必须相同
		if(pushV.size() != popV.size())
			return false;
        
		// 用s来模拟入栈与出栈的过程
		int outIdx = 0;
		int inIdx = 0;
		stack<int> s;
		while(outIdx < popV.size())
		{
			// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈
			while(s.empty() || s.top() != popV[outIdx])
			{
				if(inIdx < pushV.size())
					s.push(pushV[inIdx++]);
				else
					return false;
			} 
            
        	// 栈顶元素与出栈的元素相等，出栈
			s.pop();
			outIdx++;
		} 
        return true;
	}
};

6.4 queue

• 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
• 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
• 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

• 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

队列的使用与stack一样较为简单。不再赘述。

7. priority_queue

priority_queue（优先级队列）也是一种容器适配器。priority_queue默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆（父节点的值大于子节点，详情点击）。 若是想得到一个小堆就需要传入相应的参数。

7.1 priority_queue的类成员函数

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

注意：

• 默认情况下，priority_queue是大堆。

  #include <iostream>
  #include <vector>
  #include <queue>
  #include <functional> // greater算法的头文件
  using namespace std;
  
  int main()
  {
  	// 默认情况下，创建的是大堆，其底层按照小于号比较
  	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
  	priority_queue<int> q1;
  	for (auto& e : v)
  		q1.push(e);
  	cout << q1.top() << endl;
  
  	// 如果要创建小堆，将第三个模板参数换成greater比较方式
  	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
  	cout << q2.top() << endl;
  }
  

  

• 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

  class Date
  { 
  public:
  	Date(int year = 1900, int month = 1, int day = 1)
  		: _year(year)
  		, _month(month)
  		, _day(day)
  	{}
  	bool operator<(const Date& d)const
  	{
  		return (_year < d._year) ||
  			(_year == d._year && _month < d._month) ||
  			(_year == d._year && _month == d._month && _day < d._day);
  	} 
      bool operator>(const Date& d)const
  	{
  	return (_year > d._year) ||
  		(_year == d._year && _month > d._month) ||
  		(_year == d._year && _month == d._month && _day > d._day);
  	} 
      friend ostream& operator<<(ostream& _cout, const Date& d)
  	{
  		_cout << d._year << "-" << d._month << "-" << d._day;
  		return _cout;
  	}
  private:
  	int _year;
  	int _month;
  	int _day;
  };
  int main()
  {
  	// 大堆，需要用户在自定义类型中提供<的重载
  	priority_queue<Date> q1;
  	q1.push(Date(2018, 10, 29));
  	q1.push(Date(2018, 10, 28));
  	q1.push(Date(2018, 10, 30));
  	cout << q1.top() << endl;
      
  	// 如果要创建小堆，需要用户提供>的重载
  	priority_queue<Date, vector<Date>, greater<Date>> q2;
  	q2.push(Date(2018, 10, 29));
  	q2.push(Date(2018, 10, 28));
  	q2.push(Date(2018, 10, 30));
  	cout << q2.top() << endl;
  }
  

  

  对于STL中我们常用的一些容器及容器适配器到这里就结束了。在C++中STL的学习是很重要的，希望大家可以继续学习下去。网上有句话说：“不懂STL，不要说你会C++”。STL是C++中的优秀作品，有了它的陪伴，许多底层的数据结构以及算法都不需要自己重新造轮子，站在前人的肩膀上，健步如飞的快速开发。

尾声

若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！