Choice Between std::vector and std::unordered_map For Searching In Few Items Case?

Question

There are a few items to iterate and search by the key. And I already form a std::vector for iteration. Do I need to form a struct for searching such as std::unordered_map?

I do know searching in std::vector resulted in O(N) and searching in std::unordered_map resulted in O(1). But the items inside are about 10. No insert or update happened after initialization. I may search for many times. Maybe 1 millions, 1 billions, or even more, I can't make sure of it.

I am concerned that hashing may be costlier than iteration.

Here is a sample:

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;
}

Here is an int key case, maybe no hashing happened. But what about other cases, a std::string, a user-defined struct and so on?

So how should I make my decision for this kind of case theoretically?

Answer 1

The politically correct answer is "benchmark!".

But based on the experience of others, when only using a small number of items of relatively small size, using a std::vector is usually faster (especially if its sorted), because it improves memory locality of your items and does not use extra heap allocations/deallocations for its items. However, if the key is something like a std::string and key-comparisons are done using its contents, then this of course might hurt memory-locality, because the string contents are not (always) contained in the string object itself, but on the heap.