c++ map的数据结构是什么|极客教程

c++ map的数据结构是什么

1. 引言

在C++的标准模板库（STL）中，map是一个非常常用的数据结构，它被用来存储键值对（key-value pair）的集合。在这篇文章中，我们将详细讨论map的数据结构、基本操作以及其在实际应用中的使用。

2. `map`的数据结构

map是一个关联式容器（associative container），它通过使用红黑树（red-black tree）实现，从而保持了元素的有序性。红黑树是一种自平衡的二叉搜索树，每个节点上都有一个额外的二元值，通常被称为“颜色”，用来表示节点的状态。

在map中，每个元素都是一个由键（key）和值（value）组成的pair对象。键用于按一定顺序对元素进行排序，而值作为与键关联的数据。由于红黑树的特性，map中的元素始终保持有序，这使得在map中进行查找、插入和删除操作都具有较高的效率。

3. `map`的基本操作

3.1 插入元素

在map中插入元素可以通过以下两种方式进行：

3.1.1 使用`insert`函数

可以使用insert函数将一个新的键值对插入到map中，示例代码如下：

#include <iostream>
#include <map>

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

    // 使用insert函数插入键值对
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    return 0;
}

3.1.2 使用下标运算符`[]`

下标运算符[]也可以用来插入元素，示例代码如下：

#include <iostream>
#include <map>

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

    // 使用下标运算符插入键值对
    myMap[1] = "apple";
    myMap[2] = "banana";
    myMap[3] = "orange";

    return 0;
}

3.2 查找元素

在map中查找元素可以使用find函数或迭代器进行操作。

3.2.1 使用`find`函数

可以使用find函数按键查找元素，如果找到则返回指向该元素的迭代器，否则返回map的尾部迭代器。示例代码如下：

#include <iostream>
#include <map>

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

    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    // 使用find函数查找元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "找到了：" << it->second << std::endl;
    }
    else {
        std::cout << "未找到该元素！" << std::endl;
    }

    return 0;
}

3.2.2 使用迭代器

可以使用迭代器遍历map的所有元素，示例代码如下：

#include <iostream>
#include <map>

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

    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    // 使用迭代器遍历所有元素
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "键：" << it->first << "，值：" << it->second << std::endl;
    }

    return 0;
}

3.3 删除元素

在map中删除元素可以使用erase函数或迭代器进行操作。

3.3.1 使用`erase`函数

可以使用erase函数按键删除元素，示例代码如下：

#include <iostream>
#include <map>

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

    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    // 使用erase函数删除指定键的元素
    myMap.erase(2);

    return 0;
}

3.3.2 使用迭代器

可以使用迭代器删除指定位置的元素，示例代码如下：

#include <iostream>
#include <map>

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

    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "orange"));

    // 使用迭代器删除指定位置的元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        myMap.erase(it);
    }

    return 0;
}