当前位置：首页 > article >正文

std::map

article 2024/12/22 15:04:44

std::map是C++标准库中的一个关联容器，它基于红黑树实现，用于存储键值对。与标准数组或向量不同，std::map允许你根据键来快速检索、插入和删除元素。正如std::vector包含在< vector >头文件中，std::map包含在< map >头文件中。

std::map的特性：

键值对存储：每个元素是一个键值对，键用于索引，值存储数据
自动排序：元素根据键的顺序自动排序，通常是按照键的升序排列
唯一键：每个键在std::map中都是唯一的，不会存在重复的键；如果插入了相同的键，则新的键值对会覆盖原来的键值对
模板类：std::map是一个模板类，可以存储任何可比较类型的键和值

在红黑树中，每个节点包含一个键值对和指向左右子节点的指针。元素按照键的大小顺序排列，因此红黑树的节点是按照键的大小顺序排列的。当执行插入、删除或查找操作时，红黑树会根据节点的键进行自平衡操作，以保持树的平衡性。这些自平衡操作包括颜色翻转、左旋和右旋等，通过这些操作，红黑树可以保持平衡，同时保持较高的性能。

std::map提供了一系列成员函数来操作和管理键值对：

构造函数

map()：默认构造函数，创建一个空的std::map对象
map(InputIterator first, InputIterator last)：根据指定范围的元素构造map

map(const map& other)：复制构造函数，创建一个新的map，包含另一个map的所有元素

std::map<std::string, int> my_map;  // 创建一个map，存储字符串键和整数值的键值对

my_map.insert({ "B", 1 });  // 添加一个键值对
my_map.insert({ "D", 2 });  // 添加一个键值对
my_map.insert(std::make_pair("C", 3));  // 添加一个键值对
my_map.insert(std::make_pair("A", 4));  // 添加一个键值对
for (auto value : my_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // A: 4  B: 1  C: 3  D: 2
}

std::map<std::string, int> new_map1(my_map);  // 通过拷贝构造创建新的map对象，深拷贝
std::cout << my_map.size() << std::endl;  // 4
std::cout << new_map1.size() << std::endl;  // 4

std::map<std::string, int> new_map2(std::move(my_map));  // 通过移动构造创建新的map对象
std::cout << my_map.size() << std::endl;  // 0
std::cout << new_map2.size() << std::endl;  // 4

赋值操作

赋值运行符 =：将一个map的内容复制给另一个map

swap(std::map& other)：交换两个map的内容

std::map<std::string, int> my_map = { {"B", 1}, {"A", 2}, {"C", 3}};  // 创建一个map，并进行初始化

std::map<std::string, int> new_map = my_map;  // 创建新的map对象，并将my_map的内容复制给new_map
for (auto value : new_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // A: 2  B: 1  C: 3
}

std::map<std::string, int> other_map{{"ABC", 1}, {"DEF", 2}};  // 创建新的map对象，并进行初始化
my_map.swap(other_map);  // 交换两个map的内容
for (auto value : my_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // ABC: 1  DEF: 2
}
for (auto value : other_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // A: 2  B: 1  C: 3
}

访问元素

operator[]：通过键访问元素，如果键不存在，则插入该键并分配新的值

at(const key_type& key)：通过键访问元素，带边界检查

std::map<std::string, int> my_map = { {"B", 1}, {"A", 2}, {"C", 3}};  // 创建一个map，并进行初始化

my_map["D"] = 5;  // 添加一个键值对
my_map["E"] = 4;  // 添加一个键值对
for (auto value : my_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // A: 2  B: 1  C: 3  D: 5  E: 4
}

std::cout << my_map["B"] << std::endl;  // 1
std::cout << my_map.at("B") << std::endl;  // 1
std::cout << my_map["F"] << std::endl;  // 0；如果map中没有相应的键，则会将其插入，并将其对应的值赋为0

插入元素

insert(const value_type& value)：插入一个键值对

emplace(Args&&… args)：在map中就地构造一个新元素

std::map<std::string, int> my_map{{"B", 1}, {"A", 2}};  // 创建一个map，并进行初始化

my_map.insert({ "D", 1 });  // 添加一个键值对
my_map.emplace(std::make_pair("C", 2));  // 就地构造一个元素
for (auto value : my_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // A: 2  B: 1  C: 2  D: 1
}

删除元素

erase(const key_type& key)：删除指定键对应的元素

clear()：清空map中的所有元素

std::map<std::string, int> my_map = { {"B", 1}, {"A", 2}, {"C", 3}};  // 创建一个map，并进行初始化

my_map.erase("A");  // 删除键为"A"的元素
for (auto value : my_map) {
    std::cout << value.first << ": " << value.second << std::endl;  // B: 1  C: 3
}

my_map.clear();  // 清空map中的所有元素
std::cout << my_map.size() << std::endl;  // 0

查找元素

find(const key_type& key)：查找指定键的元素，返回指向该元素的迭代器

count(const key_type& key)：返回指定键在map中出现的次数（总是0或1）

std::map<std::string, int> my_map = { {"B", 1}, {"A", 2}, {"C", 3} };  // 创建一个map，并进行初始化

std::cout << my_map.count("A") << std::endl;  // 1；map中存在该键，结果为1
std::cout << my_map.count("D") << std::endl;  // 0；map中不存在该键，结果为0

容量

empty()：检查map是否为空
size()：返回map中元素的数量

max_size()：返回map能容纳的最大元素数量

std::map<std::string, int> my_map;  // 创建一个map，存储字符串键和整数值的键值对

my_map.insert({ "B", 1 });  // 添加一个键值对
my_map.insert({ "D", 2 });  // 添加一个键值对
my_map.insert(std::make_pair("C", 3));  // 添加一个键值对
my_map.insert(std::make_pair("A", 4));  // 添加一个键值对

bool is_empty = my_map.empty();  // 判断map是否为空，如果为空，返回1；如果不为空，返回0
std::cout << is_empty << std::endl;  // 0

std::cout << my_map.size() << std::endl;  // 4
std::cout << my_map.max_size() << std::endl;  // 230584300921369395，能容纳的最大元素数量

迭代器
- begin()：返回指向第一个元素的迭代器
- end()：返回指向尾后一个位置的迭代器
- rbegin()：返回指向最后一个元素的逆向迭代器
- rend()：返回指向首个元素前一个位置的逆向迭代器

std::map的性能受到多种因素的影响，包括但不限于以下几点：

底层数据结构：std::map基于红黑树实现，确保了在查找、插入和删除操作上有较好的平衡性能
插入和删除操作：由于std::map是有序的关联容器，插入和删除操作可能需要重新平衡底层的红黑树，因此插入和删除元素的性能可能略低于无序容器，例如std::unordered_map
查找操作：由于底层使用了红黑树，std::map的查找操作的时间复杂度为O(logn)，其中n是容器中元素的数量，这使得在大型数据集上查找效率较高
内存占用：红黑树作为底层数据结构，每个节点需要存储额外的指针和颜色信息，因此std::map相比于一些无序容器可能会消耗更多的内存
迭代器稳定性：std::map的迭代器在插入和删除操作后仍然有效，这意味着不会因为插入或删除元素而使现有的迭代器失效

std::map在大多数情况下提供了较好的性能和稳定性，特别适用于需要有序存储和高效查找的场景。然而在某些特定情况下，例如需要快速的插入和删除操作，并且不需要元素的顺序关系时，可能会有更合适的选择。

查看全文

http://www.kler.cn/a/331472.html