本文主要是介绍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_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; 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特点对比分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!