目录

  1. 概述
  2. 基本特性
  3. 基本用法
  1. <unordered_map> 的对比
  2. 注意事项
  3. 实用示例:学生成绩管理
  4. 小练习
  1. 参考资料
  2. 出站链接

概述

<map> 是 C++ STL 中的有序关联容器,用于存储键值对(key-value pairs)。键是唯一的,元素按键的升序自动排序。它基于平衡二叉树实现,提供 O(log n) 的插入、删除和查找操作。

包含头文件

#include <map>
#include <iostream>

定义格式

std::map<键类型, 值类型, 比较器> 变量名;
  • 键类型:键的数据类型(如 intstd::string)。
  • 值类型:值的数据类型(如 intdouble)。
  • 比较器:可选,默认是 std::less<Key>(升序),可改为 std::greater<Key>(降序)。

基本特性

  • 键唯一性:每个键只能对应一个值。
  • 自动排序:键按升序存储(可自定义比较器)。
  • 高效操作:插入、删除、查找的时间复杂度为 O(log n)。
  • 动态大小:支持运行时调整。

基本用法

声明和初始化

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;             // 空 map
    std::map<int, std::string> m2 = {{1, "A"}, {2, "B"}, {3, "C"}}; // 初始化列表(C++11)

    std::cout << "m2: ";
    for (const auto& pair : m2) {
        std::cout << "{" << pair.first << ", " << pair.second << "} ";
    }
    std::cout << std::endl; // 输出:{1, A} {2, B} {3, C}
    return 0;
}

插入元素

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    m.insert({1, "Alice"});          // 插入键值对
    m.insert(std::make_pair(2, "Bob"));
    m[3] = "Charlie";                // 使用 [] 插入或覆盖

    std::cout << "m: ";
    for (const auto& pair : m) {
        std::cout << "{" << pair.first << ", " << pair.second << "} ";
    }
    std::cout << std::endl; // 输出:{1, Alice} {2, Bob} {3, Charlie}
    return 0;
}

删除元素

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
    m.erase(2); // 删除键为 2 的元素

    std::cout << "After erase: ";
    for (const auto& pair : m) {
        std::cout << "{" << pair.first << ", " << pair.second << "} ";
    }
    std::cout << std::endl; // 输出:{1, A} {3, C}
    return 0;
}

查找元素

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
    auto it = m.find(2); // 查找键为 2 的元素
    if (it != m.end()) {
        std::cout << "Found: {" << it->first << ", " << it->second << "}" << std::endl; // 输出:Found: {2, B}
    }

    if (m.count(1)) {
        std::cout << "Key 1 exists" << std::endl; // 输出:Key 1 exists
    }
    return 0;
}

访问和修改元素

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "A"}, {2, "B"}};
    std::cout << "Value at 1: " << m[1] << std::endl; // 输出:A
    m[1] = "Alice"; // 修改值
    std::cout << "New value at 1: " << m.at(1) << std::endl; // 输出:Alice

    // m.at(3) 若键不存在会抛出 std::out_of_range
    return 0;
}
  • []:若键不存在,插入默认值(需谨慎)。
  • at():若键不存在,抛异常。

大小和状态

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "A"}, {2, "B"}};
    std::cout << "Size: " << m.size() << std::endl;         // 输出:2
    std::cout << "Empty? " << (m.empty() ? "Yes" : "No") << std::endl; // 输出:No
    return 0;
}

迭代器

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
    std::cout << "Forward: ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        std::cout << "{" << it->first << ", " << it->second << "} ";
    }
    std::cout << std::endl; // 输出:{1, A} {2, B} {3, C}

    std::cout << "Reverse: ";
    for (auto it = m.rbegin(); it != m.rend(); ++it) {
        std::cout << "{" << it->first << ", " << it->second << "} ";
    }
    std::cout << std::endl; // 输出:{3, C} {2, B} {1, A}
    return 0;
}

<unordered_map> 的对比

特性std::mapstd::unordered_map
数据结构平衡二叉树哈希表
键顺序升序无序
重复键不允许不允许
查找O(log n)平均 O(1)
插入/删除O(log n)平均 O(1)
内存开销树节点+指针桶+指针
迭代器双向前向

注意事项

  1. 键唯一性:重复键插入无效,需用 <multimap> 支持重复键。
  2. 迭代器失效:插入不影响现有迭代器,删除使指向被删元素的迭代器失效。
  3. 性能:适合需要排序的场景,若只需高效查找,使用 <unordered_map>
  4. [] 的副作用:访问不存在的键会插入默认值。

实用示例:学生成绩管理

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

int main() {
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;

    std::cout << "Student Scores:\n";
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

    std::string name;
    std::cout << "Enter a student name to lookup: ";
    std::cin >> name;
    auto it = scores.find(name);
    if (it != scores.end()) {
        std::cout << name << "'s score: " << it->second << "\n";
    } else {
        std::cout << name << " not found.\n";
    }
    return 0;
}

输出示例:

Student Scores:
Alice: 95
Bob: 87
Charlie: 92
Enter a student name to lookup: Bob
Bob's score: 87

小练习

问题

写一个 C++ 程序:

  1. 定义一个 std::map<int, std::string>
  2. 插入键值对:{1, “A”}、{2, “B”}、{3, “C”}、{2, “D”}(注意重复键)。
  3. 删除键为 1 的元素。
  4. 输出所有键值对和大小。

参考答案

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

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

    // 插入元素
    m.insert({1, "A"});
    m.insert({2, "B"});
    m.insert({3, "C"});
    m[2] = "D"; // 覆盖键 2 的值

    // 删除键 1
    m.erase(1);

    // 输出所有键值对和大小
    std::cout << "Elements: ";
    for (const auto& pair : m) {
        std::cout << "{" << pair.first << ", " << pair.second << "} ";
    }
    std::cout << "\nSize: " << m.size() << std::endl;

    return 0;
}

输出:

Elements: {2, D} {3, C}
Size: 2

参考资料

  1. C++ Standard Library Reference: <map> 的官方文档。
  • ISO/IEC 14882:2011 (C++11 Standard)
  1. cppreference.com: 提供 <map> 的详细说明和示例。
  2. The C++ Programming Language (4th Edition) by Bjarne Stroustrup: C++ 容器权威书籍。
  3. Effective STL by Scott Meyers: STL 容器实用建议。

出站链接


下一步

  • 如果你想试试练习,请提交代码,我会帮你检查。
  • 如果需要更深入内容(如自定义比较器、与 <multimap> 对比),或设计测验题,请告诉我!
  • 你也可以提出具体问题,如“如何用 <map> 实现字典?”或“<map> 的红黑树实现原理?”。

现在,你想做什么?试试练习,还是有其他需求?