C++ 字典实现方法

在C++中没有像Python那样的内置“字典”（即dict）这种直接的数据类型，但可以使用std::map或者std::unordered_map来实现类似字典的功能。这些容器位于C++标准库的<map>或<unordered_map>头文件中。

这两者都允许将“键-值对”进行存储和查找，像Python的字典一样，不过它们有一些区别：

1. std::map：

   • 是一个有序的关联容器，底层实现通常为红黑树。
   • 存储的键值对是有序的，按照键的顺序自动排序。
   • 查找、插入、删除的时间复杂度为O(log n)。

   例子：

   #include <iostream>
   #include <map>
   
   int main() {
       std::map<std::string, int> myMap;
   
       myMap["apple"] = 1;
       myMap["banana"] = 2;
   
       std::cout << "apple: " << myMap["apple"] << std::endl;
   
       // 遍历
       for (const auto& pair : myMap) {
           std::cout << pair.first << ": " << pair.second << std::endl;
       }
   
       return 0;
   }

2. std::unordered_map：

   • 是一个无序的关联容器，底层实现通常为哈希表。
   • 键值对是无序的，插入顺序与存储顺序无关。
   • 查找、插入、删除的平均时间复杂度为O(1)，但最坏情况下可能为O(n)。

   例子：

   #include <iostream>
   #include <unordered_map>
   
   int main() {
       std::unordered_map<std::string, int> myUnorderedMap;
   
       myUnorderedMap["apple"] = 1;
       myUnorderedMap["banana"] = 2;
   
       std::cout << "apple: " << myUnorderedMap["apple"] << std::endl;
   
       // 遍历
       for (const auto& pair : myUnorderedMap) {
           std::cout << pair.first << ": " << pair.second << std::endl;
       }
   
       return 0;
   }

总结

• C++中的std::map和std::unordered_map可以实现类似Python字典的功能。
• std::map是有序的，而std::unordered_map是无序的。
• 使用哪种容器取决于你的使用场景：如果你需要按键有序存储，选择std::map；如果你不关心顺序，且希望更快的查找速度，选择std::unordered_map。