c++ - 在 std::vector 和 std::unordered_map 之间进行选择以在少数项目中进行搜索？

Question

有一些项目可以通过按键进行迭代和搜索。我已经形成了一个 std::vector 用于迭代。我是否需要形成一个 struct 来进行搜索，例如 std::unordered_map？

我确实知道在 std::vector 中搜索导致了 O(N) 并且在 std::unordered_map 中搜索导致了 O(1)。但是里面的项目大约是10个。初始化后没有发生插入或更新。我可能会搜索很多次。可能是100万，10亿，甚至更多，我不敢肯定。

我担心散列可能比迭代更昂贵。

这是一个示例:

class Item
{
public:
    int key;
    const char* value;
};

class Items
{
public:
    Items(const std::vector<const Item> items) 
    : _vector(items)
    , _map(generateMap()){
    }

    const char* getValueByKey(int key) const {
        //which one to choose
        //map
//        const auto& iter = _map.find(key);
//        if (iter!=_map.end()) {
//            return iter->second;
//        }
//        return nullptr;
        //vector
        for (const auto& iter : _vector) {
            if (iter.key==key) {
                return iter.value;
            }
        }
        return nullptr;
    }

protected:
    const std::unordered_map<int, const char*> generateMap() const{
        std::unordered_map<int, const char*> map;
        for (const auto& item : _vector) {
            map.insert({item.key, item.value});//I can make sure that no same key will exists
        }
        return map;
    }

    const std::vector<const Item> _vector;
    const std::unordered_map<int, const char*> _map;//Is it necessary?
};

int main() 
{   
    const std::vector<const Item> items ={
        {1, "value_1"},
        {20, "value_2"},
        {10, "value_3"},
        {55, "value_4"},
    }; 
    Items theItems = items;
    srand(time(nullptr));
    for (int i = 0; i < 1000000; i++) {
        int key = rand();
        printf("%d %s exists\n", key, theItems.getValueByKey(key)==nullptr?"is not":"is");
    }
    return 0;
}

这是一个 int 关键案例，可能没有发生散列。但是其他情况呢，std::string、用户定义的struct 等等？

那么对于这种情况，理论上我应该如何决策呢？

Answer 1

政治上正确的答案是“基准!”。

但根据其他人的经验，当仅使用少量相对较小的项目时，使用 std::vector 通常更快(尤其是排序时)，因为它提高了您的项目的内存位置，并且不为其项目使用额外的堆分配/解除分配。但是，如果键类似于 std::string 并且键比较是使用其内容完成的，那么这当然可能会损害内存局部性，因为不(总是)包含字符串内容在字符串对象本身中，但在堆上。