STL 笔记（二） 关联容器 map、set、multimap 和 multimap

STL 关联容器简单介绍

在 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】