c++ map中如何使用和查找性能测试

C++ STL 中的 map 是一种键值对容器，它将键值对存储在有序的树形结构中。map 中的每个元素都是一对键–值对，其中每个键是 的，映射到一个值，这使得 map 成为一种非常有用的数据结构。在 C++ 中 map 的实现方式通常为红黑树，其查找、插入和删除的时间复杂度都为 O(log n)。

使用 map

为了使用 C++ 中的 map，必须包含头文件 map。

#include <map>

初始化 map 变量时，需指定键类型和值类型，可以使用模板类 std::map。下面的代码演示了如何初始化一个空 map：

std::map<std::string, int> myMap;

以上代码声明了一个键类型为 std::string，值类型为 int 的 map 变量 myMap，这个 map 是空的。

可以通过“[]”符号给 map 添加元素：

myMap["one"] = 1;
myMap["two"] = 2;

以上代码将在 map 中添加两个键值对，其中键为字符串 “one” 和 “two”，对应的值分别是 1 和 2。

也可以使用 insert 函数来添加元素到 map 中：

myMap.insert({"three", 3});
myMap.insert(std::make_pair("four", 4));

以上代码也将在 map 中添加两个键值对，其中键为字符串 “three” 和 “four”，对应的值分别是 3 和 4。

查找元素

要查找 map 中的元素，可以使用 map 中的 find 函数。

auto it = myMap.find("one");
if (it != myMap.end()) 
{
    std::cout << "Found " << it->first << " " << it->second << std::endl;
}
else 
{
    std::cout << "Not found" << std::endl;
}

以上代码会查找键为字符串 “one” 的元素，在找到时输出键和值，否则输出“Not found”。

性能测试

为了测试 map 的性能，我们可以使用 C++11 新增的计时器std::chrono。下面的程序将分别测试以插入和查找为主的两个 map 操作：

#include <iostream>
#include <map>
#include <chrono>

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

    // 测试插入的性能
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000000; ++i) {
        myMap[i] = i;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Inserting 1 million elements into map took " << duration.count() << " ms" << std::endl;

    // 测试查找的性能
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000000; ++i) {
        auto it = myMap.find(i);
        if (it != myMap.end()) {
            // 执行一些操作
        }
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Finding 1 million elements in map took " << duration.count() << " ms" << std::endl;

    return 0;
}

以上程序首先创建了一个空的 map，然后分别测试了向 map 中插入 1 百万个元素和从 map 中查找 1 百万个元素的性能。程序将在执行完每个操作后输出所用时间（以毫秒为单位）。

上述程序的运行结果表明，向 map 中插入 1 百万个元素需要 1094 ms，而从 map 中查找 1 百万个元素仅需 9 ms。这表明 map 的查找性能很高，但插入操作需要较多时间。总体上，map 在大多数情况下是一个可靠的数据结构，既可以快速插入，又可以快速查找。