C++的map / multimap容器

一、介绍

        在C++的map / multimap容器中，所有的元素均是pair类型（有关pair类型可以参考我之前写的 《C++的set / multiset容器》的3.2中有介绍到）。

        每对pair的第一个元素被称为关键字key，第二个元素被称为值value。因此，map的元素也被称为键值对。

        将元素插入map / multimap后，元素会根据关键字的排序规则自动排序。

二、数据结构

        map / multimap容器均属于关联式容器，底层使用平衡二叉树 / 红黑树实现。

三、map与multimap的区别

        map与multimap的区别在于是否可以出现重复的key。

map	不允许同一个map中出现重复key
multimap	允许同一个map中出现重复ke

        由于二者之间除此以外并无差别，因此下文例子均基于map容器的使用示例。

四、map的使用

        map在使用前，请包含头文件#include<map>。此外，为了便于观察示例结果，以下示例均使用自己编写的printMap函数打印map所有键值对信息。

//打印map所有键值对
void printMap(map<int, char> &m) {//判空if (m.empty()) {cout << "The map is empty now." << endl;return;}for (map<int, char>::iterator it = m.begin(); it != m.end(); it++) {cout << "<" << it->first << ", " << it->second << ">" << endl;}
}

4.1 map初始化

        map的初始化可以使用构造函数与=运算符实现：

声明	解释
map<T1, T2> m;	构造函数，初始化一个空map m的关键字key类型为T1，值value的类型为T2
map<T1, T2> m(map<T1, T2> m1);	拷贝构造函数，用m1初始化m
operator=(map<T1, T2> m1)	重载的=运算符， 有关重载运算符可以看我之前写的《C++重载运算符》

map<int, char> m0;//初始化一个空map，key为int类型，value为char类型
map<int, char> m1(m0);//拷贝构造函数
map<int, char> m2 = m0;//使用重载的等号运算符

4.2 map容量与大小

声明	解释
empty()	判断map是否为空
size()	返回map中键值对的数目

map<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为valuem0.insert(pair<int, char>(i, 'a' + i));
}
//cout << "m0 : " << endl; printMap(m0);cout << boolalpha << m0.empty() << endl;//false
cout << m0.size() << endl;//10

         程序的执行结果如下所示：

4.3 map交换元素

声明	解释
swap(map<T1, T2> m1)	交换当前map与m1的全部元素

map<int, char> m0;
map<int, char> m1;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));//i作为key，大写字母作为m1的valuem1.insert(pair<int, char>(i, 'A' + i));
}cout << "Before Swap : " << endl;
cout << "m0 : " << endl; printMap(m0);
cout << "m1 : " << endl; printMap(m1);m0.swap(m1);//交换
cout << "-------------------分割线--------------------" << endl;
cout << "After. Swap : " << endl;
cout << "m0 : " << endl; printMap(m0);
cout << "m1 : " << endl; printMap(m1);

         程序执行结果如下所示：

4.4 map插入元素

声明	解释
insert(pair<T1, T2>(key, value))	将键值对<key, value>插入到map

map<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
cout << "m0 : " << endl; printMap(m0);

         程序运行结果如下所示：

4.5 map删除元素

声明	解释
erase(pos)	删除迭代器pos指向的那个元素， 并返回下一个元素的迭代器
erase(begin, end)	删除迭代器pos指向的那个元素， 并返回下一个元素的迭代器
erase(key)	删除map中关键字为key的元素 (如果是multimap，则删除关键字为key的全部元素)
clear()	清除全部元素

4.5.1 erase(pos)示例

map<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
cout << "m0 : " << endl; printMap(m0);//erase(m0.begin+1)
map<int, char>::iterator begin = m0.begin();
begin++;
m0.erase(begin);
cout << "After erase(m0.begin+1) , m0 : " << endl; printMap(m0);

        程序运行结果如下所示：

4.5.2 erase(begin, end)示例

map<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
cout << "m0 : " << endl; printMap(m0);//erase(m0.begin+1, end-2)
map<int, char>::iterator begin = m0.begin();
map<int, char>::iterator end = m0.end();
begin++;
end--; end--;
m0.erase(begin, end);
cout << "After erase(m0.begin+1, end-2) , m0 : " << endl; printMap(m0);

         程序运行结果如下所示：

4.5.3 erase(key)示例

        为了便于测试删除的是关键字为key的全部元素，此示例采用multimap：

multimap<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
//插入<0, 'A'> <0, 'B'> <0, 'C'>
for (int i = 0; i < 3; i++) {m0.insert(pair<int, char>(0, 'A' + i));
}
cout << "m0 : " << endl; printMap(m0);//erase(0)
m0.erase(0);
cout << "After erase(0) , m0 : " << endl; printMap(m0);

        程序运行结果如下所示：

4.5.4 clear()示例

map<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
cout << "m0 : " << endl; printMap(m0);//clear()
m0.clear();
cout << "After clear() , m0 : " << endl; printMap(m0);

         程序运行结果如下所示：

4.6 map查找元素

声明	解释
find(key)	返回map中关键字为key的第一个元素的迭代器 如果没找到，返回end()

multimap<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
//插入<0, 'A'> <0, 'B'> <0, 'C'>
for (int i = 0; i < 3; i++) {m0.insert(pair<int, char>(0, 'A' + i));
}
cout << "m0 : " << endl; printMap(m0);//找到key为0的第一个元素的迭代器
multimap<int, char>::iterator it = m0.find(0);
cout << "it->second : " << it->second << endl;

         程序运行结果如下所示：

4.7 map统计指定元素个数

声明	解释
count(key)	统计map中关键字为key的元素个数

multimap<int, char> m0;
for (int i = 0; i < 10; i++) {//i作为key，小写字母作为m0的valuem0.insert(pair<int, char>(i, 'a' + i));
}
//插入<0, 'A'> <0, 'B'> <0, 'C'>
for (int i = 0; i < 3; i++) {m0.insert(pair<int, char>(0, 'A' + i));
}
cout << "m0 : " << endl; printMap(m0);//统计key为0的元素个数
cout << "m0.count(0) : " << m0.count(0) << endl;

        程序运行结果如下所示：

4.8 map自定义排序规则

        map和set类似，一样可以通过仿函数指定自己的排序规则。（有关set容器可以看我之前写的文章《C++的set / multiset容器》）

        下面给出一个示例便于直观理解。为了便于说明问题，以下类中的成员权限均设置为public。首先我们先自定义一个关键字类MyKey：

class MyKey {
public://优先级：id1 > id2int id1;int id2;
};

        接下来我们给出指定排序规则的仿函数：

//仿函数：自定义排序规则
class MyKeyCompare {
public:bool operator()(MyKey k1, MyKey k2) const {if (k1.id1 == k2.id1) {//如果二者id1相等，则比较id2return k1.id2 < k2.id2;}else {return k1.id1 < k2.id1;}}
};

        在定义语句的第三个泛型中指定仿函数，元素在插入后将自动按照仿函数的规则进行排序，在主函数进行测试，打印map的全部元素信息：

//打印map所有元素信息的函数
void printMp(map<MyKey, string, MyKeyCompare> &mp) {for (map<MyKey, string>::iterator it = mp.begin(); it != mp.end(); it++) {cout << "id1为" << it->first.id1 << ", ";cout << "id2为" << it->first.id2 << ", ";cout << "名为" << it->second << endl;}
}//主函数
int main() {map<MyKey, string, MyKeyCompare> mp;mp.insert(pair<MyKey, string>(MyKey(0, 1), "A"));mp.insert(pair<MyKey, string>(MyKey(2, 1), "B"));mp.insert(pair<MyKey, string>(MyKey(1, 6), "C"));mp.insert(pair<MyKey, string>(MyKey(0, 4), "D"));mp.insert(pair<MyKey, string>(MyKey(1, 1), "E"));printMp(mp);return 0;
}

        程序的执行结果如下所示：

         从上述结果中观察可以看出，各个元素已经按照先id1后id2的规则进行自动排序了。