C++STL相关

本篇主要总结学习STL时遇到的的一些知识点，可能会比较零散，会慢慢整理。

Set

set作为一个容器用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序，set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值。

set不允许两个元素有相同的键值。C++的标准库中的集合支持高效的插入、删除和查询操作，这三个操作的时间复杂度都是 O(lgn)，其中n是当前集合中元素的个数。如果用数组，虽然插入的时间复杂度是 O(1)，但是删除合查询都是 O(n)，此时效率太低。在C++中我们常用的集合是set。std::set 是基于hash表的，因此并不是顺序存储。

常用方法

set<string>s;
s.insert("SZ");
s.erase("SZ");
s.count("SZ")//返回是否存在
s.find("SZ")//返回指向该元素的迭代器
for (set<string>::iterator it = s.begin(); it != s.end(); ++it) 
        cout << (*it) << endl;//遍历

lower_bound与upper_bound方法

lower_bound

假如集合为C，我们查找的键值为key，则C.lower_bound(key)会查找第一个键值不小于key的元素的迭代器。

这里注意两点，第一是不小于，第二是返回值类型为迭代器。

比如容器（set中元素自动排序，红黑树特性）中元素有{1,3,5,8,11}，key为6，则在此容器上使用lower_bound查找6的结果是8这个元素对应的迭代器，因为它是第一个不小于6的元素。

upper_bound

假如集合为C，我们查找的键值为key，则C.upper_bound(key)会查找第一个比key大的元素的迭代器。

可以出来两种方法结合可以很好的获取上下界。

unordered_set

基于hash表的，因此并不是顺序存储。

unordered_set和set：

unordered_set基于哈希表，是无序的。
set实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。

map和unordered_map

映射是指两个集合之间的元素的相互对应关系。通俗地说，就是一个元素对应另外一个元素。比如一个姓名的集合 {“Tom”, “Jone”, “Marry”}，班级集合{1, 2}。姓名与班级之间可以有如下的映射关系： class(“Tom”) = 1 , class(“Jone”) = 2 , class(“Marry”) = 1
我们称其中的姓名集合为 关键字集合(key) , 班级集合为值集合(value) 。 在 C++ 中我们常用的映射是 map。

map的特点是增加和删除节点对迭代器的影响很小。对于迭代器来说，可以修改实值，而不能修改key。

std::unordered_map 就是以key来查找value而设计,不会根据key排序。其实现使用了哈希表

对比：

unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历。

unordered_map可类比于Python中的字典。其实现使用了哈希表，可以以O(1)的时间复杂度访问到对应元素，但缺点是有较高的额外空间复杂度。与之对应，STL中的map对应的数据结构是红黑树，红黑树内的数据时有序的，在红黑树上查找的时间复杂度是O(logN)，相对于unordered_map的查询速度有所下降，但额外空间开销减小。

结论：如果需要内部元素自动排序，使用map，不需要排序使用unordered_map