std::map
霍伟彦
概念
std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。
map映照容器运用了哈希表地址映射的思想，也就是key-value的思想，每一个key对应着一个值，每个key是唯一的，底层采用红黑树的数据结构实现。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
map会根据key自动排序，建立Key － value（键值对）的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。可以 快速插入Key - Value 记录、 快速删除记录。根据Key 修改value记录。 遍历所有记录。
std::map 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。
使用
这里介绍std::map的基本使用。
头文件
#include <vector>
成员函数
(构造函数) 构造 map
(析构函数) 析构 map
operator= 赋值给容器
get_allocator 返回相关的分配器
元素访问
at(C++11) 访问指定的元素，同时进行越界检查
operator[] 访问或插入指定的元素
迭代器
begin()
cbegin() 返回指向容器第一个元素的迭代器
end()
cend() 返回指向容器尾端的迭代器
rbegin()
crbegin() 返回指向容器最后元素的逆向迭代器
rend()
crend() 返回指向前端的逆向迭代器
容量
empty(); //检查容器是否为空，若为空返回true，否则返回false
size(); //返回容纳的元素数
max_size(); //返回可容纳的最大元素数
修改器
clear() //清空容器
insert() //插入元素
erase() //擦除元素
swap() //交换内容
emplace() //原位构造元素
查找
find(key) //寻找带有特定键的元素,函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。
count(key) //返回匹配特定键的元素数量,因为此容器不允许重复故为 1 或 0。
equal_range() //返回匹配特定键的元素范围
lower_bound() //返回指向首个不小于给定键的元素的迭代器
upper_bound() //返回指向首个大于给定键的元素的迭代器
观察器
key_comp() //返回用于比较键的函数
value_comp() //返回用于在value_type类型的对象中比较键的函数。
基本操作
插入元素
std::map<int, std::string> mp;
mp.insert(std::pair<int,std::string>(1,"aaaaa")); //pair方式插入
mp.insert(std::make_pair<int,std::string>(2,"bbbbb")); //make_pair方式插入
mp.insert(std::map<int, std::string>::value_type(3,"ccccc")); //value_type方式插入
mp[4] = "ddddd"; //[]方式插入
前三种方法当出现重复键时，编译器会报错，而第四种方法，当键重复时，会覆盖掉之前的键值对。
动态插入时：
insert方式插入，如果key不存在，则插入记录，如果存在则什么都不做。
下标的方式插入，如果原本key不存在则会先创建对应的记录，然后再进行赋值，存在则覆盖之前的Value值。
可通过find(key)判断是否已存在该key的键值对；
查找元素
#include <iostream>
#include <string>
#include <map>
int main()
{
int key1 = 1,key3 =3;
std::map<int, std::string> mp;
//插入元素
mp[key1] = "key1_value";
//查找元素
std::map<int, std::string>::iterator it = mp.find(key1);//或auto it = mp.find(key1);
if(it == mp.end())
{
std::cout << "key1 is not find." << std::endl;
}
else
{
std::cout << "key1 valud is " << it->second << std::endl;
}
it = mp.find(key3);
if(it == mp.end())
{
std::cout << "key3 is not find." << std::endl;
}
else
{
std::cout << "key3 valud is " << it->second << std::endl;
}
return 0;
}
移除元素
//从map中删除元素：
iterator erase(iterator it); //通过一个条目对象删除（操作迭代器）
iterator erase(iterator first，iterator last); //删除一个范围（操作迭代器）
size_type erase(const Key&key); //通过关键字删除
示例
示例1：
#include <iostream>
#include <string>
#include <map>
using std::string;
int main()
{
//1.定义
std::map<int, string> m_map; //key表示学号，value表示姓名
//或使用如下方式
typedef std::map<int, string> MY_MAP;
MY_MAP m_map2;
//2.插入数据-方式1-operator[]
int zhangba_key = 8;
m_map[zhangba_key] = "张八";
//插入数据-方式2-insert
m_map.insert(std::map<int, string>::value_type(3,"三三"));
//插入数据-方式3-insert
m_map.insert(std::pair<int, string>(2,"小二"));
//插入数据-方式4-insert
m_map.insert(std::make_pair<int, string>(4,"小四"));
//迭代器遍历打印当前容器信息
for(std::map<int, string>::iterator it = m_map.begin();it != m_map.end();it++)
{
std::cout << it->first << ":" << it->second <<", ";
}
//first表示的是key，second存的是value
std::cout << std::endl << std::endl;
//3.查找数据和修改数据-方式1-operator[]
string value = m_map[zhangba_key]; //zhangba_key = 8 = key
std::cout << "zhangba_key" << zhangba_key << ":" << value << std::endl;
m_map[zhangba_key] = "张小八";
//查找数据和修改数据-方式1-find(key)
auto search = m_map.find(zhangba_key);//auto这里等于std::map<int, string>::iterator
if (search != m_map.end()) {
std::cout << "Found " << search->first << " " << search->second << '\n';
} else {
std::cout << "Not found\n";
}
search->second = "张老八";
std::cout << m_map[zhangba_key] << std::endl << std::endl;
//注意:
//A.键本身是不能被修改的，除非删除。
//B.不管键存不存在，比如my_Map[1] = i;，都会执行赋值操作
//C.插入新数据时，可通过find函数判断是否存在该key
//4.删除数据-方式1-通过key删除
m_map.erase(zhangba_key);
//4.删除数据-方式2-通过迭代器删除
MY_MAP::iterator my_Itr;
my_Itr = m_map.find(2);
std::cout << "my_Itr->first:" << my_Itr->first << "my_Itr->second:" << my_Itr->second << std::endl << std::endl;
m_map.erase(my_Itr);
//5.遍历数据
for(my_Itr=m_map.begin(); my_Itr!=m_map.end(); ++my_Itr)
{
std::cout << my_Itr->first << ":" << my_Itr->second <<",";
}
std::cout << std::endl << std::endl;
//6.其他方法
int map_size = m_map.size(); //返回元素数目
bool map_empty = m_map.empty(); //判断是否为空
std::cout << "map_size:" << map_size << "map_empty:" << map_empty <<std::endl;
m_map.clear(); //清空所有元素
map_size = m_map.size();
map_empty = m_map.empty();
std::cout << "map_size:" << map_size << "map_empty:" << map_empty <<std::endl;
return 0;
}
//输出如下:
2:小二, 3:三三, 4:小四, 8:张八,
zhangba_key8:张八
Found 8 张小八
张老八
my_Itr->first:2my_Itr->second:小二
3:三三,4:小四,
map_size:2map_empty:0
map_size:0map_empty:1
示例2-map嵌套用法：
#include <iostream>
#include <string>
#include <map>
using std::string;
using std::map;
int main()
{
std::map<int,std::map<int,int> >multiMap; //对于这样的map嵌套定义，
std::map<int, int> temp; //定义一个map<int, string>变量，对其定义后在插入multiMap
temp[9] = 9;
temp[10] = 10;
multiMap[10] = temp;
multiMap[10][11]=11;
multiMap[5][30]=30;
map<int,map<int,int> >::iterator multitr; // 以下是如何遍历本multiMap
map<int,int>::iterator intertr;
for(multitr=multiMap.begin();multitr!=multiMap.end();multitr++)
{
for(intertr= multitr ->second.begin(); intertr != multitr ->second.end(); intertr ++)
std::cout<< multitr ->first<<" "<<intertr->first<<" ("<<intertr -> second <<")"<<std::endl;
}
return 0;
}
其他
map与multimap差别在于multiple允许一个键对应多个值。
map和其他容器嵌套使用
std::map<int, std::vector<ClassA> > m_map;
应用场景
应用场景1：
client/server，server处理client相关的登录信息；
1.定义 std::map<int,CclientDeal*> m_clientDealMap;
2.查找和添加(建立连接时)
auto it = m_clientDealMap.find(fd); //fd为int型入参
if(it != m_clientDealMap.end()) //如果查找到元素直接返回
{
return false;
}
m_clientDealMap[fd] = pClient; //pClient为COBCPDeal*入参
3.查找和移除(断开连接时)
auto it = m_clientDealMap.find(fd); //fd为int型入参
if(it != m_clientDealMap.end()) //如果查找到元素直接返回
{
return false;
}
m_clientDealMap.erase(it);//查找操作同上
应用场景2：
用户管理相关。
1.定义typedef std::map<std::string, CUser*> UserMap;
UserMap m_userMap; ///所有的用户列表
2.用迭代器遍历访问元素
for(UserMap::iterator it = m_userMap.begin();it != m_userMap.end();){
if(it->first!="admin"){
delete ((CUser*)(it->second));
it = m_userMap.erase(it);
}else{
++it;
}
}
3.反相迭代器使用如下
for(UserMap::reverse_iterator it = m_userMap.rbegin();it != m_userMap.rend();){}
注意：数据的遍历有三种方法：①应用前项迭代器；②应用反向迭代器；③用数组方式： for(int nindex = 1; nindex <= nSize; nindex++) {}；数组方式依赖键是数值。
注意：这里使用it访问，并非*it。first表示的是key，second存的是value
参考资料：
https://zh.cppreference.com/w/cpp/container/map
https://blog.csdn.net/wujunokay/article/details/12163549
类似资料：