面试题：C++ vector复杂场景下基于值查询时间复杂度的权衡

设计思路

使用unordered_map辅助查询：为了快速基于CustomClass中某个特定成员变量的值进行查询，可以使用unordered_map。将CustomClass中的特定成员变量作为unordered_map的键，将vector<CustomClass>中对应元素的索引作为值。这样在查询时，可以通过unordered_map快速定位到vector中的元素。
数据结构定义：

#include <iostream>
#include <vector>
#include <unordered_map>

class CustomClass {
public:
    int id; // 假设这个是特定查询成员变量
    int otherData;
    CustomClass(int i, int o) : id(i), otherData(o) {}
};

class QueryHelper {
private:
    std::vector<CustomClass> dataVector;
    std::unordered_map<int, std::vector<size_t>> idToIndexMap;
public:
    void addElement(const CustomClass& obj) {
        size_t index = dataVector.size();
        dataVector.push_back(obj);
        idToIndexMap[obj.id].push_back(index);
    }

    std::vector<CustomClass> findElementsByID(int targetId) {
        std::vector<CustomClass> result;
        auto it = idToIndexMap.find(targetId);
        if (it != idToIndexMap.end()) {
            for (size_t index : it->second) {
                result.push_back(dataVector[index]);
            }
        }
        return result;
    }
};

时间复杂度分析

添加元素操作：
- 向vector中添加元素的时间复杂度为$O(1)$（平均情况，不考虑动态扩容的分摊情况）。
- 向unordered_map中插入元素的时间复杂度平均为$O(1)$。所以添加元素的整体时间复杂度为$O(1)$。
查询操作：
- 在unordered_map中查找特定键的时间复杂度平均为$O(1)$。
- 遍历unordered_map中对应的值（即vector的索引列表），假设每个ID对应的元素个数为$k$，则遍历的时间复杂度为$O(k)$。所以查询操作的平均时间复杂度为$O(k)$。

不同场景下的权衡

查询频率与内存占用：
- 如果查询频率非常高，使用unordered_map辅助查询可以显著提高查询效率，虽然增加了一定的内存占用（用于存储unordered_map），但在这种场景下是值得的。
- 如果查询频率较低，而内存比较紧张，那么引入unordered_map可能不太划算，因为会额外消耗内存。
数据更新频率：
- 如果数据频繁更新，特别是特定查询成员变量的值频繁变化，需要在更新vector中的元素后同步更新unordered_map，这会增加代码维护成本和操作的时间复杂度。在这种情况下，可能需要重新评估数据结构的设计。
- 如果数据相对稳定，只进行少量的插入和查询操作，上述设计能很好地满足需求，代码维护成本也相对较低。

星途面试题库

面试题：C++ vector复杂场景下基于值查询时间复杂度的权衡

知识考点

面试题答案

设计思路

时间复杂度分析

不同场景下的权衡