STL 笔记（二） 关联容器 map、set、multimap 和 multimap常用函数

转载：http://blog.csdn.net/thisinnocence/article/details/39646813

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 常用函数

[python] view plaincopy

1. #构造：  
2. map c:                                                           #创建空映射,不包含任何元素  
3. map c(op):                                                       #以 op 为排序准则，产生一个空的map  
4. map c1(c2):                                                      #复制 c2 中的元素到 c1 中  
5. map c(const value_type *first, const value_type* last):          #复制 [first, last) 之间元素构成新映射  
6. map c(const value_type *first, const value_type* last,op):       #以 op 为排序准则，复制[first, last)之间元素构成新映射  
7. multimap m:                                                      #创建空映射,不包含任何元素    
8. multimap m(op):                                                  #以 op 为排序准则，产生一个空的 multimap  
9. multimap m1(m2):                                                 #复制 m2 中的元素到 m1 中  
10. multimap m(const value_type *first, const value_type* last):     #复制 [first, last)之间元素构成新映射  
11. multimap m(const value_type *first, const value_type* last,op):  #以op为排序准则，复制 [first, last)之间元素构成新映射  
12. #增删  
13. iterator insert(const value_type& x):                            #插入元素 x  
14. iterator insert(iterator it,const value_type& x):                #在迭代指针 it 处插入元素x  
15. void insert(const value_type *first,const value_type* last):     #插入[first, last)之间元素  
16. iterator erase(iterator it):                                     #删除迭代指针it处元素  
17. iterator erase(iterator first,iterator last):                    #删除[first, last)之间元素  
18. size_type erase(const Key& key):                                 #删除键值等于key的元素  
19. #遍历  
20. iterator begin():                                                #返回首元素的迭代器指针  
21. iterator end()：                                                 #返回尾元素的迭代器指针  
22. reverse_iterator rbegin():                                       #返回尾元素的逆向迭代器指针  
23. reverse_iterator rend():                                         #返回首元素前一个位置的迭代器指针  
24. reference operator[](const Key& k):                              #只用在映射map 类中，重载[]，并返回值的引用  
25. #功能  
26. int size() const:                                                #返回容器元素个数  
27. bool empty() const:                                              #判断容器是否空，若返回true，表明容器已空  
28. const_iterator find(const Key& key) const:                       #查找返回键值等于 key 的迭代器指针  
29. int count(const Key& key) const:                                 #返回键值等于 key 的元素的个数  
30. const_iterator lower_bound(const Key& key):                      #返回键大于等于 key 的第一个迭代器指针  
31. const_iterator upper_bound(const Key& key):                      #返回键大于 key 的第一个迭代器指针  
32. pair<const_iterator,const_iterator> equal_range(const Key& key) const: #返回一对迭代器，使得[first, last)内元素等于key  

set 常用函数

[python] view plaincopy

1. #构造  
2. set c:                                                          #创建空集合,不包含任何元素  
3. set c(op):                                                      #以 op 为排序准则，产生一个空的 set  
4. set c1(c2):                                                     #复制 c2 中的元素到 c1 中  
5. set c(const value_type *first, const value_type* last):         #复制 [first, last) 之间元素构成新集合  
6. set c(const value_type *first, const value_type* last,op):      #以 op 为排序准则，复制 [first, last) 之间元素构成新集合  
7. multiset m:                                                     #创建空集合,不包含任何元素  
8. multiset m(op):                                                 #以 op 为排序准则，产生一个空的 set  
9. multiset m1(m2):                                                #复制 m2 中的元素到 m1 中  
10. multiset m(const value_type *first, const value_type* last):    #复制 [first, last) 之间元素构成新集合  
11. multiset m(const value_type *first, const value_type* last,op): #以 op 为排序准则，复制 [first, last) 之间元素构成新集合  
12. #增删  
13. pair<iterator,bool> insert( x):                                 #插入元素x  
14. iterator insert(iterator it,x):                                 #在迭代器it处插入元素x  
15. void insert(const value_type *first,const value_type *last):    #插入[first, last)之间元素  
16. iterator erase(iterator it):                                    #删除迭代器指针it处元素  
17. iterator erase(iterator first,iterator last):                   #删除[first, last)之间元素  
18. size_type erase(const Key& key):                                #删除元素值等于key的元素  
19. #遍历  
20. iterator begin():                                               #返回首元素的迭代器指针  
21. iterator end()：                                                #返回尾元素的迭代器指针  
22. reverse_iterator rbegin():                                      #返回尾元素的逆向迭代器指针  
23. reverse_iterator rend():                                        #返回首元素前一个位置的迭代器指针  
24. #功能  
25. int size() const:                                               #返回容器元素个数  
26. bool empty() const:                                             #判断容器是否为空，若返回true，表明容器已空  
27. const_iterator find(const Key& key) const:                      #查找返回元素值等于key的迭代器指针  
28. int count(const Key& key) const:                                #返回容器中元素等于key的元素的个数  
29. const_iterator lower_bound(const Key& key):                     #返回键大于等于 key 的第一个迭代器指针  
30. const_iterator upper_bound(const Key& key):                     #返回键大于 key 的第一个迭代器指针  
31. pair<const_iterator,const_iterator> equal_range(const Key& key) const: #返回一对迭代器，使得[first, last)内元素等于key  
32. void swap(set& s):                                              #交换集合元素  
33. void swap(multiset& s):                                         #交换多集合元素    

map 小例子

[cpp] view plaincopy

1. #include <iostream>  
2. #include <map>  
3. using namespace std;  
4.   
5. class Cat {  
6. public:  
7.     int age;  
8.     Cat(int age) {  
9.         this->age = age;  
10.     }  
11.     /* map 底层是红黑树，用作 key 的对象必须可排序, 需重载 < 运算符 */  
12.     bool operator <(const Cat &c) const {  
13.         return age < c.age;  
14.     }  
15. };  
16.   
17. int main() {  
18.     map<char, char> m;  
19.     m.insert(map<char, char>::value_type('a', 'a'));  
20.     m['b'] = 'b';  
21.     cout << "m['a'] is: " << m['a'] << ", ";     // 用运算符[]访问  
22.     map<char, char>::iterator it = m.find('b');  // 用迭代器访问  
23.     cout << "m['b'] is: " << it->second << ", ";  
24.     cout << "m['c'] is: " << m['c'] << endl;     // 用 []访问要先判断是否存在，不存在则会被插入  
25.     m['c'] = 'c';  
26.     m['d'] = 'd';  
27.     for (map<char, char>::iterator it = m.begin(); it != m.end(); it++) {  
28.         cout << it->first << ":";      // `first`  是 key, 不可修改(const 修饰)  
29.         cout << (*it).second << ", ";  // `second` 是value,可以修改  
30.     }  
31.     map<char, char>::iterator it_low, it_up;  
32.     it_low = m.lower_bound('c');  
33.     it_up = m.upper_bound('c');  
34.     cout << "\nlower_bound('c') is: " << it_low->first << endl;  
35.     cout << "upper_bound('c') is: " << it_up->first << endl;  
36.     pair<map<char, char>::iterator, map<char, char>::iterator> ret;  
37.     ret = m.equal_range('c');  
38.     cout << "equal_range('c'): " << ret.first->first << ", "<< ret.second->first << endl;  
39.     map<Cat, char> t;  
40.     Cat c(1);  
41.     t[c] = 'a';  
42.     c.age = 2;  // key 对象修改后，无法再从 map 查到这个键值对  
43.     cout << "修改 key 对象后，再次查找这个 key 出现的次数: " << t.count(c) << endl;  
44. }  
45.   
46. /* 输出： 
47.  m['a'] is: a, m['b'] is: b, m['c'] is: 
48.  a:a, b:b, c:c, d:d, 
49.  lower_bound('c') is: c 
50.  upper_bound('c') is: d 
51.  equal_range('c'): c, d 
52.  修改 key 对象后，再次查找这个 key 出现的次数: 0 
53.  */  

【地址：http://blog.csdn.net/thisinnocence/article/details/39646813】