C++ 学习笔记4

发表于 更新于
STL 容器和 STL 算法。

STL

只有 array 在栈上分配内存，其它 STL 容器在堆上分配内存。

string

string是字符容器，内部维护了一个动态的字符数组。

  1. 用作字符串。
  2. 用于存放数据的容器。

与普通的字符数组相比，string容器有三个优点：

  1. 使用的时候，不必考虑内存分配和释放的问题；

  2. 动态管理内存（可扩展）；

  3. 提供了大量操作容器的API。缺点是效率略有降低，占用的资源也更多。

静态常量成员string::npos为字符数组的最大长度（通常为unsigned int的最大值）。

capacity() string 的容量。

size() string 当前存放的数据大小。

append(地址，大小) 向 string 容器中追加数据。

构造函数

NBTS（null-terminated string）：C风格的字符串（以空字符0结束的字符串）。

1
2
3
4
5
6
7
8
9
10
11
12
13
string(); // 创建一个长度为0的string对象（默认构造函数）。

string(const char *s); // 将string对象初始化为s指向的NBTS（转换函数）。

string(const string &str); // 将string对象初始化为str（拷贝构造函数）。

string(const char *s,size_t n); // 将string对象初始化为s指向的地址后n字节的内容。 // 可以把 string 理解为一个地址块，这里的 const char* 可以理解为 void*

string(const string &str,size_t pos=0,size_t n=npos); // 将sring对象初始化为str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）。（第一个参数若是使用 c 风格字符串，则会导致使用第四个构造函数，因为函数重载更匹配。）

template<class T> string(T begin,T end); // 将string对象初始化为区间[begin,end]内的字符，其中begin和end的行为就像指针，用于指定位置，范围包括begin在内，但不包括end。

string(size_t n,char c); // 创建一个由n个字符c组成的string对象。

构造函数使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using  namespace std;

int main()
{
    // 1）string()：创建一个长度为0的string对象（默认构造函数）。
    string s1;        // 创建一个长度为0的string对象
    cout << "s1=" << s1 << endl;       // 将输出s1=
    cout << "s1.capacity()=" << s1.capacity() << endl;    // 返回当前容量，可以存放字符的总数。
    cout << "s1.size()=" << s1.size() << endl;                   // 返回容器中数据的大小。
    cout << "容器动态数组的首地址=" << (void *)s1.c_str() << endl;
    s1 = "xxxxxxxxxxxxxxxxxxxx";
    cout << "s1.capacity()=" << s1.capacity() << endl;    // 返回当前容量，可以存放字符的总数。
    cout << "s1.size()=" << s1.size() << endl;                   // 返回容器中数据的大小。
    cout << "容器动态数组的首地址=" << (void *)s1.c_str() << endl;

    // 2）string(const char *s)：将string对象初始化为s指向的NBTS（转换函数）。
    string s2("hello world");
    cout << "s2=" << s2 << endl;       // 将输出s2=hello world
    string s3 = "hello world";
    cout << "s3=" << s3 << endl;       // 将输出s3=hello world

    // 3）string(const string & str)：将string对象初始化为str（拷贝构造函数）。
    string s4(s3);                                     // s3 = "hello world";
    cout << "s4=" << s4 << endl;       // 将输出s4=hello world
    string s5 = s3;
    cout << "s5=" << s5 << endl;       // 将输出s5=hello world

    // 4）string(const char* s, size_t n)：将string对象初始化为s指向的NBTS的前n个字符，即使超过了NBTS结尾。
    string s6("hello world", 5);
    cout << "s6=" << s6 << endl;       // 将输出s6=hello
    cout << "s6.capacity()=" << s6.capacity() << endl;    // 返回当前容量，可以存放字符的总数。
    cout << "s6.size()=" << s6.size() << endl;                   // 返回容器中数据的大小。
    string s7("hello world", 50); 
    cout << "s7=" << s7 << endl;       // 将输出s7=hello未知内容
    cout << "s7.capacity()=" << s7.capacity() << endl;    // 返回当前容量，可以存放字符的总数。
    cout << "s7.size()=" << s7.size() << endl;                   // 返回容器中数据的大小。

    // 5）string(const string & str, size_t pos = 0, size_t n = npos)：
    // 将string对象初始化为str从位置pos开始到结尾的字符，或从位置pos开始的n个字符。
    string s8(s3, 3, 5);                               // s3 = "hello world";
    cout << "s8=" << s8 << endl;         // 将输出s8=lo wo
    string s9(s3, 3);          
    cout << "s9=" << s9 << endl;         // 将输出s9=lo world
    cout << "s9.capacity()=" << s9.capacity() << endl;    // 返回当前容量，可以存放字符的总数。
    cout << "s9.size()=" << s9.size() << endl;                   // 返回容器中数据的大小。
    string s10("hello world", 3, 5);
    cout << "s10=" << s10 << endl;       // 将输出s10=lo wo
    string s11("hello world", 3);                // 注意：不会用构造函数5），而是用构造函数4）
    cout << "s11=" << s11 << endl;       // 将输出s11=hel

    // 6）template<class T> string(T begin, T end)：将string对象初始化为区间[begin, end]内的字符，
    //      其中begin和end的行为就像指针，用于指定位置，范围包括begin在内，但不包括end。

    // 7）string(size_t n, char c)：创建一个由n个字符c组成的string对象。
    string s12(8, 'x');
    cout << "s12=" << s12 << endl;       // 将输出s12=xxxxxxxx
    cout << "s12.capacity()=" << s12.capacity() << endl;    // s12.capacity()=15
    cout << "s12.size()=" << s12.size() << endl;                   // s12.size()=8
    string s13(30, 0);
    cout << "s13=" << s13 << endl;       // 将输出s13=
    cout << "s13.capacity()=" << s13.capacity() << endl;    // s13.capacity()=31
    cout << "s13.size()=" << s13.size() << endl;                   // s12.size()=30 
}

C++11新增的构造函数：

  1. string(string && str) noexcept：它将一个string对象初始化为string对象str，并可能修改str（移动构造函数）。

  2. string(initializer_list<char> il)：它将一个string对象初始化为初始化列表il中的字符。例如：string ss = { 'h','e','l','l','o' };

char cc[8] 的深层理解

分配了 8 个字节的内存空间。可以存放任意数据。

数据类型只是对内存空间的语法表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
using  namespace std;

int main()
{
	char cc[8];   // 在栈上分配8字节的内存空间。

	// 把cc的内存空间用于字符串。
	strcpy(cc, "hello");
	cout << "cc=" << cc << endl << endl;

	// 把cc的内存空间用于int型整数。
	int* a, * b;
	a = (int *)cc;          // 前4个字节的空间用于整数a。
	b = (int *)cc + 4;   // 后4个字节的空间用于整数b。
	*a = 12345;
	*b = 54321;
	cout << "*a=" << *a << endl;
	cout << "*b=" << *b << endl << endl;
	
	// 把cc的内存空间用于double。
	double* d = (double*)cc;
	*d = 12345.7;
	cout << "*d=" << *d << endl << endl;

	// 把cc的内存空间用于结构体。
	struct stt
	{
		int a;
		char b[4];
	}*st;
	st = (struct stt*)cc;
	st->a = 38;
	strcpy(st->b, "abc");
	cout << "st->a=" << st->a << endl;
	cout << "st->b=" << st->b << endl << endl;
	
	// void* malloc(size_t size);
	//char* cc1 = (char*)malloc(8);
	//int* cc1 = (int*)malloc(8);
}

string 的成员函数

string 使用迭代器操作意义不大，会更复杂。

特性操作

1
2
3
4
5
6
7
8
9
size_t max_size() const;    // 返回string对象的最大长度string::npos，此函数意义不大。
size_t capacity() const;     // 返回当前容量，可以存放字符的总数。
size_t length() const;      // 返回容器中数据的大小（字符串语义）。
size_t size() const;         // 返回容器中数据的大小（容器语义）。
bool empty() const;     // 判断容器是否为空。
void clear();             // 清空容器，清空后，size()将返回0。
void shrink_to_fit();	      // 将容器的容量降到实际大小（需要重新分配内存）。
void reserve( size_t size=0);  // 将容器的容量设置为至少size。
void resize(size_t len,char c=0);  // 把容器的实际大小置为len，如果len<实际大小，会截断多出的部分；如果len>实际大小，就用字符c填充。resize()后，length()和size()将返回len。

字符操作

1
2
3
4
5
6
7
8
char &operator[](size_t n); 
const char &operator[](size_t n) const;  // 只读。
char &at(size_t n); 
const char &at(size_t n) const;          // 只读。
operator[]和at()返回容器中的第n个元素，但at函数提供范围检查，当越界时会抛出out_of_range异常，operator[]不提供范围检查。
const char *c_str() const; // 返回容器中动态数组的首地址，语义：寻找以null结尾的字符串。
const char *data() const; // 返回容器中动态数组的首地址，语义：只关心容器中的数据。
int copy(char *s, int n, int pos = 0) const; // 把当前容器中的内容，从pos开始的n个字节拷贝到s中，返回实际拷贝的数目。

赋值操作

assign 与构造函数相同。

给已存在的容器赋值，将覆盖容器中原有的内容。

1
2
3
4
5
6
7
1）string &operator=(const string &str); // 把容器str赋值给当前容器。
2）string &assign(const char *s); // 将string对象赋值为s指向的NBTS。
3）string &assign(const string &str); // 将string对象赋值为str。
4）string &assign(const char *s,size_t n); // 将string对象赋值为s指向的地址后n字节的内容。
5）string &assign(const string &str,size_t pos=0,size_t n=npos); // 将sring对象赋值为str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）。
6）template<class T> string &assign(T begin,T end); // 将string对象赋值为区间[begin,end]内的字符。
7）string &assign(size_t n,char c); // 将string对象赋值为由n个字符c。

连接操作

append 与构造函数相同。

把内容追加到已存在容器的后面。

1
2
3
4
5
6
7
1）string &operator+=(const string &str); //把容器str连接到当前容器。
2）string &append(const char *s); // 把指向s的NBTS连接到当前容器。
3）string &append(const string &str); // 把容器str连接到当前容器。
4）string &append(const char *s,size_t n); // 将s指向的地址后n字节的内容连接到当前容器。
5）string &append(const string &str,size_t pos=0,size_t n=npos); // 将str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）连接到当前容器。
6）template<class T> string &append (T begin,T end); // 将区间[begin,end]内的字符连接到容器。
7）string &append(size_t n,char c); // 将n个字符c连接到当前容器。

交换操作

1
void swap(string &str);    // 把当前容器与str交换。如果数据量很小，交换的是动态数组中的内容，如果数据量比较大，交换的是动态数组的地址。

截取操作

1
string substr(size_t pos = 0,size_t n = npos) const; // 返回pos开始的n个字节组成的子容器。

比较操作

compare()函数有异常，慎用

string 比较：

1
2
3
4
bool operator==(const string &str1,const string &str2) const; // 比较两个字符串是否相等。
int compare(const string &str) const; // 比较当前字符串和str1的大小。
int compare(size_t pos, size_t n,const string &str) const; // 比较当前字符串从pos开始的n个字符组成的字符串与str的大小。
int compare(size_t pos, size_t n,const string &str,size_t pos2,size_t n2)const; // 比较当前字符串从pos开始的n个字符组成的字符串与str中pos2开始的n2个字符组成的字符串的大小。

C 风格字符串比较：

1
2
3
int compare(const char *s) const; 
int compare(size_t pos, size_t n,const char *s) const;
int compare(size_t pos, size_t n,const char *s, size_t pos2) const;

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
size_t find(const string& str, size_t pos = 0) const;
size_t find(const char* s, size_t pos = 0) const;
size_t find(const char* s, size_t pos, size_t n) const;
size_t find(char c, size_t pos = 0) const;

size_t rfind(const string& str, size_t pos = npos) const;
size_t rfind(const char* s, size_t pos = npos) const;
size_t rfind(const char* s, size_t pos, size_t n) const;
size_t rfind(char c, size_t pos = npos) const;

size_t find_first_of(const string& str, size_t pos = 0) const;
size_t find_first_of(const char* s, size_t pos = 0) const;
size_t find_first_of(const char* s, size_t pos, size_t n) const;
size_t find_first_of(char c, size_t pos = 0) const;

size_t find_last_of(const string& str, size_t pos = npos) const;
size_t find_last_of(const char* s, size_t pos = npos) const;
size_t find_last_of(const char* s, size_t pos, size_t n) const;
size_t find_last_of(char c, size_t pos = npos) const;

size_t find_first_not_of(const string& str, size_t pos = 0) const;
size_t find_first_not_of(const char* s, size_t pos = 0) const;
size_t find_first_not_of(const char* s, size_t pos, size_t n) const;
size_t find_first_not_of(char c, size_t pos = 0) const;

size_t find_last_not_of(const string& str, size_t pos = npos) const;
size_t find_last_not_of(const char* s, size_t pos = npos) const;
size_t find_last_not_of(const char* s, size_t pos, size_t n) const;
size_t find_last_not_of(char c, size_t pos = npos) const;

替换操作

1
2
3
4
5
6
7
8
9
10
11
12
13
string& replace(size_t pos, size_t len, const string& str);
string& replace(size_t pos, size_t len, const string& str, size_t subpos, size_t sublen = npos);
string& replace(size_t pos, size_t len, const char* s);
string& replace(size_t pos, size_t len, const char* s, size_t n);
string& replace(size_t pos, size_t len, size_t n, char c);

以下函数意义不大。
string& replace(iterator i1, iterator i2, const string& str);
string& replace(iterator i1, iterator i2, const char* s);
string& replace(iterator i1, iterator i2, const char* s, size_t n);
string& replace(iterator i1, iterator i2, size_t n, char c);
template <class InputIterator>
string& replace(iterator i1, iterator i2, InputIterator first, InputIterator last);

插入操作

1
2
3
4
5
6
7
8
9
10
11
string& insert(size_t pos, const string& str);
string& insert(size_t pos, const string& str, size_t subpos, size_t sublen = npos);
string& insert(size_t pos, const char* s);
string& insert(size_t pos, const char* s, size_t n);
string& insert(size_t pos, size_t n, char c);

以下函数意义不大。
iterator insert(iterator p, size_t n, char c);
iterator insert(iterator p, char c);
template <class InputIterator>
iterator insert(iterator p, InputIterator first, InputIterator last);

删除操作

1
2
3
4
5
string &erase(size_t pos = 0, size_t n = npos); // 删除pos开始的n个字符。

以下函数意义不大。
iterator erase(iterator it); // 删除it指向的字符，返回删除后迭代器的位置。
iterator erase(iterator first, iterator last); / /删除[first，last）之间的所有字符，返回删除后迭代器的位置。

vector

vector容器封装了动态数组结构。

包含头文件： #include<vector>

vector类模板的声明：

1
2
3
4
5
6
7
8
template<class T, class Alloc = allocator<T>>
class vector{
private:
	T *start_; 
	T *finish_;
	T *end_;
	……
}

picGR9s.png

分配器

各种STL容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存

如果省略该模板参数的值，将默认使用allocator<T>，用new和delete分配和释放内存。

构造函数

1
2
3
4
5
6
7
8
1）vector();  // 创建一个空的vector容器。
2）vector(initializer_list<T> il); // 使用统一初始化列表。
3）vector(const vector<T>& v);  // 拷贝构造函数。
4）vector(Iterator first, Iterator last);  // 用迭代器创建vector容器。
5）vector(vector<T>&& v);  // 移动构造函数（C++11标准）。
6）explicit vector(const size_t n);   // 创建vector容器，元素个数为n（容量和实际大小都是n）。
7）vector(const size_t n, const T& value);  // 创建vector容器，元素个数为n，值均为value。
析构函数~vector()释放内存空间。

特性操作

1
2
3
4
5
6
7
8
9
size_t max_size() const;     // 返回容器的最大长度，此函数意义不大。
size_t capacity() const;      // 返回容器的容量。
size_t size() const;          // 返回容器的实际大小（已使用的空间）。
bool empty() const;        // 判断容器是否为空。
void clear();               // 清空容器。
void reserve(size_t size);   // 将容器的容量设置为至少size。
void shrink_to_fit();	       // 将容器的容量降到实际大小（需要重新分配内存）。
void resize(size_t size);    // 把容器的实际大小置为size。小于则截断，大于则补充0。
void resize(size_t size,const T &value);  // 把容器的实际大小置为size，如果size<实际大小，会截断多出的部分；如果size>实际大小，就用value填充。

元素操作

1
2
3
4
5
6
7
8
9
10
T &operator[](size_t n); 
const T &operator[](size_t n) const;  // 只读。
T &at(size_t n); 
const T &at(size_t n) const;          // 只读。
T *data();            // 返回容器中动态数组的首地址，可以操作地址操作元素。
const T *data() const; // 返回容器中动态数组的首地址。
T &front();        // 第一个元素。
const T &front();  // 第一个元素，只读。
const T &back();  // 最后一个元素，只读。
T &back();        // 最后一个元素。

赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1
2
3
4
5
1）vector &operator=(const vector<T> &v);    // 把容器v赋值给当前容器。
2）vector &operator=(initializer_list<T> il); // 用统一初始化列表给当前容器赋值。
3）void assign(initializer_list<T> il);        // 使用统一初始化列表赋值。
4）void assign(Iterator first, Iterator last);  // 用迭代器赋值。
5）void assign(const size_t n, const T& value);  // 把n个value给容器赋值。

交换操作

1
void swap(vector<T> &v);    // 把当前容器与v交换，交换的是动态数组的地址。

比较操作

1
2
bool operator == (const vector<T> & v) const;
bool operator != (const vector<T> & v) const;

插入和删除

emplace_back 使用类的构造函数的参数，直接传递类构造函数需要的对应的参数，会直接构造，不需要在此之前创建先对象。效率更高。

1
2
3
4
5
6
7
8
1）void push_back(const T& value);  // 在容器的尾部追加一个元素。
2）void emplace_back(…);           // 在容器的尾部追加一个元素，…用于构造元素。C++11
3）iterator insert(iterator pos, const T& value);  // 在指定位置插入一个元素，返回指向插入元素的迭代器。
4）iterator emplace (iterator pos, …);  // 在指定位置插入一个元素，…用于构造元素，返回指向插入元素的迭代器。C++11
5）iterator insert(iterator pos, iterator first, iterator last);  // 在指定位置插入一个区间的元素，返回指向第一个插入元素的迭代器。
6）void pop_back();                      // 从容器尾部删除一个元素。
7）iterator erase(iterator pos);             // 删除指定位置的元素，返回下一个有效的迭代器。
8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。

emplace_back 示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
using  namespace std;

class AA
{
public:
	int m_bh;               // 编号。
	string m_name;     // 姓名。

	AA()      // 默认构造函数。
	{ 
		//cout << "默认构造函数AA()。\n"; 
	}

	AA(const int &bh,const string& name) : m_bh(bh),m_name(name)   // 有两个参数的构造函数。
	{
		//cout << "构造函数，name=" << m_name << "。\n"; 
	}

	AA(const AA& g) :m_bh(g.m_bh), m_name(g.m_name)                       // 拷贝构造函数。
	{ 
		//cout << "拷贝构造函数，name=" << m_name << "。\n"; 
	}

	//~AA() { cout << "析构函数。\n"; }
};

int main()
{
	vector<AA> v(10);
	
	cout << v.size() << v.data() << endl;
	
	//AA a(18,"西施"); 
	//v.push_back(a);
	//v.emplace_back(a);
	v.emplace_back(18,"西施"); // 原位构造

	cout << "bh=" << v[0].m_bh << ",name=" << v[0].m_name << endl;
}

vector 嵌套

类似于二维数组，但是 vector 的二维是不固定大小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using  namespace std;

int main()
{
	vector<vector<int>> vv;   // 创建一个vector容器vv，元素的数据类型是vector<int>。

	vector<int> v;        // 创建一个容器v，它将作为容器vv的元素。

	v = { 1,2,3,4,5 };      // 用统一初始化列表给v赋值。
	vv.push_back(v);    // 把容器v作为元素追加到vv中。

	v = { 11,12,13,14,15,16,17 };   // 用统一初始化列表给v赋值。
	vv.push_back(v);                      // 把容器v作为元素追加到vv中。

	v = { 21,22,23 };     // 用统一初始化列表给v赋值。
	vv.push_back(v);    // 把容器v作为元素追加到vv中。

	// 用嵌套的循环，把vv容器中的数据显示出来。
	for (int ii = 0; ii < vv.size(); ii++)
	{
		for (int jj = 0; jj < vv[ii].size(); jj++)
			cout << vv[ii][jj] << " ";      // 像二维数组一样使用容器vv。

		cout << endl;
	}
}

迭代器

c++ 将常用数据结构进行封装，如数组为vector，链表为 list 等

即 STL 将各种数据结构封装成了容器，每个容器都有一个迭代器，迭代器提供了访问容器元素的通用方法（模板化）。

迭代器是访问容器中元素的通用方法。

如果使用迭代器，不同的容器，访问元素的方法是相同的。

迭代器（只要支持这些操作，就是迭代器，例如数组指针就是天然的迭代器）支持的基本操作：赋值（=）、解引用（*）、比较（==和!=）、从左向右遍历（++）。

一般情况下，迭代器是指针和移动指针的方法。

迭代器五种分类：

正向迭代器

只能使用++运算符从左向右遍历容器，每次沿容器向右移动一个元素。

1
2
3
4
5
6
7
8
9
容器名<元素类型>::iterator 迭代器名;        // 正向迭代器。
容器名<元素类型>::const_iterator 迭代器名;  // 常正向迭代器。

iterator begin();
const_iterator begin();
const_iterator cbegin();  // 避免 auto 判断为 begin ，因此加入 cbegin 配合auto使用。
iterator end();
const_iterator end();
const_iterator cend();

双向迭代器

具备正向迭代器的功能，还可以反向（从右到左）遍历容器（也是用++），不管是正向还是反向遍历，都可以用–让迭代器后退一个元素。

1
2
3
4
5
6
7
容器名<元素类型>:: reverse_iterator 迭代器名;        // 反向迭代器。
容器名<元素类型>:: const_reverse_iterator 迭代器名;  // 常反向迭代器。

reverse_iterator rbegin();
const_reverse_iterator crbegin();
reverse_iterator rend();
const_reverse_iterator crend();

随机访问迭代器

具备双向迭代器的功能，还支持以下操作：

  • 用于比较两个迭代器相对位置的关系运算（<、<=、>、>=）。

  • 迭代器和一个整数值的加减法运算（+、+=、-、-=）。

  • 支持下标运算（iter[n]）。

    物理存储结构是数组的容器才有随机访问迭代器。STL 中，string、vector、deque 的物理存储结构都是数组。

数组的指针是纯天然的随机访问迭代器。

输入和输出迭代器

这两种迭代器比较特殊，它们不是把容器当做操作对象，而是把输入/输出流作为操作对象。

STL 容器迭代器类型

容器类型 迭代器类型
vector Random Access
deque Random Access
list Bidirectional
set Bidirectional
multiset Bidirectional
map Bidirectional
multimap Bidirectional
unordered_set Forward
unordered_multiset Forward
unordered_map Forward
unordered_multimap Forward
stack N/A (不直接支持迭代器)
queue N/A (不直接支持迭代器)
priority_queue N/A (不直接支持迭代器)

迭代器操作

迭代器类型 支持的操作
Input 读取、递增（++）
Output 写入、递增（++）
Forward 读取、写入、递增（++）
Bidirectional 读取、写入、递增（++）、递减（–）
Random Access 读取、写入、递增（++）、递减（–）、随机访问（+、-）、比较（<、<=、>、>=）

迭代器失效

resize()、reserve()、assign()、push_back()、pop_back()、insert()、erase()等函数会引起vector容器的动态数组发生变化，可能导致vector迭代器失效。

当在循环中，使用上述函数会使迭代器失效，有些可以解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {1,2,3,4,5,6,7};

    for (auto it = vec.begin(); it != vec.end();)
    {
        cout << *it << endl;
        it = vec.erase(it); // erase 返回下一个有效迭代器。
    }

    return 0;
}

基于范围的 for 循环

C++11中引入了基于范围的for循环。

语法：

1
2
3
4
5
6
7
for (迭代的变量 : 迭代的范围)

{

    // 循环体。

}

注意：

  1. 迭代的范围可以是数组名、容器名、初始化列表或者可迭代的对象（支持begin()、end()、++、==）。

  2. 数组名传入函数后，已退化成指针，不能作为容器名。

  3. 如果容器中的元素是结构体和类，迭代器变量应该申明为引用，加const约束表示只读。

    因为迭代器变量如果不是引用，则会导致每次迭代都会调用拷贝构造和析构，使用引用可以避免，加 const 的引用可以避免容器中的变量被修改。

  4. 注意迭代器失效的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
using  namespace std;

class AA
{
public:
	string m_name;

	AA() { cout << "默认构造函数AA()。\n"; }

	AA(const string& name) : m_name(name) { cout << "构造函数，name=" << m_name << "。\n"; }

	AA(const AA& a) : m_name(a.m_name) { cout << "拷贝构造函数，name=" << m_name << "。\n"; }

	AA& operator=(const AA& a) { m_name = a.m_name;  cout << "赋值函数，name=" << m_name << "。\n";  return *this; }

	~AA() { cout << "析构函数，name=" << m_name<<"。\n"; }
};

int main()
{
	vector<int> vv = { 1,2,3,4,5,6,7,8,9,10 };

	//for (auto it = vv.begin(); it != vv.end(); it++)     // 用迭代器遍历容器vv。
	//{
	//	cout << *it << " ";
	//}
	//cout << endl;

	for (auto val : vv)      // 用基于范围的for循环遍历数组vv。
	{
		cout << val << " ";
		vv.push_back(10);
	}
	cout << endl;

	/*vector<AA> v;
	cout << "1111，v.capacity()=" << v.capacity() << "\n";
	v.emplace_back("西施");
	cout << "2222，v.capacity()=" << v.capacity() << "\n";
	v.emplace_back("冰冰");
	cout << "3333，v.capacity()=" << v.capacity() << "\n";
	v.emplace_back("幂幂");
	cout << "4444，v.capacity()=" << v.capacity() << "\n";

	for (const auto &a : v)
		cout << a.m_name << " ";
	cout << endl;*/
}

list

list 容器封装了双链表。

包含头文件： #include<list>

不支持随机访问迭代器，也就是不支持迭代器加值。如 lis.begin() + 3 这样。

list 成员函数

构造函数

1
2
3
4
5
6
7
1）list();  // 创建一个空的list容器。
2）list(initializer_list<T> il); // 使用统一初始化列表。
3）list(const list<T>& l);  // 拷贝构造函数。
4）list(Iterator first, Iterator last);  // 用迭代器创建list容器。
5）list(list<T>&& l);  // 移动构造函数（C++11标准）。
6）explicit list(const size_t n);   // 创建list容器，元素个数为n。
7）list(const size_t n, const T& value);  // 创建list容器，元素个数为n，值均为value。

析构函数~list()释放内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <list>
using  namespace std;

int main()
{
	// 1）list();  // 创建一个空的list容器。
	list<int> l1;
	// cout << "li.capacity()=" << l1.capacity() << endl;  // 链表没有容量说法。
	cout << "li.size()=" << l1.size() << endl;

	// 2）list(initializer_list<T> il); // 使用统一初始化列表。
	list<int> l2({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
	// list<int> l2={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	// list<int> l2  { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	for (int value : l2)       // 用基于范围的for循环遍历容器。
		cout << value << " ";
	cout << endl;

	// 3）list(const list<T>& l);  // 拷贝构造函数。
	list<int> l3(l2);
	// list<int> l3=l2;
	for (int value : l3)    
		cout << value << " ";
	cout << endl;

	// 4）list(Iterator first, Iterator last);  // 用迭代器创建list容器。
	list<int> l4(l3.begin(), l3.end());      // 用list容器的迭代器。
	for (int value : l4)  
		cout << value << " ";
	cout << endl;

	vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  // 创建vector容器。
	list<int> l5(v1.begin() + 2, v1.end() - 3);          // 用vector容器的迭代器创建list容器。
	for (int value : l5)   
		cout << value << " ";
	cout << endl;

	int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };   // 创建数组。
	list<int> l6(a1 + 2, a1 + 10 - 3);           // 用数组的指针作为迭代器创建list容器。
	for (int value : l6)     
		cout << value << " ";
	cout << endl;

	char str[] = "hello world";         // 定义C风格字符串。
	string s1(str + 1, str + 7);          // 用C风格字符串创建string容器。
	for (auto value : s1)                   // 遍历string容器。
		cout << value << " ";
	cout << endl;
	cout << s1 << endl;                 // 以字符串的方式显示string容器。

	vector<int> v2(l3.begin(), l3.end());   // 用list迭代器创建vector容器。
	for (auto value : v2)                               // 遍历vector容器。
		cout << value << " ";
	cout << endl;
}

特性操作

1
2
3
4
5
6
size_t max_size() const;     // 返回容器的最大长度，此函数意义不大。
size_t size() const;        // 返回容器的实际大小（已使用的空间）。
bool empty() const;      // 判断容器是否为空。
void clear();             // 清空容器。
void resize(size_t size);   // 把容器的实际大小置为size。
void resize(size_t size,const T &value);  // 把容器的实际大小置为size，如果size<实际大小，会截断多出的部分；如果size>实际大小，就用value填充。

元素操作

1
2
3
4
T &front();        // 第一个元素。
const T &front();  // 第一个元素，只读。
const T &back();  // 最后一个元素，只读。
T &back();        // 最后一个元素。

赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1
2
3
4
5
1）list &operator=(const list<T> &l);         // 把容器l赋值给当前容器。
2）list &operator=(initializer_list<T> il);  // 用统一初始化列表给当前容器赋值。
3）list assign(initializer_list<T> il);        // 使用统一初始化列表赋值。
4）list assign(Iterator first, Iterator last);  // 用迭代器赋值。
5）void assign(const size_t n, const T& value);  // 把n个value给容器赋值。

交换、反转、排序、归并

1
2
3
4
5
void swap(list<T> &l);   // 把当前容器与l交换，交换的是链表结点的地址。
void reverse();           // 反转链表。
void sort();              // 对容器中的元素进行升序排序。
void sort(_Pr2 _Pred);    // 对容器中的元素进行排序，排序的方法由_Pred决定（二元函数）。
void merge(list<T> &l);  // 采用归并法合并两个已排序的list容器，合并后的list容器仍是有序的。（也就是并集，新的链表可以有重复的元素）

比较操作

1
2
bool operator == (const vector<T> & l) const;
bool operator != (const vector<T> & l) const;

插入和删除

连接操作：会将原链表的指针放到被连接的链表的位置，而不是复制过去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1）void push_back(const T& value);  // 在链表的尾部追加一个元素。
2）void emplace_back(…);           // 在链表的尾部追加一个元素，…用于构造元素。C++11
3）iterator insert(iterator pos, const T& value);  // 在指定位置插入一个元素，返回指向插入元素的迭代器。
4）iterator emplace (iterator pos, …);  // 在指定位置插入一个元素，…用于构造元素，返回指向插入元素的迭代器。C++11
5）iterator insert(iterator pos, iterator first, iterator last);  // 在指定位置插入一个区间的元素，返回指向第一个插入元素的迭代器。
6）void pop_back();                      // 从链表尾部删除一个元素。
7）iterator erase(iterator pos);             // 删除指定位置的元素，返回下一个有效的迭代器。
8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。
9）void push_front(const T& value);  // 在链表的头部插入一个元素。
10）emplace_front(…);          // 在链表的头部插入一个元素，…用于构造元素。C++11
11）splice(iterator pos, const vector<T> & l);	  // 把另一个链表连接到当前链表。
12）splice(iterator pos, const vector<T> & l, iterator first, iterator last);	// 把另一个链表指定的区间连接到当前链表。
13）splice(iterator pos, const vector<T> & l, iterator first);	// 把另一个链表从first开始的结点连接到当前链表。
14）void remove(const T& value);	 // 删除链表中所有值等于value的元素。
15）void remove_if(_Pr1 _Pred);    // 删除链表中满足条件的元素，参数_Pred是一元函数。
16）void unique();                 // 删除链表中相邻的重复元素，只保留一个。注意：是相邻的，不相邻的相同的元素不会删除。
17）void pop_front();              // 从链表头部删除一个元素。

pair

pair是类模板，一般用于表示key/value数据，其实现是结构体。

pair结构模板的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T1, class T2>

struct pair 

{ 

   T1 first;   // 第一个成员，一般表示key。

   T2 second; // 第二个成员，一般表示value。

   pair();    // 默认构造函数。

   pair(const T1 &val1,const T2 &val2);  // 有两个参数的构造函数。

   pair(const pair<T1,T2> &p);      // 拷贝构造函数。

   void swap(pair<T1,T2> &p);      // 交换两个pair。

};

make_pair函数模板的定义如下：

1
2
3
4
5
6
7
8
9
template <class T1, class T2>

make_pair(const T1 &first,const T2 &second)

{

   return pair<T1,T2>(first, second);

}

pair 对象创建的多种方法示例：

函数返回临时对象和返回局部对象不一样，前者赋值函数返回值时不调用拷贝构造函数，后者调用拷贝构造函数。（linux下是相同的，visual studio是不同的）

对于使用 make_pair 时，有自己创建的类类型要让 make_pair 自动推导，也就是说不需要显式指定模板类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
using  namespace std;

template <class T1, class T2>
struct Pair
{
	T1 first;        // 第一个成员，一般表示key。
	T2 second;  // 第二个成员，一般表示value。
	Pair()  {
		cout << "调用了有默认的构造函数。\n";
	}
	Pair(const T1& val1, const T2& val2) :first(val1), second(val2)  {
		cout << "调用了有两个参数的构造函数。\n";
	}
	Pair(const Pair<T1, T2>& p) : first(p.first),second(p.second)  {
		cout << "调用了拷贝构造函数。\n";
	}
};

template <class T1, class T2>
Pair<T1, T2> make_Pair(const T1& first, const T2& second)
{
	// Pair<T1, T2> p(first, second);
	// return p;        // 返回局部对象。
	return Pair<T1, T2>(first, second);  // 返回临时对象。
}

int main()
{
	//pair<int, string> p0;
	//cout << "p0 first=" << p0.first << ",second=" << p0.second << endl;

	//pair<int, string> p1(1, "西施1");    // 两个参数的构造函数。
	//cout << "p1 first=" << p1.first << ",second=" << p1.second << endl;

	//pair<int, string> p2 = p1;             // 拷贝构造。
	//cout << "p2 first=" << p2.first << ",second=" << p2.second << endl;

	//pair<int, string> p3 = { 3, "西施3" };   // 两个参数的构造函数。
	//// pair<int, string> p3 { 3, "西施3" };   // 两个参数的构造函数，省略了等于号。
	//cout << "p3 first=" << p3.first << ",second=" << p3.second << endl;

	auto p4 = Pair<int, string>(4, "西施4");   // 匿名对象（显式调用构造函数）。
	cout << "p4 first=" << p4.first << ",second=" << p4.second << endl;

	auto p5 = make_Pair<int, string>(5, "西施5");   // make_pair()返回的临时对象。
	cout << "p5 first=" << p5.first << ",second=" << p5.second << endl;

	//pair<int, string> p6 = make_pair(6, "西施6");  // 慎用，让make_pair()函数自动推导，再调用拷贝构造，再隐式转换。
	//cout << "p6 first=" << p6.first << ",second=" << p6.second << endl;

	//auto p7 = make_pair(7, "西施7");    // 慎用，让make_pair()函数自动推导，再调用拷贝构造。
	//cout << "p7 first=" << p7.first << ",second=" << p7.second << endl;

	//p5.swap(p4);   // 交换两个pair。

	//cout << "p4 first=" << p4.first << ",second=" << p4.second << endl;
	//cout << "p5 first=" << p5.first << ",second=" << p5.second << endl;

	//struct st_girl
	//{
	//	string name;
	//	int   age;
	//	double height;
	//};
	//// 用pair存放结构体数据。
	//pair<int, st_girl> p = { 3,{"西施",23,48.6} };
	//cout << "p first=" << p.first << endl;
	//cout << "p second.name=" << p.second.name << endl;
	//cout << "p second.age=" << p.second.age << endl;
	//cout << "p second.height=" << p.second.height << endl;
}

map

map 容器封装了红黑树（平衡二叉排序树），用于查找。小于上个节点的在左，大于上个节点的在右。

包含头文件： #include<map>

map容器的元素是pair键值对。

map类模板的声明：

1
2
3
4
5
template <class K, class V, class P = less<K>, class _Alloc = allocator<pair<const K, V >>>
class map : public _Tree<_Tmap_traits< K, V, P, _Alloc, false>> 
{
   … 
}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数P：排序方法，缺省按key升序。

第四个模板参数_Alloc：分配器，缺省用new和delete。

map提供了双向迭代器。

成员函数

构造函数

1
2
3
4
5
map();  // 创建一个空的map容器。
map(initializer_list<pair<K,V>> il); // 使用统一初始化列表。
map(const map<K,V>& m);  // 拷贝构造函数。
map(Iterator first, Iterator last);  // 用迭代器创建map容器。
map(map<K,V>&& m);  // 移动构造函数（C++11标准）。

构造函数示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <map>
using  namespace std;

int main()
{
	// 1）map();  // 创建一个空的map容器。
	map<int, string> m1;

	// 2）map(initializer_list<pair<K, V>> il); // 使用统一初始化列表。
	map<int, string> m2( { { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } } );
	// map<int, string> m2={ { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } };
	// map<int, string> m2   { { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } };
	for (auto& val : m2)
		cout << val.first << "," << val.second << "  ";
	cout << endl;

	// 3）map(const map<K, V>&m);  // 拷贝构造函数。
	map<int, string> m3 = m2;
	for (auto& val : m3)
		cout << val.first << "," << val.second << "  ";
	cout << endl;

	// 4）map(Iterator first, Iterator last);  // 用迭代器创建map容器。
	auto first = m3.begin();  first++;
	auto last = m3.end();  last--;
	map<int, string> m4(first,last);
	for (auto& val : m4)
		cout << val.first << "," << val.second << "  ";
	cout << endl;
	
	// 5）map(map<K, V> && m);  // 移动构造函数（C++11标准）。
}

特性操作

1
2
3
size_t size() const;        // 返回容器的实际大小（已使用的空间）。
bool empty() const;      // 判断容器是否为空。
void clear();             // 清空容器。

元素操作

1
2
3
4
V &operator[](K key);             // 用给定的key访问元素。
const V &operator[](K key) const;  // 用给定的key访问元素，只读。
V &at(K key);                     // 用给定的key访问元素。
const V &at(K key) const;         // 用给定的key访问元素，只读。

注意：

  1. [ ]运算符：如果指定键不存在，会向容器中添加新的键值对；如果指定键存在，则读取或修改容器中指定键的值。

  2. at()成员函数：如果指定键不存在，不会向容器中添加新的键值对，而是直接抛出out_of_range 异常。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <map>
using  namespace std;

int main()
{
	map<string, string> m( { { "08","冰冰" }, { "03","西施" }, { "01","幂幂" }, { "07","金莲" }, { "05","西瓜" } } );
	
	cout << "m[08]=" << m["08"] << endl;     // 显示key为08的元素的value。
	cout << "m[09]=" << m["09"] << endl;    // 显示key为09的元素的value。key为09的元素不存在，将添加新的键值对。
	m["07"] = "花花";                                          // 把key为07的元素的value修改为花花。
	m["12"] = "小乔";                                          // 将添加新的键值对。

	for (auto& val : m)
		cout << val.first << "," << val.second << "  ";
	cout << endl;
}

赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1
2
1）map<K,V> &operator=(const map<K,V>& m);         // 把容器m赋值给当前容器。
2）map<K,V> &operator=(initializer_list<pair<K,V>> il);  // 用统一初始化列表给当前容器赋值。

交换操作

1
void swap(map<K,V>& m);    // 把当前容器与m交换。

交换的树的根节点。

比较操作

1
2
bool operator == (const map<K,V>& m) const;
bool operator != (const map<K,V>& m) const;

查找操作

  1. 查找键值为key的键值对
    在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。

    1
    2
    iterator find(const K &key); 
    const_iterator find(const K &key) const;  // 只读。

  2. 查找键值>=key的键值对

    在map容器中查找第一个键值>=key的键值对，成功返回迭代器；失败返回end()。

    1
    2
    iterator lower_bound(const K &key); 
    const_iterator lower_bound(const K &key) const;  // 只读。

  3. 查找键>key的键值对

    在map容器中查找第一个键值>key的键值对，成功返回迭代器；失败返回end()。

    1
    2
    iterator upper_bound(const K &key); 
    const_iterator upper_bound(const K &key) const;  // 只读。

  4. 统计键值对的个数

    统计map容器中键值为key的键值对的个数。因为 map 中的键是唯一的，所以返回值只能是 0 或者 1。

    1
    size_t count(const K &key) const;

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <map>
using  namespace std;

int main()
{
	map<string, string> m( { { "08","冰冰" }, { "03","西施" }, { "01","幂幂" }, { "07","金莲" }, { "05","西瓜" } } );

	for (auto& val : m)
		cout << val.first << "," << val.second << "  ";
	cout << endl;
	
	// 在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。
	auto it1 = m.find("05");
	if (it1 != m.end())
		cout << "查找成功：" << it1->first << "," << it1->second << endl;
	else
		cout << "查找失败。\n";

	// 在map容器中查找第一个键值 >= key的键值对，成功返回迭代器；失败返回end()。
	auto it2 = m.lower_bound("05");
	if (it2 != m.end())
		cout << "查找成功：" << it2->first << "," << it2->second << endl;
	else
		cout << "查找失败。\n";

	//	在map容器中查找第一个键值 > key的键值对，成功返回迭代器；失败返回end()。
	auto it3 = m.upper_bound("05");
	if (it3 != m.end())
		cout << "查找成功：" << it3->first << "," << it3->second << endl;
	else
		cout << "查找失败。\n";

	//	统计map容器中键值为key的键值对的个数。
	cout << "count(05)=" << m.count("05") << endl;   // 返回1。
	cout << "count(06)=" << m.count("06") << endl;   // 返回0。
}

插入和删除

1
2
3
4
5
6
7
8
9
1）void insert(initializer_list<pair<K,V>> il);  // 用统一初始化列表在容器中插入多个元素。
2）pair<iterator,bool> insert(const pair<K,V> &value);  // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。
3）void insert(iterator first,iterator last);  // 用迭代器插入一个区间的元素。
4）pair<iterator,bool> emplace (...);  // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。返回值pair：first是已插入元素的迭代器，second是插入结果。
例：mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));
5）iterator emplace_hint (const_iterator pos,...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义，如果提示的位置是正确的，对性能有提升，如果提示的位置不正确，性能反而略有下降，但是，插入是否成功与该参数元关。该参数常用end()和begin()。成功返回新插入元素的迭代器；如果元素已经存在，则插入失败，返回现有元素的迭代器。
6）size_t erase(const K & key);  // 从容器中删除指定key的元素，返回已删除元素的个数。
7）iterator erase(iterator pos);  // 用迭代器删除元素，返回下一个有效的迭代器。
8）iterator erase(iterator first,iterator last);  // 用迭代器删除一个区间的元素，返回下一个有效的迭代器。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <map>
using  namespace std;

class CGirl        // 超女类。
{
public:
	string m_name;   // 超女姓名。
	int      m_age;       // 超女年龄。

	/*CGirl() : m_age(0) {
		cout << "默认构造函数。\n";
	}*/
	CGirl(const string name, const int age) : m_name(name), m_age(age) {
		cout << "两个参数的构造函数。\n";
	}
	CGirl(const CGirl & g) : m_name(g.m_name), m_age(g.m_age) {
		cout << "拷贝构造函数。\n";
	}
};

int main()
{
	//map<int, CGirl> mm;
	//mm.insert     (pair<int, CGirl>(8, CGirl("冰冰", 18)));                // 一次构造函数，两次拷贝构造函数。
	//mm.insert     (make_pair<int, CGirl>(8, CGirl("冰冰", 18)));     // 一次构造函数，两次拷贝构造函数。
	//mm.emplace(pair<int, CGirl>(8, CGirl("冰冰", 18)));                // 一次构造函数，两次拷贝构造函数。
	//mm.emplace(make_pair<int, CGirl>(8, CGirl("冰冰", 18)));     // 一次构造函数，两次拷贝构造函数。
	//mm.emplace(8, CGirl("冰冰", 18));                                             // 一次构造函数，一次拷贝构造函数。
	//mm.emplace(8, "冰冰", 18);                                                        // 错误。
	//mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));  // 一次构造函数。

	//for (const auto& val : mm)
	//	cout << val.first << "," << val.second.m_name << "," << val.second.m_name << "  ";
	//cout << endl;

	//return 0;

	map<int, string> m;

	// 1）void insert(initializer_list<pair<K,V>> il);  // 用统一初始化列表在容器中插入多个元素。
	m.insert({ { 8,"冰冰" }, { 3,"西施" }});
	m.insert({ pair<int,string>(1,"幂幂"), make_pair<int,string>(7,"金莲"), {5,"西瓜"}});
	m.insert({ { 18,"冰冰" }, { 3,"西施" } });

	// 2）pair<iterator,bool> insert(const pair<K,V> &value);  
	// 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。
	auto ret = m.insert(pair<int, string>(18, "花花"));
	if (ret.second == true) cout << "插入成功：" << ret.first->first << "," << ret.first->second << endl;
	else cout << "插入失败。\n";

	// 3）void insert(iterator first, iterator last);  // 用迭代器插入一个区间的元素。

	// 4）pair<iterator, bool> emplace(...);  
	// 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。
	// 返回值pair：first是已插入元素的迭代器，second是插入结果。
	auto ret1 = m.emplace(20, "花花");
	if (ret1.second == true) cout << "插入成功：" << ret1.first->first << "," << ret1.first->second << endl;
	else cout << "插入失败。\n";

	// 5）iterator emplace_hint(const_iterator pos, ...); 
	// 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义，如果提示的位置是正确的，
	// 对性能有提升，如果提示的位置不正确，性能反而略有下降，但是，插入是否成功与该参数元关。
	// 该参数常用end()和begin()。成功返回新插入元素的迭代器；如果元素已经存在，则插入失败，返回现
	// 有元素的迭代器。
	m.emplace_hint(m.begin(), piecewise_construct, forward_as_tuple(23), forward_as_tuple("冰棒")); 

	for (auto& val : m)
		cout << val.first << "," << val.second << "  ";
	cout << endl;
}

unordered_map

哈希表

哈希表（数组+链表）中，桶是数组，桶的元素是链表。

哈希表要扩容，则必须要重新分配内存。

哈希表的表长不一样了，那么哈希函数肯定也就不一样，因此所有元素要重新哈希，要重新散列。用新的方法把元素分布到不同的桶中。

哈希表长（桶的个数）： 数组的长度。

哈希函数： size_t hash(const T &key) {… // key % 小于哈希表长的最大质数。}

装填因子： 元素总和/表长，值越大，效率越低。

容器是否扩展由装填因子决定，装填因子在 unordered_map 中是元素数量除以桶数。装填因子达到最大（默认为1，可通过 max_load_factor 设置）则会自动扩展。

umap 扩容时需要将全部已分配的数组和链表销毁，重新哈希，代价很大，与 vector 扩容类似。

pigpAfA.png

unordered_map

unordered_map容器封装了哈希表，查找、插入和删除元素时，只需要比较几次key的值。

包含头文件： #include<unordered_map>

unordered_map容器的元素是pair键值对。

unordered_map类模板的声明：

1
2
3
4
5
template <class K, class V, class _Hasher = hash<K>, class _Keyeq = equal_to<K>, class _Alloc = allocator<pair<const K, V>>>
class unordered_map : public _Hash<_Umap_traits<K, V, _Uhash_compare<K, _Hasher, _Keyeq>, _Alloc, false>>
{
   …
}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数_Hasher：哈希函数，默认值为std::hash<K>

第四个模板参数_Keyeq：比较函数，用于判断两个key是否相等，默认值是std::equal_to<K>。

第五个模板参数_Alloc：分配器，缺省用new和delete。

创建std::unordered_map类模板的别名：

1
2
template<class K,class V>
using umap = std::unordered_map<K, V>;

构造函数

因为哈希表的扩容代价很高，因此在构造函数中提供了指定桶个数的参数。

1
2
3
4
5
6
7
8
1）umap();  // 创建一个空的umap容器。
2）umap(size_t bucket);  // 创建一个空的umap容器，指定了桶的个数，下同。
3）umap(initializer_list<pair<K,V>> il); // 使用统一初始化列表。
4）umap(initializer_list<pair<K,V>> il, size_t bucket); // 使用统一初始化列表。
5）umap(Iterator first, Iterator last);  // 用迭代器创建umap容器。
6）umap(Iterator first, Iterator last, size_t bucket);  // 用迭代器创建umap容器。
7）umap(const umap<K,V>& m);  // 拷贝构造函数。
8）umap(umap<K,V>&& m);  // 移动构造函数（C++11标准）。

特性操作

当前装填因子达到最大装填因子时，容器就会扩容，即第 7 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1）size_t size() const;        // 返回容器中元素的个数。
2）bool empty() const;      // 判断容器是否为空。
3）void clear();             // 清空容器。
4）size_t max_bucket_count();     // 返回容器底层最多可以使用多少桶，无意义。
5）size_t bucket_count();          // 返回容器桶的数量，空容器有8个桶。
6）float load_factor();   // 返回容器当前的装填因子，load_factor() = size() / bucket_count()。
7）float max_load_factor();        // 返回容器的最大装填因子，达到该值后，容器将扩充，缺省为1。
8）void max_load_factor (float z ); // 设置容器的最大装填因子。
9）iterator begin(size_t n);        // 返回第n个桶中第一个元素的迭代器。
10）iterator end(size_t n);          // 返回第n个桶中最后一个元素尾后的迭代器。
11）void reserve(size_t n);          // 将容器设置为至少n个桶。
12）void rehash(size_t n);           // 将桶的数量调整为>=n。如果n大于当前容器的桶数，该方法会将容器重新哈希；如果n的值小于当前容器的桶数，该方法可能没有任何作用。
13）size_t bucket_size(size_t n);     // 返回第n个桶中元素的个数，0 <= n < bucket_count()。
14）size_t bucket(K &key);          // 返回值为key的元素对应的桶的编号。

元素操作

1
2
3
4
V &operator[](K key);             // 用给定的key访问元素。
const V &operator[](K key) const;  // 用给定的key访问元素，只读。
V &at(K key);                     // 用给定的key访问元素。
const V &at(K key) const;         // 用给定的key访问元素，只读。

注意：

  1. [ ]运算符：如果指定键不存在，会向容器中添加新的键值对；如果指定键不存在，则读取或修改容器中指定键的值。

  2. at()成员函数：如果指定键不存在，不会向容器中添加新的键值对，而是直接抛出out_of_range 异常。

赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1
2
1）umap<K,V> &operator=(const umap<K,V>& m);       // 把容器m赋值给当前容器。
2）umap<K,V> &operator=(initializer_list<pair<K,V>> il);  // 用统一初始化列表给容器赋值。

交换操作

1
void swap(umap<K,V>& m);    // 把当前容器与m交换。

比较操作

1
2
bool operator == (const umap<K,V>& m) const;
bool operator != (const umap<K,V>& m) const;

查找操作

1）查找键值为key的键值对

在umap容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。

1
2
iterator find(const K &key); 
const_iterator find(const K &key) const;  // 只读。

2）统计键值对的个数

统计umap容器中键值为key的键值对的个数。

1
size_t count(const K &key) const;

插入和删除

使用 insert，若是有相同的key存在，则不会插入新元素或修改原有元素。

1
2
3
4
5
6
7
8
9
1）void insert(initializer_list<pair<K,V>> il);  // 用统一初始化列表在容器中插入多个元素。
2）pair<iterator,bool> insert(const pair<K,V> &value);  // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。
3）void insert(iterator first,iterator last);  // 用迭代器插入一个区间的元素。
4）pair<iterator,bool> emplace (...);  // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。返回值pair：first是已插入元素的迭代器，second是插入结果。
例：mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));
5）iterator emplace_hint (const_iterator pos,...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义。对哈希容器来说，此函数意义不大。
6）size_t erase(const K & key);  // 从容器中删除指定key的元素，返回已删除元素的个数。
7）iterator erase(iterator pos);  // 用迭代器删除元素，返回下一个有效的迭代器。
8）iterator erase(iterator first,iterator last);  // 用迭代器删除一个区间的元素，返回下一个有效的迭代器。

queue

queue容器的逻辑结构是队列，物理结构可以是数组或链表，主要用于多线程之间的数据共享。queue容器不支持迭代器。

包含头文件： #include<queue>

queue类模板的声明：

1
2
3
4
template <class T, class _Container = deque<T>>
class queue{
    ……
}

第一个模板参数T：元素的数据类型。

第二个模板参数_Container：底层容器的类型，缺省是std::deque，可以用std::list ，还可以用自定义的类模板，不可以用 std::vector。

构造函数

1
2
3
4
1）queue();  // 创建一个空的队列。
2）queue(const queue<T>& q);  // 拷贝构造函数。
3）queue(queue<T>&& q);  // 移动构造函数（C++11标准）。
析构函数~queue()释放内存空间。

常用操作

1
2
3
4
5
6
7
8
9
1）void push(const T& value);  // 元素入队。
2）void emplace(…);           // 元素入队，…用于构造元素。C++11
3）size_t size() const;          // 返回队列中元素的个数。
4）bool empty() const;        // 判断队列是否为空。
5）T &front();                 // 返回队头元素。
6）const T &front();           // 返回队头元素，只读。
7）T &back();                 // 返回队尾元素。
8）const T &back();           // 返回队头元素，只读。
9）void pop();                // 出队，删除队头的元素。

其它操作

1
2
3
4
1）queue &operator=(const queue<T> &q);    // 赋值。
2）void swap(queue<T> &q);    // 交换。
3）bool operator == (const queue<T> & q) const; // 重载==操作符。
4）bool operator != (const queue<T> & q) const; // 重载!=操作符。

其它 11 种容器

STL 的 array 是在栈上分配内存的，其它容器是在堆上分配内存。

std::array

在栈上分配内存，创建数组的时候，数组长度必须是常量，创建后的数组大小不可变。随机访问迭代器。比常规数组更方便（能用于模板），可以代替常规数组。

1
2
3
4
5
6
template<class T, size_t size>
class array{
private:
	T elems_[size]; 
	……
};

array 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
1）void fill(const T & val);     // 给数组填充值（清零）。
2）size_t size();               // 返回数组的大小。
3）bool empty() const;        // 无意义。
4）T &operator[](size_t n); 
5）const T &operator[](size_t n) const;  // 只读。
6）T &at(size_t n); 
7）const T &at(size_t n) const;          // 只读。
8）T *data();            // 返回数组的首地址。
9）const T *data() const; // 返回数组的首地址。
10）T &front();          // 第一个元素。
11）const T &front();    // 第一个元素，只读。
12）const T &back();    // 最后一个元素，只读。
13）T &back();        // 最后一个元素。

示例：

可以用模板传参，避免参数需要数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <array>
using  namespace std;

////void func(int arr[][6],int len)
//void func(int (* arr)[6], int len)
//{
//	for (int ii = 0; ii < len; ii++)
//	{
//		for (int jj = 0; jj < 6; jj++)
//			cout << arr[ii][jj] << " ";
//		cout << endl;
//	}
//}

//void func(const array < array<int, 5>, 10 >& arr)  
//{
//	for (int ii = 0; ii < arr.size(); ii++)
//	{
//		for (int jj = 0; jj < arr[ii].size(); jj++)
//			cout << arr[ii][jj] << " ";
//		cout << endl;
//	}
//}

template <typename T>
void func(const T& arr)
{
	for (int ii = 0; ii < arr.size(); ii++)
	{
		for (int jj = 0; jj < arr[ii].size(); jj++)
			cout << arr[ii][jj] << " ";
		cout << endl;
	}
}

int main()
{
	//int aa[11] = {1,2,3,4,5,6,7,8,9,10,11};         // 一维数组。
	//array<int, 10> aa = { 1,2,3,4,5,6,7,8,9,10 };         // 一维数组。
	//for (int ii = 0; ii < 10; ii++)            // 传统的方法。
	//	cout << aa[ii] << " ";
	//cout << endl;
	//
	//for (int ii = 0; ii < aa.size(); ii++)  // 利用array的size()方法。
	//	cout << aa[ii] << " ";
	//cout << endl;
	//
	//for (auto it= aa.begin(); it < aa.end(); it++)      // 使用迭代器。
	//	cout << *it << " ";
	//cout << endl;

	//for (auto val : aa)                           // 基于范围的for循环。
	//	cout << val << " ";
	//cout << endl;

	//int bb[10][6];
	//for (int ii = 0; ii < 10; ii++)  // 对二维数组赋值。
	//{
	//	for (int jj = 0; jj < 6; jj++)
	//		bb[ii][jj] = jj * 10 + ii;
	//}

	//func(bb,10);  // 把二维数组传给函数。

	array< array<int, 5>, 10 > bb;  // 二维数组，相当于int bb[10][5]。
	 
	for (int ii = 0; ii < bb.size(); ii++)  // 对二维数组赋值。
	{
		for (int jj = 0; jj < bb[ii].size(); jj++)
			bb[ii][jj] = jj * 10 + ii;
	}

	func(bb);  // 把二维数组传给函数。
}

deque

双端队列。随机访问迭代器。

deque容器存储数据的空间是多段等长的连续空间构成，各段空间之间并不一定是连续的。

为了管理这些连续空间的分段，deque容器用一个数组存放着各分段的首地址。

pigiXMn.png

通过建立数组，deque容器的分段的连续空间能实现整体连续的效果。

当deque容器在头部或尾部增加元素时，会申请一段新的连续空间，同时在数组中添加指向该空间的指针。

特点

  • 提高了在两端插入和删除元素的效率，扩展空间的时候，不需要拷贝以前的元素。

  • 在中间插入和删除元素的效率比vector更糟糕。

  • 随机访问的效率比vector容器略低。

操作

类似 vector，但是deque有push_front等

forward_list（单链表）

物理结构：单链表

迭代器：正向迭代器

比双链表少了一个指针，可节省一丢丢内存，减少了两次对指针的赋值操作。

如果单链表能满足业务需求，建议使用单链表而不是双链表。

操作与 list 类似。

multimap

底层是红黑树。

multimap和map的区别在：multimap允许关键字重复，而map不允许重复。

各种操作与map容器相同。

set&multiset

底层是红黑树。

set和map的区别在：map中存储的是键值对，而set只保存关键字。

multiset和set的区别在：multiset允许关键字重复，而set不允许重复。

各种操作与map容器相同。

unordered_multimap

底层是哈希表。

unordered_multimap和unordered_map的区别在：unordered_multimap允许关键字重复，而unordered_map不允许重复。

各种操作与unordered_map容器相同。

unordered_set&unordered_multiset

底层是哈希表。

unordered_set和unordered_map的区别在：unordered_map中存储的是键值对，而unordered_set只保存关键字。

unordered_multiset和unordered_set的区别在：unordered_multiset允许关键字重复，而unordered_set不允许重复。

各种操作与unordered_map容器相同。

priority_queue（优先队列）

底层容器可以用deque和list。

优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。

各种操作与queue容器相同。

stack（栈）

底层容器可以用deque和list。

STL 算法

#include <algorithm>

全部 stl 函数的前两个参数都是迭代器区间，后面的参数不一定。

仿函数本质是类中的重载函数，相比普通函数可以携带更多的信息，如在传递仿函数时，可以使用类的有参构造函数等。传入仿函数时要加括号，表示创建匿名函数对象。

要使用 STL 提供的仿函数，需要包含 #include <functional>，内部是用结构体模板实现的，因为结构体默认是 public，代码更简单。

STL提供了很多处理容器的函数模板，它们的设计是相同的，有以下特点：

  1. 用迭代器表示需要处理数据的区间。

  2. 返回迭代器放置处理数据的结果（如果有结果）。

  3. 接受一个函数对象参数（结构体模板），用于处理数据（如果需要）。

传统编程思想：函数参数传对象的地址或引用。

模板的思想：函数参数传迭代器，因为传对象的地址或引用，函数只能支持某种类型的容器。但是传迭代器，函数可以支持多种容器，只要有迭代器就行。

重载了小括号的类也叫做仿函数。

for_each 函数

模板思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>
#include <list>

using std::cout;
using std::endl;

// version 1 2 3
// void func(const int& p)
// {
//     cout << p << endl;
// }

// class fun
// {
// public:
//     void operator()(const int& val)
//     {
//         cout << val << endl;
//     }
// };

// version 1：固定类型
// void foreach(const std::list<int>::iterator& p1, const std::list<int>::iterator& p2)
// {
//     for(auto it = p1; it!=p2; it++)
//     {
//         cout << *it << endl;
//     }
// }

// version 2：只要有迭代器操作的类型就行
// template <typename T>
// void foreach(const T& p1, const T& p2)
// {
//     for(auto it = p1; it!=p2; it++)
//     {
//         cout << *it << endl;
//     }
// }

// version 3-1：用户传入自定义操作函数
// template <typename T>
// void foreach(const T& p1, const T& p2, void (*pfun)(const int&))
// {
//     for(auto it = p1; it!=p2; it++)
//     {
//         pfun(*it);
//     }
// }

// version 3-2：用户传入自定义操作仿函数
// template <typename T>
// void foreach(const T& p1, const T& p2, fun f1)
// {
//     for(auto it = p1; it!=p2; it++)
//     {
//         f1(*it);
//     }
// }

// version 4：全部参数模板化，包括函数和类，都变成模板
template <typename T1, typename T2>
void foreach(const T1& p1, const T1& p2, T2 f)
{
    for(auto it = p1; it!=p2; it++)
    {
        f(*it);
    }
}

template <typename T>
void func(T p)
{
    cout << p << endl;
}

template <class T>
class fun
{
public:
    void operator()(T val)
    {
        cout << val << endl;
    }
};

int main()
{
    // std::vector<int> vec{1, 2, 3, 4, 5, 6};
    std::vector<std::string> vec{"1", "2", "3", "4", "5", "6"};

    // foreach(vec.begin(), vec.end(), func); version 3-1
    // foreach(vec.begin(), vec.end(), fun()); version 3-2

    foreach(vec.begin(), vec.end(), func<std::string>);
    foreach(vec.begin(), vec.end(), fun<std::string>());

    return 0;
}

find_if

第三个参数传递一个返回值类型为 bool 的函数或仿函数用于判断是否满足条件，满足条件则 find_if 返回当前迭代器，不满足条件返回最后的迭代器。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>  // STL算法函数头文件。
using  namespace std;

template<typename T>
bool zsshow(const T& no)    // 张三的个性化表白函数。
{
	if (no != 3) return false;
	cout << "亲爱的" << no << "号：我是一只傻傻鸟。\n";
	return true;
}

template<typename T>
class czs   // 张三的个性化表白仿函数。
{
public:
	T m_no;     // 存放张三喜欢的超女编号。
	czs(const T& no) : m_no(no) {}  // 构造函数的参数是张三喜欢的超女编号。
	bool operator()(const T& no) {
		if (no != m_no) return false;
		cout << "亲爱的" << no << "号：我是一只傻傻鸟。\n";
		return true;
	}
};

template<typename T1, typename T2>
T1 findif(const T1 first, const T1 last, T2 pfun)
{
	for (auto it = first; it != last; it++)
		if (pfun(*it) ==true)  return it;        // 用迭代器调用函数对象。

	return last;
}

int main()
{
	vector<int> bh = { 5,8,2,6,9,33,1,7 };   // 存放超女编号的容器。
	//list<string> bh = { "05","08","02","06","09","03","01","07" };   // 存放超女编号的容器。

	auto it1=find_if(bh.begin(), bh.end(), zsshow<int>);  // 第三个参数是模板函数。
	if (it1 == bh.end()) cout << "查找失败。\n";
	else cout << "查找成功：" << *it1 << endl;

	auto it2=find_if(bh.begin(), bh.end(), czs<int>(8));       // 第三个参数是仿函数。
	if (it2 == bh.end()) cout << "查找失败。\n";
	else cout << "查找成功：" << *it2 << endl;
}

sort

主要用于 vector 的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>   // STL算法函数。
#include <functional>   // STL仿函数。
using  namespace std;

template<typename T>
bool compasc(const T& left, const T& right)   {     // 普通函数，用于升序。
	return left < right;
}

template<typename T>
struct _less
{
	bool operator()(const T& left, const T& right) { // 仿函数，用于升序。
		return left < right;
	}
};

template<typename T>
bool compdesc(const T& left, const T& right) {     // 普通函数，用于降序。
	return left > right;
}

template<typename T>
class _greater
{
public:
	bool operator()(const T& left, const T& right) { // 仿函数，用于降序。
		return left > right;
	}
};

template<typename T, typename compare>
void bsort(const T first, const T last, compare comp)  // 冒泡排序。
{
	while(true)
	{
		bool bswap = false;        // 本轮遍历已交换过元素的标识，true-交换过，false-未交换过。
		for (auto it = first; ; )
		{
			auto left = it;                  // 左边的元素。
			it++;
			auto right = it;               // 右边的元素。
			if (right == last) break;  // 表示it1已经是最后一个元素了。

			//if (*left > *right)             // 如果左边的元素比右边大，交换它们的值。
			//if (*left < *right)             // 如果左边的元素比右边小，交换它们的值。
			// 排序规则：如果comp()返回true，left排在前面（升序），否则right排在前面（降序）。
			if (comp(*left, *right) == true)  continue;

			// 交换两个元素的值。
			auto tmp = *right;
			*right = *left;
			*left = tmp;
			bswap = true;        // 一轮遍历已交换过元素的标识。
		}

		if (bswap == false) break;  // 如果在for循环中不曾交换过元素，说明全部的元素已有序。
	}
}

int main()
{
	vector<int> bh = { 5,8,2,6,9,33,1,7 };   // 存放超女编号的容器。
	//list<string> bh = { "05","08","02","06","09","03","01","07" };   // 存放超女编号的容器。

	//bsort(bh.begin(), bh.end(),compasc<int>);        // 普通函数（升序）。
	//bsort(bh.begin(), bh.end(), compdesc<int>);     // 普通函数（降序）。

	//bsort(bh.begin(), bh.end(),_less<int>());             // 仿函数（升序）。
	//bsort(bh.begin(), bh.end(), _greater<int>());      // 仿函数（降序）。

	//bsort(bh.begin(), bh.end(), less<int>());             // STL提供的仿函数（升序）。
	//bsort(bh.begin(), bh.end(), greater<int>());       // STL提供的仿函数（降序）。

	//sort(bh.begin(), bh.end(),_less<int>());             // 仿函数（升序）。
	sort(bh.begin(), bh.end(), _greater<int>());      // 仿函数（降序）。

	for (auto val : bh)
		cout << val << " ";
	cout << endl;
}

其它STL算法函数

STL将算法函数分成四组：

  1. 非修改式序列操作：对区间中的每个元素进行操作，这些操作不修改容器的内容。

  2. 修改式序列操作：对区间中的每个元素进行操作，这些操作可以容器的内容（可以修改值，也可以修改排列顺序）。

  3. 排序和相关操作：包括多个排序函数和其它各种函数，如集合操作。

  4. 通用数字运算：包括将区间的内容累积、计算两个容器的内部乘积、计算小计、计算相邻对象差的函数。通常，这些都是数组的操作特性，因此vector是最有可能使用这些操作的容器。

前三组在头文件#include <algorithm>中，第四组专用于数值数据，在#include <numeric>中。

详见《C++ Primer plus》，第六版，从886页开始。

  1. 如果容器有成员函数，则使用成员函数，如果没有才考虑用STL的算法函数。
  2. 把全部的STL算法函数过一遍，知道大概有些什么东西。
  3. 如果打算采用某算法函数，一定要搞清楚它的原理，关注它的效率。
  4. 不要太看重这些算法函数，自己写一个也就那么回事。
  5. 不是因为简单，而是因为不常用。