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.

Answer 2

If you are not going to change your data and you need to do many searches I suggest you to try to use a std:vector and sort it. Then you can use a find algorithm such as binary_search, lower_bound or upper_bound from the STL exploiting the fact that the container is sorted.

You get the best: both locality and O(log(N)) complexity.

Answer 3

In the case of a small number of items, but with a lookup on the order of a billion times, we need to see which is faster, a short iteration of a vector vs an unordered_map, which as stated above can give you O(1) performance as long as you avoid collisions. A single iteration of a vector is likely to be faster than the hashing of a map. The question then becomes how many items does the map become faster for an average lookup. To determine that answer you should perform bench-marking between the two to see what actually gives the best time for your particular situation.

Alternatively, because you mention no insert or update will happen after initialization, if the range of your keys is small you can use a lookup table which would give you the fastest performance (no hashing issues) at the cost of slight memory overhead.

Answer 4

I would take a look at boost::flat_map, which provides a map interface over a vector implementation.

Regardless of the Big O complexity, the fact is that your hardware will perform much better with a vector than a map because of data locality and prefetching data from main memory.

Quoting Chandler Carruth, "Maps are an exercise in slowing down your code"