面试题：C++ map键值查找优化之自定义比较器

Question

假设你有一个自定义结构体`MyStruct`，包含两个成员变量`int id`和`string name`。现在你要使用`map<MyStruct, double>`来存储数据，并通过`id`进行高效查找。请实现一个自定义比较器，使得`map`能按照`id`从小到大排序，从而优化查找操作，同时分析这种优化对查找时间复杂度的影响。

Answer 1

1. 自定义比较器实现：

   #include <iostream>
   #include <map>
   #include <string>
   
   struct MyStruct {
       int id;
       std::string name;
   };
   
   struct CompareById {
       bool operator()(const MyStruct& a, const MyStruct& b) const {
           return a.id < b.id;
       }
   };
   

   这里定义了一个CompareById结构体，重载了operator()，使得map在比较MyStruct类型的键时，按照id从小到大排序。

2. 使用自定义比较器的map定义：

   std::map<MyStruct, double, CompareById> myMap;
   

3. 查找时间复杂度分析：

   • 对于普通的无序容器（如unordered_map），在理想情况下，查找操作的平均时间复杂度为(O(1))，但最坏情况下可能达到(O(n))（例如哈希冲突严重时）。
   • 对于使用上述自定义比较器的map，map内部是基于红黑树实现的。在这种情况下，查找操作的时间复杂度为(O(\log n))，其中(n)是map中元素的个数。这是因为红黑树的高度为(O(\log n))，而查找操作的时间复杂度与树的高度相关。通过按照id排序，使得查找时能够利用树的有序性，每次比较可以排除大约一半的节点，从而优化了查找操作，相较于无序容器在最坏情况下的(O(n))时间复杂度，具有更好的性能表现。