STL 标准库提供了 4 种关联式容器，分别为 map、set、multimap、multiset

set

set的元素有序不重复，而且能根据元素的值自动进行排序。set中的键值不能直接修改，只能先删除再插入。底层采用红黑树。

set不支持随机访问，只能使用迭代器去访问。由于set放入一个元素就会调整这个元素的位置，把它放到合适的位置，所以set中只有一个insert插入操作。

set<int> s;
s.insert(5);
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(4);
cout<<"set 的 size："<<  s.size() <<endl;  // 5
cout<<"set 中的第一个元素是 ："<<  *s.begin()<<endl;  // 1
cout<<"set 中的最后一个元素是:"<<  *s.end()<<endl;   // 5
set<int>::iterator it;
for(it=s.begin(); it!=s.end(); it++)
{
    cout<< *it <<endl;
}    // 1  2  3  4  5
//    s.clear();
s.erase(++s.begin());
cout << "       after erase begin"<<endl;
for(it=s.begin(); it!=s.end(); it++)
{
    cout<< *it <<endl;
}	 // 1  3  4  5
cout<<"lower bound: "<<*s.lower_bound(5)<<endl;  // 5
cout<<"upper bound: "<<*s.upper_bound(5)<<endl;  // 4
if(s.empty())
    cout << "set is empty !" <<endl;

multiset底层也是红黑树，但允许有重复数据

map 和 unordered_map

map适合存储一个数据字典，并要求方便地根据key找value。Map节点有一个Key和Value两个元素，Key不重复，Value可以重复。map可以通过key改变value的值

底层也是红黑树，所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此它的插入删除查找的时间复杂度为O(logN)

map支持随机访问(at函数和[])，这是set没有的。

map<int, string> m;
m.insert(pair<int, string>(1, "a"));
m.insert(pair<int, string>(2, "b"));
m.insert(pair<int, string>(3, "c"));
m.insert(pair<int, string>(4, "d"));
m.insert(pair<int, string>(5, "e"));

cout << m.upper_bound(3)->second <<endl;   // 大于
cout << m.lower_bound(3)->second <<endl;   // 不小于

运行结果：

d
c

缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间

unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的，但查找速度非常的快。 缺点：哈希表的建立比较耗费时间。