目录

一、基本概念

二、内部实现 

三、常用函数 

3.1 构造函数

3.2 插入操作

3.2.1 insert 成员函数

3.2.2 使用 emplace 成员函数（C++11 及以后）

3.2.3 使用 try_emplace 成员函数（C++17 及以后）

3.3 删除操作

3.3.1 erase方法删除

3.3.2 clear 方法清空整个容器

3.3.3 std::map::erase_if （C++20 引入）

3.4 查找操作

3.5 访问元素 

3.6 容量操作

四、注意事项 

五、应用场景

结语

一、基本概念

  • 定义与特性

    • map容器是C++标准模板库（STL）中的一种关联容器，用于存储键值对数据。
    • map中的所有元素都是pair，其中第一个元素是key（键值），起到索引作用；第二个元素是value（实值），是与key相关联的数据。
    • map中的元素会根据key值自动排序，默认情况下是按照升序排序。

  • 与multimap的区别

    • map不允许容器中有重复key值的元素。
    • multimap允许容器中有重复key值的元素，即一个key可以对应多个value。

二、内部实现 

std::map 的底层实现通常基于 红黑树（Red-Black Tree）。红黑树是一种自平衡的二叉搜索树，它保证了基本的动态集合操作（如插入、删除、查找等）在最坏情况下的时间复杂度为 O(logn)。 红黑树具有以下特性：

  • 节点是红色或黑色：每个节点都有一个颜色属性，用于确保树的平衡。
  • 根节点是黑色：这有助于确保树的高度不会过高。
  • 所有叶子节点都是黑色：这里的叶子节点是指树末端的空节点（NIL节点）。
  • 如果一个节点是红色的，则它的两个子节点都是黑色的（即不存在两个连续的红色节点）。
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点：这确保了树的高度是对数级别的。

这些特性使得红黑树能够在插入和删除操作后通过重新着色和旋转来保持平衡，从而保证了高效的查找性能。

std::map 的特性包括：

  • 有序性：按键的顺序存储元素，默认是升序。
  • 唯一键：每个键在 std::map 中是唯一的。
  • 快速查找：平均和最坏情况下的查找时间复杂度为 O(log n)。
  • 自动平衡：红黑树的自动平衡特性保证了这些操作的效率。

三、常用函数 

map容器提供了丰富的成员函数来支持各种操作。 

3.1 构造函数

  • 默认构造函数：创建一个空的 std::map。 
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    // myMap is now an empty map
    return 0;
}
  • 填充范围构造函数：使用迭代器范围来初始化 std::map。
#include <iostream>
#include <map>
#include <vector>

int main() {
    std::vector<std::pair<int, std::string>> vec = {{1, "one"}, {2, "two"}, {3, "three"}};
    std::map<int, std::string> myMap(vec.begin(), vec.end());

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

填充范围构造函数代码输出：

  • 复制构造函数：使用另一个 std::map 来初始化新的 std::map。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> originalMap = {{1, "one"}, {2, "two"}};
    std::map<int, std::string> myMap(originalMap);

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}
  • 移动构造函数（C++11 及以上）：使用另一个 std::map 的资源来初始化新的 std::map，并销毁原来的 std::map。
#include <iostream>
#include <map>
#include <utility> // for std::move

int main() {
    std::map<int, std::string> originalMap = {{1, "one"}, {2, "two"}};
    std::map<int, std::string> myMap(std::move(originalMap));

    // originalMap is now in a valid but unspecified state
    // We should not use originalMap after moving from it

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}
  • 初始化列表构造函数（C++11 及以上）：使用初始化列表来直接初始化 std::map。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}
  • 指定比较函数的构造函数：使用自定义的比较函数或函数对象来初始化 std::map。 
#include <iostream>
#include <map>

bool customCompare(int a, int b) {
    return a > b; // Descending order
}

int main() {
    std::map<int, std::string, bool(*)(int, int)> myMap(customCompare);
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

指定比较函数的构造函数代码输出：

3.2 插入操作

std::map 提供了多种插入元素的方法 。

3.2.1 insert 成员函数

insert 成员函数有多种重载形式，可以插入单个元素或填充一个范围内的元素。

插入单个元素：

  • 使用键值对插入
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    // 插入一个键值对
    myMap.insert(std::pair<int, std::string>(1, "one"));

    // 或者使用 make_pair 辅助函数
    myMap.insert(std::make_pair(2, "two"));

    // 或者直接使用大括号初始化列表（C++11 及以后）
    myMap.insert({3, "three"});

    // 输出元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
  • 使用 std::map::value_type 插入：std::map::value_type 是一个别名，表示存储在 std::map 中的元素类型，即 std::pair<const Key, T>。
myMap.insert(std::map<int, std::string>::value_type(4, "four"));
  • 使用返回值检查插入是否成功：insert 返回一个 std::pair，其中第一个元素是指向插入元素或已存在元素的迭代器，第二个元素是一个布尔值，表示是否成功插入了新元素。
auto result = myMap.insert({5, "five"});
if (result.second) {
    std::cout << "Insertion successful!" << std::endl;
} else {
    std::cout << "Key already exists!" << std::endl;
}

插入一个范围内的元素：

可以使用另一个 std::map 或其他兼容的范围（如std::vector、std::list 的迭代器对）来填充 std::map。

std::map<int, std::string> anotherMap = {{6, "six"}, {7, "seven"}};
myMap.insert(anotherMap.begin(), anotherMap.end());
3.2.2 使用 emplace 成员函数（C++11 及以后）

emplace 成员函数直接在容器内构造元素，避免了不必要的复制或移动操作。它通常比 insert 更高效，特别是当要插入的元素是大型对象或具有复杂构造函数时。

myMap.emplace(8, "eight"); // 直接在容器中构造键值对
3.2.3 使用 try_emplace 成员函数（C++17 及以后）

try_emplace 是 emplace 的一个变体，它尝试在容器中直接构造元素，但如果键已存在，则不会修改该元素并返回一个指向现有元素的迭代器。它结合了 emplace 的高效性和 insert 的不覆盖现有元素的特点。

auto [it, inserted] = myMap.try_emplace(10, "ten");
if (inserted) {
    std::cout << "Insertion successful!" << std::endl;
} else {
    std::cout << "Key already exists!" << std::endl;
}

3.3 删除操作

std::map 提供了多种删除元素的方法，包括按值删除、按键删除、删除指定迭代器位置的元素等。 

3.3.1 erase方法删除

按键删除： 

erase 方法可以接受一个键作为参数，并删除与该键关联的元素。如果键不存在，则不执行任何操作。

按迭代器删除： 

erase 方法也可以接受一个迭代器或一对迭代器（表示一个范围），并删除相应位置的元素或范围内的元素。

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"},
        {4, "four"},
        {5, "five"}
    };

    // 删除键为2的元素
    myMap.erase(2);

    // 打印剩余的元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 获取指向键为3的元素的迭代器
    auto it = myMap.find(3);
    if (it != myMap.end()) {
        // 删除迭代器指向的元素
        myMap.erase(it);
    }
 
    // 删除从键为1的元素到末尾的元素（不包含键为1的元素）
    auto it_start = myMap.find(1);
    if (it_start != myMap.end()) {
        auto it_end = myMap.end();
        myMap.erase(std::next(it_start), it_end);
    }
 
    // 打印剩余的元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

上述代码输出：

3.3.2 clear 方法清空整个容器

clear 方法会删除 std::map 中的所有元素，使其变为空容器。

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 清空容器
    myMap.clear();

    // 检查容器是否为空
    if (myMap.empty()) {
        std::cout << "The map is empty." << std::endl;
    }

    return 0;
}
3.3.3 std::map::erase_if （C++20 引入）

C++20 引入了 erase_if 方法，它接受一个谓词（predicate），并删除满足谓词条件的所有元素。

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"},
        {4, "four"}
    };

    // 删除所有值长度大于3的元素
    myMap.erase_if([](const auto& pair) {
        return pair.second.length() > 3;
    });

    // 打印剩余的元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

3.4 查找操作

std::map 提供了多种查找元素的方法，包括使用 find 方法、count 方法以及通过下标运算符[]进行查找。

  • 使用 find 方法查找元素：find 方法接受一个键作为参数，并返回一个指向具有该键的元素的迭代器。如果找不到该键，则返回end()迭代器。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 查找键为2的元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}
  • 使用count 方法检查元素是否存在：count 方法接受一个键作为参数，并返回该键在容器中出现的次数。对于 std::map 来说，这个值要么是0（键不存在），要么是1（键存在且唯一，因为std::map 中的键是唯一的）。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 检查键为2的元素是否存在
    if (myMap.count(2) > 0) {
        std::cout << "Key 2 exists" << std::endl;
    } else {
        std::cout << "Key 2 does not exist" << std::endl;
    }

    return 0;
}
  • 使用下标运算符[]查找元素：下标运算符[]也可以用于查找元素，但如果键不存在，它会插入一个具有该键的新元素，并将其值初始化为默认值（对于内置类型通常是0或空指针，对于类类型则是调用默认构造函数）。因此，使用下标运算符进行查找时要小心，因为它可能会修改容器。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 使用下标运算符查找键为2的元素（安全方式）
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found using find: " << it->first << " -> " << it->second << std::endl;
    } else {
        // 如果确实要使用下标运算符并处理可能的新插入，可以这样做：
        // 但请注意，这将在键不存在时插入一个新元素
        std::string& value = myMap[2]; // 如果键2不存在，则插入一个新元素并初始化为空字符串
        // 然后可以检查value是否为默认值来判断键是否原本就存在
        // 但对于std::string来说，空字符串是一个有效的值，所以这种方法不太适用于std::string类型的值
        // 一种更好的做法是先使用find，如果不存在再插入新元素
    }

    // 不安全的示例（仅用于演示目的，不推荐在实际代码中使用）
    // 这将插入一个新元素（如果键4不存在）或返回现有元素的值
    std::string value = myMap[4]; // 如果键4不存在，则myMap现在包含一个键为4、值为空字符串的元素
    // 注意：这里value将是空字符串，因为键4原本不存在于map中

    // 由于上面的操作可能插入了新元素，这里不再打印myMap的内容
    // 以避免混淆

    return 0;
}

注意事项：

  • 上面的下标运算符使用示例中包含了不安全用法（即直接访问可能新插入的元素）
  • 在实际代码中，应首先使用find来检查元素是否存在，然后再决定是否使用下标运算符

3.5 访问元素 

std::map 提供了多种访问元素的方法，包括使用迭代器、下标运算符 []、at 方法以及 find 方法。 

  • 使用迭代器访问元素：迭代器提供了对容器中元素的顺序访问。你可以使用迭代器遍历整个 std::map，或者定位到特定的元素。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 使用迭代器访问元素
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // 也可以直接定位到某个元素（假设知道元素存在）
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Direct access: " << it->first << ": " << it->second << std::endl;
    }

    return 0;
}
  • 使用下标运算符 [] 访问元素：下标运算符 [] 可以用来通过键访问元素的值。如果键不存在，则会插入一个具有该键的新元素，并将其值初始化为默认值（对于类类型，通常是调用默认构造函数）。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"}
    };

    // 使用下标运算符访问存在的元素
    std::string value1 = myMap[1];
    std::cout << "Value for key 1: " << value1 << std::endl;

    // 使用下标运算符访问不存在的元素（会插入新元素）
    // 注意：这通常不是访问元素的好方法，因为它会修改容器
    std::string value2 = myMap[3]; // 这将插入一个键为3、值为空字符串的新元素
    std::cout << "Value for key 3 (after insertion): " << (myMap.count(3) > 0 ? myMap[3] : "not found") << std::endl;

    // 更安全的做法是先检查元素是否存在，然后再访问
    if (myMap.find(3) != myMap.end()) {
        std::cout << "Safe access to value for key 3: " << myMap[3] << std::endl;
    } else {
        std::cout << "Key 3 does not exist" << std::endl;
    }

    return 0;
}
  • 使用 at 方法访问元素：at 方法提供了一种通过键访问元素值的更安全的方式。如果键不存在，at 方法会抛出一个 std::out_of_range 异常。
#include <iostream>
#include <map>
#include <stdexcept> // for std::out_of_range

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"}
    };

    try {
        // 使用at方法访问存在的元素
        std::string value = myMap.at(1);
        std::cout << "Value for key 1 using at: " << value << std::endl;

        // 使用at方法访问不存在的元素（会抛出异常）
        std::string nonExistentValue = myMap.at(3);
    } catch (const std::out_of_range& e) {
        std::cout << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

3.6 容量操作

std::map 提供了多种容量操作，允许你检查容器的大小、以及是否为空等。 

  • size()方法：返回容器中元素的数量。
  • empty()方法：检查容器是否为空。如果容器中没有元素，则返回 true；否则返回 false。
  • max_size() 方法：返回容器可以容纳的最大元素数量。这通常是一个非常大的值，表示容器的理论限制。
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    // 打印容器元素个数
    std::cout << "Size of map: " << myMap.size() << std::endl;

    // 检查容器是否为空
    if (myMap.empty()) {
        std::cout << "Map is empty" << std::endl;
    }
    else {
        std::cout << "Map is not empty" << std::endl;
    }

    // 返回容器可以容纳的最大元素数量
    std::cout << "Maximum size of map: " << myMap.max_size() << std::endl;

    return 0;
}

上述代码输出：

四、注意事项 

map容器使用的注意事项：

  1. 键的唯一性：
    • 在std::map中，键必须是唯一的。如果尝试插入一个已存在的键，使用[]操作符会更新对应的值，而使用insert方法则不会改变已有的键值对，insert会返回一个pair，其中first成员是迭代器，指向具有相同键的元素（如果找到），或指向新插入的元素（如果未找到），second成员是一个bool值，指示插入是否成功。
  2. 自动排序：
    • std::map中的元素默认按照键的升序排序。键的类型需要支持比较操作，这通常意味着键类型需要重载<运算符，或者提供一个自定义的比较函数作为模板参数。
  3. 性能特点：
    • 由于std::map的底层实现为是红黑树，所以插入、删除和查找操作的平均时间复杂度为O(log n)，其中n是容器中的元素数量。
    • 迭代器在插入和删除操作中通常保持有效，除了指向被直接操作的元素的迭代器外。但是，插入可能导致重新平衡树结构，从而改变迭代器的顺序。
  4. 内存管理：
    • std::map中的元素是连续存储的概念不准确，实际上，每个键值对作为一个节点存储，键和值并不是连续存放的。

五、应用场景

map容器的应用场景：

  1. 键值映射：
    • 当你需要根据某个特定的键（key）快速查找、插入或删除与其关联的值（value）时，map是理想的选择。例如，在数据库索引、配置文件解析、电话簿应用中，都可以使用map来实现键值对的存储和查询。
  2. 排序与索引：
    • 由于map内部自动根据键对元素进行排序（默认为升序），它可以用来维护有序的数据集合，如成绩排名、事件时间排序等场景。
  3. 计数与频率统计：
    • 虽然std::unordered_map在某些计数场景下可能更快，但在需要按顺序输出统计结果或进行区间查询时，map更合适。例如，统计文本中单词出现的频次并按字母顺序输出。

结语

在C++编程世界中，std::map容器以其强大的键值对存储和自动排序功能，成为了处理有序数据关联关系的首选。它提供了高效的查找、插入和删除操作，同时保证了键的唯一性，使得数据的管理变得简洁而有序。无论是实现复杂的数据结构，还是处理简单的键值映射，std::map都能凭借其出色的性能和灵活的使用方式，满足开发者的需求。通过深入理解和熟练掌握std::map，开发者可以更加高效地处理数据，提升程序的性能和可维护性。在未来的编程实践中，std::map将继续发挥其重要作用，助力开发者创造更加出色的C++程序。

如需更多信息，建议查阅C++参考手册中的map：  

std::map - cppreference.com - C++参考手册

 

# c++ # 开发语言
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模

avatar 魔乐社区
cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区
cover

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

avatar 魔乐社区