如何通过结构体成员值快速获取vector中的结构体元素

为什么不能直接重载std::vector的operator[] #

std::vector是标准库容器，其operator[]是基于容器内元素的索引位置实现的，无法直接重载为按自定义的number成员查找。要实现类似array[wanted_number]的快速访问，需要借助关联容器或自定义封装类。

几种高效解决方案 #

1. 使用std::unordered_map（哈希表，推荐） #

这是性能最优的方案，平均查找时间复杂度为O(1)，适合频繁查找的场景：

• 先构建number到Element的映射：遍历一次原vector，将number作为键，Element对象（或其引用/指针）作为值存入哈希表。
• 查找时直接通过键获取元素，无需遍历。

代码示例：

#include <vector>
#include <unordered_map>

struct Element 
{
  int number;
  Element(int number) : number(number) {}
};

int main() {
    std::vector<Element> array = {Element(3), Element(7), Element(1)};
    
    // 构建哈希映射
    std::unordered_map<int, Element> num_map;
    for (const auto& elem : array) {
        num_map[elem.number] = elem;
        // 如果允许number重复，改用unordered_map<int, std::vector<Element>>
        // num_map[elem.number].push_back(elem);
    }
    
    // 快速查找
    int wanted_number = 7;
    auto it = num_map.find(wanted_number);
    if (it != num_map.end()) {
        Element wanted_element = it->second;
        // 处理元素
    }
    return 0;
}

2. 自定义封装类，实现operator[] #

如果希望保持类似vector的使用习惯，可以封装一个类，内部同时维护原vector和number到索引的映射，重载operator[]来实现快速访问：

#include <vector>
#include <unordered_map>
#include <stdexcept>

struct Element 
{
  int number;
  Element(int number) : number(number) {}
};

class ElementStore {
private:
    std::vector<Element> elements;
    std::unordered_map<int, size_t> num_to_index;
public:
    ElementStore(std::vector<Element> vec) : elements(std::move(vec)) {
        // 构建number到vector索引的映射
        for (size_t i = 0; i < elements.size(); ++i) {
            num_to_index[elements[i].number] = i;
        }
    }

    // 重载operator[]，返回可修改的元素引用
    Element& operator[](int wanted_number) {
        auto it = num_to_index.find(wanted_number);
        if (it == num_to_index.end()) {
            throw std::out_of_range("不存在对应number的元素");
        }
        return elements[it->second];
    }

    // 常量版本，返回不可修改的元素引用
    const Element& operator[](int wanted_number) const {
        auto it = num_to_index.find(wanted_number);
        if (it == num_to_index.end()) {
            throw std::out_of_range("不存在对应number的元素");
        }
        return elements[it->second];
    }
};

// 使用示例
int main() {
    std::vector<Element> array = {Element(5), Element(2), Element(8)};
    ElementStore store(std::move(array));
    
    // 像访问vector一样获取元素
    Element wanted_element = store[2];
    return 0;
}

3. 当number是连续非负整数时的优化 #

如果number的取值是连续的（比如从0开始或从某个固定值开始的连续整数），且没有空缺，可以直接用vector的索引对应number：

• 例如number从0到N-1，直接array[wanted_number]即可；
• 如果number从start开始，计算偏移量：array[wanted_number - start]。

这种方式的查找时间是O(1)，但仅适用于number范围连续且可控的场景。

注意事项 #

• 若number存在重复值，哈希映射会覆盖之前的元素，需改用std::unordered_map<int, std::vector<Element>>来存储所有匹配元素；
• 构建映射的时间复杂度是O(n)，适合多次查找的场景；如果仅需一次查找，直接遍历vector的性能反而更优（无需额外内存和构建时间）；
• std::unordered_map的性能依赖哈希函数的质量，默认的int哈希函数足够高效，无需额外自定义。

内容的提问来源于stack exchange，提问作者NNC21July