【C++】STL各种数据结构的应用场景

通过索引 O(1) 时间复杂度获取索引值。

O(1) 时间复杂度增、删、改节点、交换任意两个节点，但不支持快速索引。

O(1) 时间复杂度获取最大值或最小值，但只支持插入新值，删除最大/最小值，不支持快速查找删除某一特定值

unordered_set: O(1) 时间复杂度判断某一关键字是否存在，也可用于去重；
unordered_map: O(1) 时间复杂度判断某一关键字是否存在，同时获取其对应的值。

注：只有哈希函数太差或者发生哈希重建才会退化为O（N）。

用于 O ( log ⁡ n ) O(log n) O(logn) 实现增、删、查、改，同时可通过迭代器 O(1) 时间复杂度获取最大最小值。举例：

#include 
#include 
#include 

using namespace std;

int main() {
	set> s;
	s.insert(make_pair(1, 2));
	s.insert(make_pair(3, 4));
	s.insert(make_pair(1, 1));
	cout << s.begin()->first << ' ' << s.begin()->second << endl;
}

set 和 map 默认升序排列，当然也可以自定义排序方式。
pair 默认先比较第一个，第一个相同再比较第二个。