c++ STL系列——（五）map

目录

引言

特点

包含头文件

基本特性

基本操作

插入元素

访问元素

移除元素

检查是否包含某个键

获取元素数量

高级特性

迭代器

自定义比较函数

实际应用

统计字符出现次数

缓存最近访问的元素

总结

---

引言

在C++中，标准模板库（STL）的 map 是一种非常有用的关联式容器。它提供了一种将键值对（key-value pair）相关联的方式，使得可以通过键（key）快速地查找、插入或删除元素。map 的设计使得它适用于许多不同的应用场景，并且在实际编程中被广泛使用。本文将深入探讨C++ STL中map的特性、用法以及实际应用。

特点

map 是 C++ STL 中的关联式容器，具有以下特点：

1. 键值对存储： map 存储的数据以键值对的形式存在，每个元素包含一个键和一个与之关联的值。这种键值对的关联方式使得可以通过键快速地查找到对应的值，实现了高效的查找操作。

2. 自动排序： map 内部通常采用红黑树（Red-Black Tree）作为底层数据结构实现，这保证了元素按照键的顺序自动排序。因此，无论何时插入新元素或者执行查找操作，map 中的元素都会保持有序状态，提供了稳定的性能。

3. 唯一键： map 中的键是唯一的，每个键只能对应一个值。这意味着相同的键不会重复存在于 map 中，确保了键值对的唯一性。

4. 高效的查找操作： 由于 map 内部使用了平衡二叉搜索树的数据结构，因此查找操作的时间复杂度为 O(log n)，其中 n 是 map 中键值对的数量。这使得可以在较大规模的数据集合中快速定位指定键的值。

5. 动态插入和删除： map 支持动态地插入和删除键值对，且插入和删除操作的时间复杂度也为 O(log n)。这使得可以根据需要灵活地更新 map 中的数据集合。

6. 迭代器支持： map 提供了迭代器接口，允许对容器中的键值对进行遍历和操作。通过迭代器，可以方便地访问 map 中的元素，并进行相应的操作，如遍历、查找等。

包含头文件

要使用map，首先需要包含相应的头文件：

#include <map>

基本特性

map是一个关联式容器，支持自动排序。它存储键值对，每个键只能出现一次，而值可以出现多次。以下是创建一个map的基本语法：

std::map<Key, Value> myMap;

这里的Key代表键的类型，Value代表值的类型。

基本操作

插入元素

向map中插入元素可以使用insert()方法：

myMap.insert(std::pair<Key, Value>(key, value));

这将把键值对(key, value)添加到map中。

访问元素

要访问map中的元素，可以使用[]运算符：

Value myValue = myMap[key];

这将返回与指定键key相关联的值。

移除元素

从map中移除元素可以使用erase()方法：

myMap.erase(key);

这将把与指定键key相关联的键值对从map中移除。

检查是否包含某个键

通过count()方法可以检查map中是否包含指定的键：

if (myMap.count(key)) {// map中包含指定的键key
}

获取元素数量

使用size()方法可以获取map中键值对的数量：

int mapSize = myMap.size();

高级特性

迭代器

map支持迭代器，可以用于遍历map中的所有键值对。以下是使用迭代器遍历map的基本语法：

std::map<Key, Value>::iterator it;
for (it = myMap.begin(); it != myMap.end(); ++it) {// 处理键值对(it->first, it->second)
}

这里的it是一个迭代器，可以用来访问map中的键值对。it->first表示迭代器指向的键，it->second表示迭代器指向的值。

自定义比较函数

在默认情况下，map根据键的自然顺序进行排序。但是，如果需要根据其他方式进行排序，可以自定义比较函数。以下是创建一个使用自定义比较函数的map的基本语法：

struct Compare {bool operator()(const Key& key1, const Key& key2) {// 自定义比较逻辑}
};
std::map<Key, Value, Compare> myMap;

这里的Compare是自定义的比较函数，可以根据自己的需求进行实现。

实际应用

统计字符出现次数

在字符串处理中，我们经常需要统计每个字符出现的次数。这可以使用map来实现：

std::string str = "hello world";
std::map<char, int> charCount;
for (char c : str) {if (c != ' ') {++charCount[c];}
}
for (auto it : charCount) {std::cout << it.first << ": " << it.second << std::endl;
}

缓存最近访问的元素

在缓存中，我们通常需要保留最近访问的元素，以便快速地访问它们。这可以使用map来实现：

const int CACHE_SIZE = 10;
std::map<std::string, std::string> cache;
void getFromCache(const std::string& key) {std::string value = cache[key];// ...
}
void setToCache(const std::string& key, const std::string& value) {if (cache.size() == CACHE_SIZE) {cache.erase(cache.begin());}cache[key] = value;
}

总结

在C++ STL中，map是一种非常有用的关联式容器，它提供了一种将键值对相关联的方式，使得可以通过键值快速地查找、插入或删除元素。通过本文的介绍，你应该对map的基本特性、操作和高级特性有了更加深入的了解。在实际编程中，合理地运用map可以帮助我们解决各种问题，提高代码的效率和可读性。