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

2025-03-23 02:50
文章标签 c++ map 对比 特点 分析

本文主要是介绍C++ 各种map特点对比分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima...

特点比较

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

  • 底层实现:基于哈希表。
  • 元素顺序:元素没android有特定的顺序,由键的哈希值决定存储位置。
  • 键的唯一性:允许键重复。
  • 查找效率:平均情况下,查找操作的时间复杂度为 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_mapstd::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;
    myMultwww.chinasem.cniMap.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) {
   android     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::pythonmultimap 的使用,允许插入重复键的元素,元素按照键的升序排列。
  • testUnorderedMultiMap 函数演示了 std::unordered_multimap 的使用,允许插入重复键的元素,元素没有特定的顺序。
  • testHashMap 函数演示了 hash_map 的使用,插入重复键的元素会覆盖原有的值,元素没有特定的顺序。

需要注意的是,hash_map 不是标准 C++ 的一部分,如果你使用的编译器不支持 ext/hash_map 头文件,代码可能无法编译。建议优先使用标准的 std::unordered_map

到此这篇关于C++ 各种map对比的文章就介绍到这了,更多相关C++ map对比内容请搜索China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程China编程(www.chinasem.cn)!

这篇关于C++ 各种map特点对比分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1153890

相关文章

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat