C++ 各种map特点对比分析_C/C++

特点比较

1. std::map

底层实现：基于红黑树（一种自平衡的二叉搜索树）。
元素顺序：元素按照键（key）的升序排列。
键的唯一性：每个键只能出现一次，插入重复键的元素会被忽略。
查找效率：查找操作的时间复杂度为 o ( l o g n ) o(log n) o(logn)，其中 n n n 是容器中元素的数量。
插入和删除效率：插入和删除操作的时间复杂度也为 o ( l o g n ) o(log n) o(logn)。

2. std::unordered_map

底层实现：基于哈希表。
元素顺序：元素没有特定的顺序，存储位置由键的哈希值决定。
键的唯一性：每个键只能出现一次，插入重复键的元素会覆盖原有的元素。
查找效率：平均情况下，查找操作的时间复杂度为 o ( 1 ) o(1) o(1)，但在最坏情况下可能达到 o ( n ) o(n) o(n)。
插入和删除效率：平均情况下，插入和删除操作的时间复杂度为 o ( 1 ) o(1) o(1)。

3. std::multimap

底层实现：同样基于红黑树。
元素顺序：元素按照键的升序排列。
键的唯一性：允许键重复，即可以有多个元素具有相同的键。
查找效率：查找操作的时间复杂度为 o ( l o g n ) o(log n) o(logn)。
插入和删除效率：插入和删除操作的时间复杂度为 o ( l o g n ) o(log n) o(logn)。

4. std::unordered_multimap

底层实现：基于哈希表。
元素顺序：元素没有特定的顺序，由键的哈希值决定存储位置。
键的唯一性：允许键重复。
查找效率：平均情况下，查找操作的时间复杂度为 o ( 1 ) o(1) o(1)，最坏情况下为 o ( n ) o(n) o(n)。
插入和删除效率：平均情况下，插入和删除操作的时间复杂度为 o ( 1 ) o(1) o(1)。

5. hash_map（sgi stl 扩展）

底层实现：基于哈希表。
元素顺序：元素没有特定的顺序，由键的哈希值决定存储位置。
键的唯一性：每个键只能出现一次，插入重复键的元素会覆盖原有的元素。
查找效率：平均情况下，查找操作的时间复杂度为 o ( 1 ) o(1) o(1)，最坏情况下为 o ( n ) o(n) o(n)。
插入和删除效率：平均情况下，插入和删除操作的时间复杂度为 o ( 1 ) o(1) o(1)。
在早期的 c++ 标准（如 c++98、c++03）中有 hash_map，不过它并非标准库的一部分，而是来自于 sgi stl 扩展。在 c++11 及以后的标准中，hash_map 被 std::unordered_map 替代，std::unordered_map 成为标准的哈希表实现。不过有些编译器仍然支持 hash_map，下面为你加入 hash_map 并进行比较，同时给出相应的 c++ 示例代码。

c++ 示例代码

#include <iostream>
#include <map>
#include <unordered_map>
#include <ext/hash_map>  // 对于支持 hash_map 的编译器
// 演示 std::map 的使用
void teststdmap() {
    std::map<int, std::string> mymap;
    mymap[1] = "apple";
    mymap[2] = "banana";
    mymap[1] = "cherry";  // 键 1 重复，会覆盖原有的值
    std::cout << "std::map:" << std::endl;
    for (const auto& pair : mymap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}
// 演示 std::unordered_map 的使用
void testunorderedmap() {
    std::unordered_map<int, std::string> myunorderedmap;
    myunorderedmap[1] = "apple";
    myunorderedmap[2] = "banana";
    myunorderedmap[1] = "cherry";  // 键 1 重复，会覆盖原有的值
    std::cout << "\nstd::unordered_map:" << std::endl;
    for (const auto& pair : myunorderedmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}
// 演示 std::multimap 的使用
void testmultimap() {
    std::multimap<int, std::string> mymultimap;
    mymultimap.insert({1, "apple"});
    mymultimap.insert({2, "banana"});
    mymultimap.insert({1, "cherry"});  // 键 1 重复，允许插入
    std::cout << "\nstd::multimap:" << std::endl;
    for (const auto& pair : mymultimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}
// 演示 std::unordered_multimap 的使用
void testunorderedmultimap() {
    std::unordered_multimap<int, std::string> myunorderedmultimap;
    myunorderedmultimap.insert({1, "apple"});
    myunorderedmultimap.insert({2, "banana"});
    myunorderedmultimap.insert({1, "cherry"});  // 键 1 重复，允许插入
    std::cout << "\nstd::unordered_multimap:" << std::endl;
    for (const auto& pair : myunorderedmultimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}
// 演示 hash_map 的使用
void testhashmap() {
    __gnu_cxx::hash_map<int, std::string> myhashmap;
    myhashmap[1] = "apple";
    myhashmap[2] = "banana";
    myhashmap[1] = "cherry";  // 键 1 重复，会覆盖原有的值
    std::cout << "\nhash_map:" << std::endl;
    for (const auto& pair : myhashmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}
int main() {
    teststdmap();
    testunorderedmap();
    testmultimap();
    testunorderedmultimap();
    testhashmap();
    return 0;
}

代码解释

teststdmap 函数演示了 std::map 的使用，插入重复键的元素会覆盖原有的值，元素按照键的升序排列。
testunorderedmap 函数演示了 std::unordered_map 的使用，插入重复键的元素也会覆盖原有的值，元素没有特定的顺序。
testmultimap 函数演示了 std::multimap 的使用，允许插入重复键的元素，元素按照键的升序排列。
testunorderedmultimap 函数演示了 std::unordered_multimap 的使用，允许插入重复键的元素，元素没有特定的顺序。
testhashmap 函数演示了 hash_map 的使用，插入重复键的元素会覆盖原有的值，元素没有特定的顺序。