STL总结

发表于   |   分类于   |  

STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。
组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。
本文就是主要介绍STL的基本内容。

序列容器

1
容器里的元素是有位置的,有前有后

array

1
2
3
4
5
静态连续数组.
C++11中新增.
大小是固定的,不能改变.
和C语言中本来支持的数组[]特性类似;
支持随机存取, 支持容器都支持的迭代器操作,支持判断数组中元素的数量等操作;

vector

1
2
3
4
5
动态连续数组.
大小可变
使用的内存是连续的.
所以支持随机存取
在末端的增删操作性能好,但是中间的插入删除性能差.

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.pop_back();
v.push_back(4);
cout << v.front() << endl;
for(vector<int>::iterator ite = v.begin(); ite != v.end(); ite++){
	cout << *ite << endl; 
}
//输出
1
1
2
3

deque

1
2
3
4
5
6
双头队列;
可在头部和尾部插入删除;
使用的内存是不连续的, 但是一段一段的;
随机存取时间复杂度为o(1);
头尾插入删除基本也是o(1);
插入删除任意元素是o(n)

forward_list

1
2
3
4
单向链表;
c++11中新增;
不支持随机存取;
列表里增加,删除,移动一个元素, 不会使得指向其他元素的迭代器失效, 只会使自己失效;

list

1
2
3
双向链表
插入删除元素常量时间;
增加, 删除, 移动元素, 不会使得其他元素的迭代器失效;

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_front(3);
l.insert(l.begin(),4);
l.insert(l.end(), 5);
list<int>::iterator iter = find(l.begin(), l.end(), 1);
if(iter != l.end())
{
	cout << "Found 1 in the list." << endl; 
} 
for(iter = l.begin(); iter != l.end(); iter++)
{
	cout << *iter << endl;
}
//输出
Found 1 in the list.
4
3
1
2
5

关联容器

1
关联容器里的值,都按照某种规则(元素值的大小)进行了排序;

set

1
2
3
集合
包含的都是关键字, 每个都是唯一的;
搜索, 删除 , 插入的时间复杂度是o(log(n))

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<int> se;
se.insert(1);
se.insert(2);
se.insert(3);
se.insert(4);
se.erase(3);
for(set<int>::iterator it = se.begin(); it != se.end(); it++)
{
	cout << *it << endl;
}
//输出
1
2
4

map

1
2
3
4
映射
包含的元素都是关键字-值, 按照关键字进行了排序
搜索, 删除, 插入的时间复杂度是o(log(n))
常用红黑树实现;

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
map<string, int> m;
m.insert(map<string,int>::value_type("()", 0));
m.insert(map<string,int>::value_type("*", 1));
m.insert(map<string,int>::value_type("-", 2));
m.insert(map<string,int>::value_type("/", 1));
m.insert(map<string,int>::value_type("+", 2));
map<string, int>::iterator ite = m.find("+");
if(ite != m.end())
{
	cout << "Found \"+\" value " << (*ite).second << endl; 
}
for(map<string, int>::iterator ite = m.begin(); ite != m.end(); ite++)
{
	cout << (*ite).first << " " << (*ite).second << endl;
}
//输出(字典序: () < * < + < - < /)
Found "+" value 2
() 0
* 1
+ 2
- 2
/ 1

multiset

1
2
3
4
可重复集合;
可以有等值的元素存在;
c++11中新增;
等值的元素, 按照插入顺序;

multimap

1
2
3
4
可重复映射
包含的元素中, 允许关键字相等
c++11中新增;
关键字等值的元素, 按照插入顺序;

无序关联容器

1
2
容器中的值, 不进行排序;
都是c++11中新增

unordered_set

1
2
3
无序集合;
等值的元素唯一;
搜索, 插入, 删除的时间复杂度为常量;

unordered_map

1
2
3
无序映射;
关键字等值的元素唯一;
搜索, 插入, 删除的时间复杂度为常量;

unordered_multiset

1
2
3
4
无序的可重复集合
可以容纳等值的元素
元素不排序
搜索,插入,删除的时间复杂度为常量

unordered_multimap

1
2
3
4
无序可重复映射
可以容纳关键字等值的元素;
不排序;
搜索, 插入, 删除的时间复杂度为常量;

容器适配器

1
为序列容器提供了不一样的接口

stack

1
LIFO栈

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop();
cout << s.top() << endl;
while(!s.empty())
{
	cout << s.top() << endl;
	s.pop();
}
//输出
2
2
1

queue

1
FIFO队列

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.pop();
q.push(4);
cout << q.front() << endl;
while(!q.empty())
{
	cout << q.front() << endl;
	q.pop();
}
//输出
2
2
3
4

priority_queue

1
队列的第一个元素总是最大的那个

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
priority_queue<int, vector<int>, greater<int> > pq;
pq.push(4);
pq.push(1);
pq.push(2);
pq.push(3);
pq.pop();
cout << pq.top() << endl;
while(!pq.empty())
{
	cout << pq.top() << endl;
	pq.pop();
}
//输出
2
2
3
4

容器的线程安全性

1
总体来说, 容器的线程安全是不靠谱的, 专家们说, 别靠容器自己来保证线程安全.

  • 对于不同的线程,可以同时用任何函数(不是成员函数哦)访问不同的容器(似乎有些废话);

  • 对于不同的线程,可以同时访问相同容器的只读成员函数;

  • 不同的线程, 可以同时修改同一容器中的不同元素, 除了vector<bool>

  • Elements of the same container can be modified concurrently with those member functions that are not specified to access these elements. More generally, the C++ standard library functions do not read objects indirectly accessible through their arguments (including other elements of a container) except when required by its specification.

  • In any case, container operations (as well as algorithms, or any other C++ standard library functions) may be parallelized internally as long as this does not change the user-visible results (e.g. std::transform may be parallelized, but not std::for_each which is specified to visit each element of a sequence in order)

    • 最终是一张大表:


    c++.png