在C++中,map、multimap和unordered_map是三种不同的容器,用于存储键值对。它们各自有不同的特点和适用场景。
std::map:
基于红黑树实现的有序关联容器,以键的顺序进行存储和访问。
每个键只能对应一个值。
插入和查找操作的平均时间复杂度为O(logN),其中N是元素数量。
适用于需要有序存储和根据键进行快速查找的场景。
std::multimap:
基于红黑树实现的有序关联容器,以键的顺序进行存储和访问。
允许一个键对应多个值,即允许重复键。
插入和查找操作的平均时间复杂度为O(logN),其中N是元素数量。
适用于需要有序存储、允许重复键和根据键进行快速查找的场景。
std::unordered_map:
基于哈希表实现的无序关联容器,元素存储顺序不固定。
每个键只能对应一个值。
插入和查找操作的平均时间复杂度为O(1),最坏情况下为O(N),其中N是元素数量。
适用于需要快速插入、查找和不需要元素有序存储的场景。
通用操作:
1、插入元素:
#include <map> //map 和 multimap容器的头文件
#include<unordered_map> //unordered_map容器的头文件// 容器的类型可以改为:std::multimap std::unordered_map
std::map<KeyType, ValueType> myMap;
myMap.insert(std::make_pair(key, value)); // 插入键值对
myMap[key] = value; // 使用下标操作符插入键值对2、访问和修改元素:
ValueType value = myMap[key]; // 使用键访问对应的值
myMap[key] = newValue; // 修改指定键的值3、查找元素:
auto iter = myMap.find(key); // 使用find函数根据键查找元素
if (iter != myMap.end()) {// 键存在,可以访问对应的值ValueType value = iter->second;
}mulitmap容器中存在一个键值对应多个值的问题,因此查找元素略有不同:
auto range = myMultimap.equal_range(key); // 查找与键匹配的元素范围
for (auto iter = range.first; iter != range.second; ++iter) {// 对范围内的元素进行操作
}4、删除元素:
myMap.erase(key); // 根据键删除对应的元素5、遍历容器:
for (const auto& pair : myMap) {KeyType key = pair.first;ValueType value = pair.second;// 对每个键值对进行操作
}6、获取容器大小
std::size_t size = myMap.size(); // 获取`std::unordered_map`中键值对的数量