std :: vector和std :: unordered_map之间的选择用于搜索少数项目案例？

Question

有几个项目可以通过密钥进行迭代和搜索.我已经形成了std::vector迭代.我需要形成一个struct搜索,如std::unordered_map？

我确实知道搜索std::vector结果O(N)并搜索std::unordered_map结果O(1).但是里面的项目大约是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关键案例,也许没有哈希发生过.但是其他情况,a std::string,用户定义struct等等呢？

那么我应该如何从理论上对这种情况做出决定呢？

Answer 1

政治上正确的答案是"基准!".

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