如何将C++ STL中的mapmultimap容器改写为支持长尾词查询的数据结构？

本文共计1551个文字，预计阅读时间需要7分钟。

1. Map基本概念

1.1 简介

Map中所有元素都是pair，其中第一个元素为key（键值），起到索引作用；第二个元素为value（值），代表实际数据。所有元素会根据key的值自动排序。

1.2 本质Map/Multimap属性

1、map基本概念

1.1、简介

• map中所有元素都是pair
• pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
• 所有元素都会根据元素的键值自动排序

1.2、本质

• map/multimap属于关联式容器，底层结构是用二叉树实现。

1.3、优点

• 可以根据key值快速找到value值

1.4、map和multimap区别

• map不允许容器中有重复key值元素
• multimap允许容器中有重复key值元素

2、map构造和赋值

2.1、功能描述

• 对map容器进行构造和赋值操作

2.2、函数原型

构造：

• map<T1, T2> mp; //map默认构造函数:
• map(const map &mp); //拷贝构造函数

赋值：

• map& operator=(const map &mp); //重载等号操作符

2.3、示例

//map的构造和赋值 void printMap(map<int,string> m) { map<int, string>::iterator it; it = m.begin(); for (int i = 0; i < m.size();i++) { cout<<"key = "<<it->first<<" value = "<<it->second<<endl; it++; } cout << endl; } void test01() { //1、默认构造 map<int, string> mp; mp.insert(make_pair(1,"zhangsan")); mp.insert(make_pair(2,"lisi")); mp.insert(make_pair(3,"wangwu")); mp.insert(make_pair(4,"laoliu")); mp.insert(make_pair(5,"xiaoqi")); printMap(mp); //2、拷贝构造 map<int, string> mp2(mp); printMap(mp2); //3、赋值 map<int, string> mp3; mp3 = mp2; printMap(mp3); } int main() { test01(); system("pause"); return 0; }

注意事项：map中所有元素都是成对出现，插入数据时需要使用对组pair

3、map的大小和交换

3.1、功能描述

• 统计map容器大小以及交换map容器

3.2、函数原型

• size(); //返回容器中元素的数目
• empty(); //判断容器是否为空
• swap(st); //交换两个集合容器

3.3、示例

//map的大小和互换 void printMap(map<int, string> m) { map<int, string>::iterator it; it = m.begin(); for (int i = 0; i < m.size(); i++) { cout << "key = " << it->first << " value = " << it->second << endl; it++; } cout << endl; } void test01() { map<int, string> mp; mp.insert(make_pair(1, "zhangsan")); mp.insert(make_pair(2, "lisi")); mp.insert(make_pair(3, "wangwu")); mp.insert(make_pair(4, "laoliu")); map<int, string> mp1; mp1.insert(make_pair(4, "哈哈哈")); mp1.insert(make_pair(6, "啦啦啦")); mp1.insert(make_pair(8, "嘿嘿嘿")); //1、判断是否为空 if (mp.empty()) { cout << "map容器为空" << endl; } else { cout << "map容器不为空" << endl; //2、访问大小 cout << "map容器的大小为：" << mp.size() << endl; } //3、交换 cout << "交换前：" << endl; printMap(mp); printMap(mp1); mp.swap(mp1); cout << "交换后：" << endl; printMap(mp); printMap(mp1); } int main() { test01(); system("pause"); return 0; }

4、map插入和删除

4.1、功能描述

• map容器进行插入数据和删除数据

4.2、函数原型

• insert(elem); //在容器中插入元素。
• clear(); //清除所有元素
• erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
• erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
• erase(key); //删除容器中值为key的元素。

4.3、示例

void printMap(map<int,char> m) { for (map<int, char>::iterator it = m.begin(); it != m.end();it++) { cout << "key=" << it->first << " value= " << it->second << endl; } cout << endl; } void test01() { int key[] = { 1,2,3,4,5 }; char val[] = { 'a','b','c','d','e' }; map<int, char> m; for (int i = 0; i < sizeof(key) / sizeof(key[0]);i++) { //1、插入 m.insert(make_pair(key[i], val[i]));//1、第一种插入 } printMap(m); m.insert(map<int,char>::value_type(6,'f'));//第二种插入 m.insert(pair<int, char>(7, 'g'));//第三种插入 m[8] = 'h';//第四种插入(不推荐使用) printMap(m); cout << m[3] << endl;//多数用于通过键，访问值 //2、删除 m.erase(m.begin()); //指定位置 m.erase(7);//通过键删除 printMap(m); m.erase(m.begin(),m.end());//通过区间删除（此区间为删除所有） printMap(m); //3、清空 m.clear(); printMap(m); } int main() { test01(); }

5、map查找和统计

5.1、功能描述

• 对map容器进行查找数据以及统计数据

5.2、函数原型

• find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回map.end();
• count(key); //统计key的元素个数

5.3、示例

//map的查找和统计 void printMap(map<int, int> m) { for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) { cout << "key=" << it->first << " value= " << it->second << endl; } cout << endl; } void test01() { map<int,int> m; m.insert(make_pair(1, 10)); m.insert(make_pair(2, 20)); m.insert(make_pair(3, 30)); m.insert(make_pair(4, 40)); printMap(m); //1、查找 map<int, int>::iterator it = m.find(4); if (it!= m.end()) { cout << "找到了" << endl; cout << "key = " << it->first << " value = " << it->second << endl; } else { cout << "未找到" << endl; } //2、统计 int ret = m.count(3); cout << "key = 3 出现：" << ret <<"次" << endl; } int main() { test01(); }

6、map容器排序

6.1、学习目标

• map容器默认排序规则为 按照key值进行 从小到大排序，掌握如何改变排序规则

6.2、主要技术点

• 利用仿函数，可以改变排序规则

6.3、示例

//map的排序 class myCompare { public: bool operator()(int v1, int v2)const { return v1 > v2; } }; void test01() { //1、默认升序 map<int, int> m; m.insert(make_pair(1, 10)); m.insert(make_pair(3, 30)); m.insert(make_pair(2, 20)); m.insert(make_pair(4, 40)); for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) { cout << "key=" << it->first << " value= " << it->second << endl; } cout << endl; //2、重写（），改变排序规则 map<int, int,myCompare> m1; m1.insert(make_pair(1, 10)); m1.insert(make_pair(2, 20)); m1.insert(make_pair(4, 40)); m1.insert(make_pair(3, 30)); for (map<int, int, myCompare>::iterator it = m1.begin(); it != m1.end(); it++) { cout << "key=" << it->first << " value= " << it->second << endl; } cout << endl; } int main() { test01(); }