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

相关文章

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin