c++ stl（标准模板库）

1. 引言

STL（标准模板库），从广义上分为：容器，算法，迭代器，容器和算法之间通过迭代器进行无缝连接。

在 c++ 标准种，STL被组织成以下13个头文件：

<algorithm>
<deque>
<functional>
<iterator>
<vector>
<list>
<map>
<memory>
<numeric>
<queue>
<stack>
<utility>
1
2
3
4
5
6
7
8
9
10
11
12

容器总体分为两种：

• 序列式容器：容器的元素的位置是由进入容器的时机和地点来决定的。
• 关联式容器：容器已经有规则，进入容器的元素的位置不是由进入容器的时机和地点来决定的。

容器是可以嵌套使用的，也就是容器可以装容器。

迭代器起到指针的作用，对指针的操作基本都可以对迭代器操作。实际上，迭代器式一个类，这个类封装一个指针。

算法，通俗的解释，就是通过优先步骤，解决一个问题。

下面给出一个简单的示例，通过这个示例，我们可以很直观的看到容器、迭代器、算法之间的密不可分的关系：

#include 
#include 
#include 
using namespace std;

void printVector(int v) 
{
	cout << v << " ";
}

int main()
{
	//容器
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

	//迭代器
	vector<int>::iterator pBegin = v.begin();
	vector<int>::iterator pEnd = v.end();

	//算法
	for_each(pBegin, pEnd, printVector);

	return 0;
}
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

2. string 容器

2.1 简要说明

• string是一个类，内部封装了char*，是一个char*型的容器。
• 封装了很多成员方法。
• 自动管理char*内存，不用主动定义字符串的长度。

string 和 char* 可以互相转换：

//string 转 char*
string str = "itcast";
const char* cstr = str.c_str();

//char* 转 string
const char* s = "itcast";
string sstr(s);
1
2
3
4
5
6
7

2.2 string 常用 API

（1）构造函数

（2）赋值

• assign()
• =

（3）取值

• []
• at()

两者的区别：[]方式如果访问越界，直接挂了，at()方式如果访问越界，抛出异常。

（4）拼接

• “+”
• “+=”
• str.append()

（5）查找和替换

• find()：查找第一次出现的位置
• rfind()：查找最后一次出现的位置
• replace()：把给定一段区间替换成别的字符串

（6）比较

• compare()

（7）子串

• substr()

（8）插入和删除

• insert()
• erase()

3. vector 容器

3.1 简要说明

• vector 容器是动态数组。
• 单口容器，即从尾部插入（push_back）和删除（pop_back）的效率更高。从其他位置插入删除会引起其他元素的移动，从而效率低下。
• 提供insert()来从指定位置插入。
• 用begin()和end()标识指向第一个元素和最后一个元素的下一个位置，用rbegin()和rend()标识指向最后一个元素和第一个元素的上一个位置。
• 支持随机访问。

随机访问的概念：迭代器支持加减一个数的操作，比如v.begin() + 2

3.2 vector 常用 API

（1）构造函数

（2）赋值

• assign()
• =
• swap()

（3）大小

• size()
• empty()
• resize()：重新指定容器的长度，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
• capacity()
• reserve()：预留容器的容量，但不初始化，元素不可访问。

（4）取值

• at()：若超出范围，抛异常
• []：若超出范围，不抛异常，直接挂
• front()：返回第一个元素
• back()：返回最后一个元素

（5）插入和删除

• push_back()
• insert()
• pop_back()
• emplace()
• emplace_back()
• erase()

c++ 11中，针对顺序容器（如vector、deque、list），新标准引入了三个新成员，emplace_front()、emplace_back()、emplace()，分别对应push_front()、push_back()、insert()，允许我们将元素放置在容器头部、容器尾部或一个指定位置之前，但emplace_front()、emplace_back()、emplace()的效率更高。

（6）用swap()缩减容量

int main()
{
	vector<int> vec;
	for (int i = 0; i < 1000; i++) {
		vec.push_back(i);
	}
	cout << vec.size() << endl;//1000
	cout << vec.capacity() << endl;//1066
	vec.resize(10);
	cout << vec.size() << endl;//10
	cout << vec.capacity() << endl;//1066

	vector<int> v(vec);
	cout << v.size() << endl;//10
	cout << v.capacity() << endl;//10

	//结论：resize只影响vector的元素的数量，但不会影响vector的容量，但vector的拷贝构造函数会使容量等于元素数量

	//因此可以用匿名对象 + swap来缩小容量，swap的功能是交换两个对象
	vector<int>(vec).swap(vec);
	cout << v.size() << endl;//10
	cout << v.capacity() << endl;//10
	
	return 0;
}
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

4. deque 容器

4.1 简要说明

• 双端数组，可以从头部和尾部进行插入和删除，push_back(), pop_back(), push_front(), pop_front()。
• begin()返回一个迭代器，指向第一个元素，end()返回一个迭代器，指向最后一个元素的下一个位置，front()返回第一个元素，back()返回最后一个元素。
• insert()可以指定位置插入，但会导致元素移动，降低效率。
• 可随机存取，效率高。

4.2 deque 常用 API

（1）构造函数

（2）赋值

• assign()
• =
• swap()

（3）大小操作

• size()
• empty()
• resize()

（4）插入和删除

• push_back()
• push_front()
• pop_back()
• pop_front()
• insert()
• erase()
• emplace()
• emplace_back()
• emplace_front()

（5）存取

• at()
• []
• front()
• back()

5. stack 容器

5.1 简要说明

• 先进后出，通过压栈push()从栈顶增加元素，通过出栈pop()从栈顶删除元素。
• 不能遍历（不提供迭代器），不支持随机存取。只能通过top()访问栈顶元素。

5.2 stack 常用 API

（1）构造函数

（2）插入和删除

• push()
• pop()

（3）取值

• top()

6. queue 容器

6.1 简要说明

• 先进先出，通过入队push()从队尾增加元素，通过出队pop()从队头删除元素。
• front()返回队头元素，back()返回队尾元素。
• 不能进行遍历（不提供迭代器），不支持随机访问。

6.2 queue 常用 API

（1）构造函数

（2）存取、插入、删除

• push()
• pop()
• back()
• front()

（3）赋值

• =

（4）大小

• empty()
• size()

7. list 容器

7.1 简要说明

• 双向链表，每个结点由data、prev指针和next指针构成，头节点的prev指针指向null，尾节点的next指针指向null。
• 通过push_back()和pop_back()从尾部添加和删除元素，通过push_front()和pop_front()从头部添加和删除元素。通过insert()从给定位置之前插入元素。
• begin()返回指向链表头的迭代器，end()返回指向链表尾的迭代器。
• 不支持随机访问，只能迭代器++或–。

7.2 list 常用 API

（1）构造函数

（2）插入和删除

• push_back()
• pop_back()
• push_front()
• pop_front()
• insert()
• clear()
• erase()
• remove(elem)：删除容器中所有与值elem匹配的元素。

（3）大小

• size()
• empty()
• resize()

（4）赋值

• assign()
• =
• swap()

（5）取值

• front()
• back()

（6）翻转链表

• reverse()
• sort()

这是list中自带的reverse和sort，不是算法中的reverse和sort。算法中的只支持可随机访问的容器。

8. set/multiset 容器

8.1 简要说明

• set/multiset的特性是所有元素会根据元素的值自动进行排序，默认升序排序。set/multiset是以红黑树尾底层机制，其查找效率非常好。set容器中不允许重复元素，multiset允许重复元素。
• 通过insert()插入数据，自动排序。
• 可以遍历（提供迭代器），不支持随机存取。
• set/multiset不能通过迭代器改变元素的值，因此这样会打破set/multiset的排序规则。

8.2 set/multiset 常用 API

（1）构造函数

（2）赋值

• =
• swap()

（3）大小

• size()
• empty()

（4）插入和删除

• insert()
• clear()
• erase()

（5）查找

• find(key)：返回迭代器
• lower_bound(keyElem)：返回第一个key>=keyElem元素的迭代器
• upper_bound(keyElem)：返回第一个key>keyElem元素的迭代器
• equal_range(keyElem)：返回lower_bound和upper_bound的两个迭代器，数据结构是pair(iterator, iterator)。

8.3 自定义set/multiset的排序规则

我们可以使用仿函数来定义，仿函数是一个类，在这个类中我们重载()运算符。

//仿函数
class mycompare { //用struct定义也可以
public:
	bool operator()(const int& v1, const int& v2) const {
		return v1 > v2;
	}
};

int main()
{
	set<int, mycompare> s;
	s.insert(1);
	s.insert(2);
	s.insert(-1);
	s.insert(5);
	for (auto it = s.begin(); it != s.end(); it++) {
		cout << *it << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

9. pair（对组）容器

9.1 简要说明

• pair 将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个共有函数first()和second()访问。
• 可以通过pair的构造函数创建队组，也可以通过make_pair()函数创建队组。

10. map/multimap 容器

10.1 简要说明

• map相对于set，具有key 和 value，所有元素根据key自动排序。pair的第一元素被称为键值，第二元素被称为实值。map也是以红黑树为底层实现机制。
• map的元素是pair
• key不能修改，value可以修改

10.2 map/multimap 常用 API

（1）构造函数

（2）赋值

• =
• swap()

（3）大小

• size()
• empty()

（4）插入和删除

• insert(pair(1,2))
• insert(make_pair(1,2))
• emplace(1,2)
• clear()
• erase()

（5）查找

• find(key)：返回迭代器
• lower_bound(keyElem)：返回第一个key>=keyElem元素的迭代器
• upper_bound(keyElem)：返回第一个key>keyElem元素的迭代器
• equal_range(keyElem)：返回lower_bound和upper_bound的两个迭代器，数据结构是pair(iterator, iterator)。

11. unordered_set/unordered_multiset 容器

11.1 简要说明

• 无序 set/multiset 容器，和 set/multiset 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
• 不再以键值对的形式存储数据，而是直接存储数据的值。
• 容器内部存储的各个元素的值不能被修改。
• 不会对内部存储的数据进行排序，因为底层采用哈希表结构存储数据。

unordered_set 容器的类模板定义如下：

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;
1
2
3
4
5

可以看到，以上 4 个参数中，只有第一个参数没有默认值，这意味着如果我们想创建一个 unordered_set 容器，至少需要手动传递 1 个参数。事实上，在 99% 的实际场景中最多只需要使用前 3 个参数（各自含义如表 1 所示），最后一个参数保持默认值即可。

12. unordered_map/unordered_multimap 容器

12.1 简要说明

• 无序 map/multimap 容器，和 map/multimap 容器很像，唯一的区别就在于，map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
• 底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

unordered_map 容器模板的定义如下所示：

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;
1
2
3
4
5
6

以上 5 个参数中，必须显式给前 2 个参数传值，并且除特殊情况外，最多只需要使用前 4 个参数，各自的含义和功能如表 1 所示。