1、理解标准容器库

STL 对于性能优化 的重要特性：
  1、对于插入和删除操作的性能开销的 大O标记 的性能保证
  2、向 序列容器 添加元素具有分摊常时性能开销
  3、具有精准地掌控容器的 动态内存分配 的能力

---

1、序列容器【元素顺序 = 插入顺序】

事项	string	vector	deque	list	forward_list
下标	√	√	√
中插	O(n)	O(n)	O(n)	O(1)	O(1)
尾插	O(1)	O(1)	O(1)	O(1)
Iterator失效	重分配	重分配	重分配	指向被删	指向被删

在迭代器不失效情况下，甚至可拼接or合并两 list 或 forward_list
可对具顺序关系的元素排序，O(${\log }_2^n$) 开销查找

---

2、关联容器【元素顺序 = 属性顺序】

有序关联容器：平衡二叉树，必须对键 or 元素 定义排序 operator<()

操作	map	multimap	set	multiset
访问	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)
插入	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)
移除	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)	O(${\log }_2^n$)

无序关联容器：散列表，只要求对键 or 元素 定义 相等关系

操作	unordered_map	unordered_multimap	unordered_set	unordered_multiset
访问	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)
插入	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)
移除	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)	avg:O(1) worst:O(n)

---

3、测试标准库容器【增删查 100000 元素 适宜】

奇特处：大O标记性能无法 反应真实情况
  1、两容器某操作均具O(1)渐进开销，但有些仍可能比其他快 n 倍
  2、unordered_map 比 map 查更快，但 差距没预想大，且 前者内存量非常大
  3、大多容器有多种插入，但某种比其他 快10%
  4、大多容器有多种遍历，但某种比其他 快很多，然而 性能开销差距比预想小

插入开销 = 分配空间【元素大小固定】 + 构造复制元素【取决于编程】
设计性能测试【链接】

2、std::vector 与 std::string

事项	vector
中插	O(n)
尾插	O(1)
索引	O(1)
排序	O(n${\log }_2^n$ )
查找	已排序 O(${\log }_2^n$ )，否则O(n)
Iterator失效	重分配

VS 中 string 可能是 vector 的一处理字符串的继承类
vector 对内存管理器的唯一调用，只是重分配【扁平结构，高效】
除非有理由必须用其他容器，否则优先用 vector

---

1、重分配

重分配：size==capacity，重分配内存，元素复制到新空间，故迭代器&索引失效
高效使用：
  1、reserve 预留足够 capacoty
  2、元素移除，也不将内存自动还给内存管理器【但存储极度有限，需注意】

clear 设容器为 0，但不一定会重分配 来减容量
shrink_to_fit 缩减容量至size，但不强制 重分配【c++11 & VS2010】

确保所有版本C++均释放 vector 内存：

std::vector<Foo> x;
...
std::vector<Foo>().swap(x)

---

2、插入与删除

vector 构造 100000	耗时	操作间比例
operator=	0.445 ms	1
insert [一次]	0.696 ms	1.56
push_back [迭代器]	2.26 ms	5.08
push_back [at]	2.05 ms	4.61
push_back [下标]	1.99 ms	4.47
push_back [迭代器 + 预分配]	0.674 ms	1.51
insert [多次 + 迭代器/at/下标]	≈2.7 ms	6.07
insert [多次 + 迭代器/at/下标 + 预分配]	≈1.45 ms	3.26

operator=：【一次创建内存】

std::vector<kvstruct> test_vector, random_vector;
...
test_vector = random_vector;

insert [一次]：

std：vector<kvstruct> test_container，random_vector;
...
test_container.insert(
	test_container.end()，
	random_vector.begin()，
	random_vector.end());

push_back：【多次重分配】

// 使用 vector 的迭代器:
std：vector<kvstruct> test_container，random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
	test_container.push_back(*it);

// 使用 std：vector:at() 成员函数:
std：vector<kvstruct> test_container，random_vector;
...
for (unsigned i = 0; i < nelts; ++i)
	test_container.push_back(random_vector.at(i));
	
// 直接使用 vector 的下标:
std：vector<kvstruct> test_container，random_vector;
...
for (unsigned i = 0; i < nelts; ++i)
	test_container.push_back(random_vector[i]);

push_back [迭代器 + 预分配]：

std：vector<kvstruct> test_container，random_vector;
...
test_container.reserve(nelts);
for (auto it=random_vector.begin(); it!= random_vector.end(); ++it)
	test_container.push_back(*it);

insert [多次 + 迭代器/at/下标]：

std：vector<kvstruct> test_container，random_vector;
...
for (auto it=random_vector.begin(); it!= random_vector.end(); ++it)
	test_container.insert(test_container.end()，*it);

vector 前端插入元素【超级弱点】	耗时	对比尾插 insert [多次 + 迭代器/at/下标]
insert	8065 ms	≈3000

---

3、遍历

操作	耗时	操作间比例
迭代器	0.236 ms	1.83
at	0.230 ms	1.78
下标	0.129 ms	1

std::vector<kvstruct> test_container;
...
unsigned sum = 0;
for (auto it=test_container.begin(); it!=test_container.end(); ++it)
	sum += it->value;


std::vector<kvstruct> test_container;
...
unsigned sum = 0;
for (unsigned i = 0; i < nelts; ++i)
	sum += test_container.at(i).value;


std::vector<kvstruct> test_container;
...
unsigned sum = 0;
for (unsigned i = 0; i < nelts; ++i)
	sum += test_container[i].value;

---

4、排序

操作	耗时 [VS2010， i7，100000]	操作间比例
sort	18.61 ms	4.94
sort 已排序	3.77 ms	1
stable_sort	16.08 ms	4.27
stable_sort 已排序	5.01 ms	1.33

std::vector<kvstruct> sorted_container, random_vector;
...
sorted_container = random_vector;
std::sort(sorted_container.begin(), sorted_container.end());

---

5、查找

操作	耗时
lower_bound	28.92 ms

std::vector<kvstruct> sorted_container, random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it) 
{
	kp = std::lower_bound(
				sorted_container.begin(),
				sorted_container.end(),
				*it);
	if (kp!= sorted_container.end() && *it < *kp)
		kp = sorted_container.end();
}

3、std::deque

事项	deque
中插	O(n)
尾插	O(1)
索引	O(1)
排序	O(n${\log }_2^n$ )
查找	已排序 O(${\log }_2^n$ )，否则O(n)
Iterator失效	重分配

deque 与 vector 类似，但操作的常量比例前者更大，故两相比较：
  1、共通操作：deque 慢 3~10倍
  2、迭代、排序、查找：deque 慢 ≈30%

deque 获取元素需 两间接引用，降低缓存局部性，且更频繁调内存管理器
queue 是容器适配器模板，deque 是其默认实现

---

2、插入与删除

deque 无 reserve，但有 push_front
注意：deque测试应为非调试模式

deque 构造 100000	耗时	操作间比例	deque : vector
operator=	5.70 ms	1.32	12.81
insert [一次]	5.28 ms	1.22	7.59
push_back [迭代器]	4.33 ms	1	1.92 [预分配：6.42]
push_back [at]	4.76 ms	1.10	2.32
push_back [下标]	5.01 ms	1.16	2.52
push_front [迭代器]	5.19 ms	1.20
push_front [下标]	5.55 ms	1.28
insert [多次 + 后端，较push_back约2倍]	≈9.5+ ms	≈2+	3.48 [预分配：6.48]
insert [多次 + 前端，较push_front约2倍]	≈10.5+ ms	≈2.5+

operator=：【一次创建内存】

std::deque<kvstruct> test_container;
std::vector<kvstruct> random_vector;
...
test_container = random_vector;

insert [一次]：

std：deque<kvstruct> test_container;
std：vector<kvstruct> random_vector;
...
test_container.insert(
	test_container.end(),
	random_vector.begin(),
	random_vector.end());

push_back：【多次重分配】

std::deque<kvstruct> test_container;
std::vector<kvstruct> random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
	test_container.push_back(*it);

for (unsigned i = 0; i < nelts; ++i)
	test_container.push_back(random_vector.at(i));

for (unsigned i = 0; i < nelts; ++i)
	test_container.push_back(random_vector[i]);

---

3、遍历

操作	耗时	操作间比例	deque : vector
迭代器	0.450 ms	1	1.91
下标	0.828 ms	1.84	6.42

---

4、排序

操作	耗时 [VS2010， i7，100000]	操作间比例	deque : vector
sort	24.82 ms	1.40	1.33
sort 已排序	? ms [<24.82]	? [<1.40]	? [<1.33]
stable_sort	17.76 ms	1	1.1
stable_sort 已排序	? ms [<17.76]	? [<1]	? [<1.1]

---

5、查找

操作	耗时	deque : vector
查找	35 ms	1.21

4、std::list

事项	list
插入	O(1)
排序	O(n${\log }_2^n$ )
查找	O(n)
Iterator失效	指向被删

缺点：
  1、太低效，但大部分操作与deque比，仍具竞争力
  2、前后向遍历 & size 昂贵，故引入forward_list，但PC上两者操作性能几乎相同

优点：【并&插优于vector】
  1、拼接 和 合并 无需复制元素，O(1)
  2、splice、sort 不会使迭代器失效
  3、插入快，O(1)
  4、不存在未使用的额外存储空间【内存碎片↓】

---

2、插入与删除

list结构简单，优化空间很小

list 构造 100000	耗时 [VS2010， i7，100000]	操作间比例	list : vector
operator=	5.10 ms	1.38	11.46
delete	2.49 ms	0.67
insert [一次]	3.69 ms	1	5.30
push_back [迭代器]	4.26 ms	1.15	1.88
push_back [at]	4.50 ms	1.22	2.20
push_back [下标]	4.63 ms	1.25	2.33
push_front [迭代器]	4.77 ms	1.29
push_front [at]	4.82 ms	1.31
push_front [下标]	4.99 ms	1.35
insert [多次 + 后端 + 迭代器 ]	4.75 ms	1.29	≈1.76
insert [多次 + 后端 + at ]	4.84 ms	1.31	≈1.79
insert [多次 + 后端 + 下标 ]	4.88 ms	1.32	≈1.81
insert [多次 + 前端 + 迭代器]	4.84 ms	1.31
insert [多次 + 前端 + at]	5.02 ms	1.36
insert [多次 + 前端 + 下标]	5.04 ms	1.37

---

3、遍历

操作	耗时	list : vector
迭代器	0.326 ms	1.38

---

4、排序

操作	耗时 [VS2010， i7，100000]	操作间比例	list : vector
std::sort	?	?	?
内置sort	23.2 ms	1	1.25

---

5、查找

操作	耗时
find	? ms

5、std::forward_list

事项	list
插入	O(1)
排序	O(n${\log }_2^n$ )
查找	O(n)
Iterator失效	指向被删

注意：因只有 insert_after，且无法获取第一个元素之前的位置，故无法前端插入
适宜场景：非常严格的小型处理器

---

2、插入与删除

forward_list 构造 100000	耗时 [VS2010， i7，100000]	操作间比例	forward_list : list
insert_after	4.24 ms	1.02	≈1
push_front	4.16 ms	1	≈1

---

3、遍历

操作	耗时	forward_list : vector
迭代器	0.343 ms	1.45

---

4、排序

操作	耗时 [VS2010， i7，100000]	操作间比例	list : vector
std::sort	?	?	?
内置sort	23.3 ms	1	1.25

---

5、查找

操作	耗时
find	? ms

6、std::map与std::multimap

事项	list
插入	O(${\log }_2^n$)
索引	O(${\log }_2^n$ )
Iterator失效	指向被删

平衡二叉树，有额外链接，无法应用bfs或dfs遍历

---

2、插入与删除

map 构造 100000	耗时 [VS2010， i7，100000]	操作间比例
insert	18.0 ms	2.1
insert end()提示	9.11 ms	1.06
insert C++11之前提示	14.4 ms	1.68
insert C++11提示	8.56 ms	1

带提示的插入 比不带提示的快

insert C++11 提示：

// C++11 之前insert前插, 之后insert后插, 故应反向遍历输入数据
ContainerT test_container;
std::vector<kvstruct> sorted_vector;
...
std::stable_sort(sorted_vector.begin(), sorted_vector.end());
auto hint = test_container.end();
for (auto it = sorted_vector.rbegin(); it != sorted_vector.rend(); ++it)
	hint = test_container.insert(hint, value_type(it->key, it->value));

---

优化 “检查并更新” 惯用法：
常用方法：

iterator it = table.find(key); 		// O(log n)
if (it != table.end()) 
{
	// 找到key的分支
	it->second = value;
}
else 
{
	// 没有找到key的分支
	it = table.insert(key, value); // O(log n)
}

优化核心：利用第一次查找结果，使插入 O(1)
1、只想有键取值，无键插入
应用场景：查前知道如何初始化元素，或更新值开销不大

std::pair<value_t, bool> result = table.insert(key, value);
if (result.second) 
{
	// k找到key的分支
}
else 
{
	// 没有找到key的分支
}

2、lower_bound 或 upper_bound 找到键或插入位置

iterator it = table.lower_bound(key);
if (it == table.end() || key < it->first) 
{
	// 找到key的分支
	table.insert(it, key, value);
}
else 
{
	// 没有找到key的分支
	it->second = value;
}

---

3、遍历

操作	耗时	map : vector
迭代器	1.34 ms	5.68

---

4、排序 [本就有序]

---

5、查找

操作	插入+排序 耗时	查找	查找间比例
vector	19.1 ms	28.92 ms	1
map	33.8ms	42.3 ms	1.46

7、std::set与std::multiset

事项	list
插入	O(${\log }_2^n$)
索引	O(${\log }_2^n$ )
Iterator失效	指向被删

set 查找返 const 元素，虽可将 排序无关成员 声明为mutable处理，但排序有关不可擅改
set 内部结构和 map 相同

8、std::unordered_map与std::unordered_multimap

事项	unordered_map
插入	avg:O(1) worst:O(n)
索引	avg:O(1) worst:O(n)
Iterator失效	再计算散列值
引用失效	指向被删

散列表，可能符合标准定义：
采用动态分配的骨干数组，其保存指向 动态分配内存的节点组成的链表 的桶的设计

reserve(n) = rehash(ceil(n/max_load_factor()));
clear必清除所有元素，并返还内存

---

2、插入与删除

unordered_map 构造 100000	耗时	操作间比例
insert	15.5 ms	1.04
insert [预分配]	14.9 ms	1

---

3、遍历

操作	耗时	unordered_map : vector
迭代器	0.34 ms	1.44

for (auto it = test_container.begin();	it != test_container.end(); ++it) 
{
	sum += it->second;
}

---

4、排序 [无法排序]

---

5、查找

操作	插入+排序 耗时	查找	查找间比例
map	33.8ms	42.3 ms	4.07
vector	19.1 ms	28.92 ms	2.78
unordered_map	15.5ms	10.4 ms	1

若存储极受限，用vector [更紧凑]；若不是，则用 unordered_map

9、总结

1、vector 总结【普适推荐】

插入：operator= —> push_back [下标 + 预分配] —> insert [一次]
遍历：下标
排序：已排用sort，未排用stable_sort
查找：lower_bound

事项	vector
中插	O(n)
尾插	O(1)
索引	O(1)
排序	O(n${\log }_2^n$ )
查找	已排序 O(${\log }_2^n$ )，否则O(n)
Iterator失效	重分配

---

2、deque 总结【比list 快点，但 vector 更优】

插入：push_back [迭代器] —> push_front [迭代器] —> insert [一次] —> operator=
遍历：迭代器
排序：已排用sort，未排用stable_sort
查找：

事项	deque
中插	O(n)
尾插	O(1)
索引	O(1)
排序	O(n${\log }_2^n$ )
查找	已排序 O(${\log }_2^n$ )，否则O(n)
Iterator失效	重分配

---

3、list 总结【效率低】

插入：insert [一次] —> push_back [迭代器] —> insert [多次 + 后端 + 迭代器 ]
—> push_front [迭代器] —> insert [多次 + 前端 + 迭代器] —> operator=
遍历：迭代器
排序：内置sort
查找：std::find

事项	list
插入	O(1)
排序	O(n${\log }_2^n$ )
查找	O(n)
Iterator失效	指向被删

---

4、forward_list 总结 【只能从前往后，并不比list更快】

出现原因：list 前/后向遍历、size昂贵
适宜场景：非常严格的小型处理器

插入：push_front —> insert_after
遍历：迭代器
排序：内置sort
查找：std::find

事项	forward_list
插入	O(1)
排序	O(n${\log }_2^n$ )
查找	O(n)
Iterator失效	指向被删

---

5、map 与 multimap 总结 【若vector能排序，则更优】

插入：提示性插入 [检查并更新优化]
遍历：迭代器
排序：本就有序
查找：

事项	list
插入	O(${\log }_2^n$)
索引	O(${\log }_2^n$ )
Iterator失效	指向被删

---

6、set与multiset 总结 【 同map实现相同 】

插入：提示性插入 [检查并更新优化]
遍历：迭代器
排序：本就有序
查找：

事项	list
插入	O(${\log }_2^n$)
索引	O(${\log }_2^n$ )
Iterator失效	指向被删

---

7、unordered_map 与 unordered_multimap 【空间够，最优推荐】

若存储极受限，用vector [更紧凑]；若不是，则用 unordered_map

插入：insert [预分配]
遍历：迭代器
排序：无法排序
查找：

事项	unordered_map
插入	avg:O(1) worst:O(n)
索引	avg:O(1) worst:O(n)
Iterator失效	再计算散列值
引用失效	指向被删

---

最后总结：

1、 STL 是第一个可复用的高效容器和算法库
2、大 O 标记性能并不能反映真实情况，有些容器比其他快许多
3、在进行插入、删除、遍历和排序操作时，vector 都是最快容器
4、lower_bound查有序 vector，可与查 map 速度相匹敌
5、deque 只比 list 稍快一点
6、forward_list 并不比 list 更快
7、unordered_map 比 map 更快，但也没快上一个数量级