STL 关联容器简单介绍
关联容器即 key-value 键值对容器，依靠 key 来存储和读取元素。
在 STL 中，有四种关联容器，各自是：
- map 键值对 key-value 存储，key 不可反复，即一个 key 仅仅能相应一个 value, 相应头文件<map>
- multimap 键值对 key-value 存储，key 能够反复，即一个 key 能够相应多个 value, 相应头文件<map>
- set 仅仅有 key, key 不可反复，相应头文件<set>
- multiset 仅仅有 key, key 能够反复。相应头文件<set>
STL 关联容器特点
- STL 关联容器的底层数据结构是红黑树。故其增删查的时间复杂度都是 O(logn)
- map 默认依照 key 的升序进行插入，非基本数据类型要求重载 < 运算符
- map 重载了 [] 运算符，使的插入和查找很方便
- map 用 [] 运算符訪问元素时，假设不存在这个key。key会自己主动插入，value为初始化值
- map 的 key 对象使用之后就不要再改动，假设必须改动，须要删除后又一次插入
- multimap 的 key-value 是一对多，没有重载 [] 运算符
map 经常使用函数
#构造：
map c: #创建空映射,不包括不论什么元素
map c(op): #以 op 为排序准则，产生一个空的map
map c1(c2): #复制 c2 中的元素到 c1 中
map c(const value_type *first, const value_type* last): #复制 [first, last) 之间元素构成新映射
map c(const value_type *first, const value_type* last,op): #以 op 为排序准则。复制[first, last)之间元素构成新映射
multimap m: #创建空映射,不包括不论什么元素
multimap m(op): #以 op 为排序准则，产生一个空的 multimap
multimap m1(m2): #复制 m2 中的元素到 m1 中
multimap m(const value_type *first, const value_type* last): #复制 [first, last)之间元素构成新映射
multimap m(const value_type *first, const value_type* last,op): #以op为排序准则，复制 [first, last)之间元素构成新映射
#增删
iterator insert(const value_type& x): #插入元素 x
iterator insert(iterator it,const value_type& x): #在迭代指针 it 处插入元素x
void insert(const value_type *first,const value_type* last): #插入[first, last)之间元素
iterator erase(iterator it): #删除迭代指针it处元素
iterator erase(iterator first,iterator last): #删除[first, last)之间元素
size_type erase(const Key& key): #删除键值等于key的元素
#遍历
iterator begin(): #返回首元素的迭代器指针
iterator end()： #返回尾元素的迭代器指针
reverse_iterator rbegin(): #返回尾元素的逆向迭代器指针
reverse_iterator rend(): #返回首元素前一个位置的迭代器指针
reference operator[](const Key& k): #仅仅用在映射map 类中。重载[]，并返回值的引用
#功能
int size() const: #返回容器元素个数
bool empty() const: #推断容器是否空。若返回true。表明容器已空
const_iterator find(const Key& key) const: #查找返回键值等于 key 的迭代器指针
int count(const Key& key) const: #返回键值等于 key 的元素的个数
const_iterator lower_bound(const Key& key): #返回键大于等于 key 的第一个迭代器指针
const_iterator upper_bound(const Key& key): #返回键大于 key 的第一个迭代器指针
pair<const_iterator,const_iterator> equal_range(const Key& key) const: #返回一对迭代器，使得[first, last)内元素等于key
set 经常使用函数
#构造
set c: #创建空集合,不包括不论什么元素
set c(op): #以 op 为排序准则。产生一个空的 set
set c1(c2): #复制 c2 中的元素到 c1 中
set c(const value_type *first, const value_type* last): #复制 [first, last) 之间元素构成新集合
set c(const value_type *first, const value_type* last,op): #以 op 为排序准则。复制 [first, last) 之间元素构成新集合
multiset m: #创建空集合,不包括不论什么元素
multiset m(op): #以 op 为排序准则，产生一个空的 set
multiset m1(m2): #复制 m2 中的元素到 m1 中
multiset m(const value_type *first, const value_type* last): #复制 [first, last) 之间元素构成新集合
multiset m(const value_type *first, const value_type* last,op): #以 op 为排序准则，复制 [first, last) 之间元素构成新集合
#增删
pair<iterator,bool> insert( x): #插入元素x
iterator insert(iterator it,x): #在迭代器it处插入元素x
void insert(const value_type *first,const value_type *last): #插入[first, last)之间元素
iterator erase(iterator it): #删除迭代器指针it处元素
iterator erase(iterator first,iterator last): #删除[first, last)之间元素
size_type erase(const Key& key): #删除元素值等于key的元素
#遍历
iterator begin(): #返回首元素的迭代器指针
iterator end()： #返回尾元素的迭代器指针
reverse_iterator rbegin(): #返回尾元素的逆向迭代器指针
reverse_iterator rend(): #返回首元素前一个位置的迭代器指针
#功能
int size() const: #返回容器元素个数
bool empty() const: #推断容器是否为空，若返回true，表明容器已空
const_iterator find(const Key& key) const: #查找返回元素值等于key的迭代器指针
int count(const Key& key) const: #返回容器中元素等于key的元素的个数
const_iterator lower_bound(const Key& key): #返回键大于等于 key 的第一个迭代器指针
const_iterator upper_bound(const Key& key): #返回键大于 key 的第一个迭代器指针
pair<const_iterator,const_iterator> equal_range(const Key& key) const: #返回一对迭代器，使得[first, last)内元素等于key
void swap(set& s): #交换集合元素
void swap(multiset& s): #交换多集合元素
map 小样例
#include <iostream>
#include <map>
using namespace std; class Cat {
public:
int age;
Cat(int age) {
this->age = age;
}
/* map 底层是红黑树，用作 key 的对象必须可排序, 需重载 < 运算符 */
bool operator <(const Cat &c) const {
return age < c.age;
}
}; int main() {
map<char, char> m;
m.insert(map<char, char>::value_type('a', 'a'));
m['b'] = 'b';
cout << "m['a'] is: " << m['a'] << ", "; // 用运算符[]訪问
map<char, char>::iterator it = m.find('b'); // 用迭代器訪问
cout << "m['b'] is: " << it->second << ", ";
cout << "m['c'] is: " << m['c'] << endl; // 用 []訪问要先推断是否存在，不存在则会被插入
m['c'] = 'c';
m['d'] = 'd';
for (map<char, char>::iterator it = m.begin(); it != m.end(); it++) {
cout << it->first << ":"; // `first` 是 key, 不可改动(const 修饰)
cout << (*it).second << ", "; // `second` 是value,能够改动
}
map<char, char>::iterator it_low, it_up;
it_low = m.lower_bound('c');
it_up = m.upper_bound('c');
cout << "\nlower_bound('c') is: " << it_low->first << endl;
cout << "upper_bound('c') is: " << it_up->first << endl;
pair<map<char, char>::iterator, map<char, char>::iterator> ret;
ret = m.equal_range('c');
cout << "equal_range('c'): " << ret.first->first << ", "<< ret.second->first << endl;
map<Cat, char> t;
Cat c(1);
t[c] = 'a';
c.age = 2; // key 对象改动后，无法再从 map 查到这个键值对
cout << "改动 key 对象后，再次查找这个 key 出现的次数: " << t.count(c) << endl;
} /* 输出：
m['a'] is: a, m['b'] is: b, m['c'] is:
a:a, b:b, c:c, d:d,
lower_bound('c') is: c
upper_bound('c') is: d
equal_range('c'): c, d
改动 key 对象后。再次查找这个 key 出现的次数: 0
*/
【地址：http://blog.csdn.net/thisinnocence/article/details/39646813】