CODEWITHSUNDEEP
c++c++11unordered-map
Humam Helfawi
Humam Helfawi

Reputation: 20311

Returning zero when the key is not exist in unordered_map

I have the following container:

std::unordered_map<uint8_t,int> um;

um is assumed to have keys between 0 and 255 but not all of them. So, in certain point of time I want to ask it to give me the value of the key 13 for example. If it was there, I want its value (which is guaranteed to be not 0). If not, I want it to return 0.

What is the best way (performance point of view) to implement this?

What I tried till now: use find and return 0 if it was not found or the value if it was found.

P.S. Changing to std::vector<int> that contains 256 items is not an option. I can not afford the space to storing 256 values always.

EDIT:

My problem is histogram computing problem keys (colors 0-255) values(frequent, int is enough). I will not be satisfied if I just know that some key is exist or not. I also need the value (the frequent).

Additional information:

Upvotes: 2

Views: 1419

Answers (2)

Arun
Arun

Reputation: 20403

I might use a vector for space compactness.

It is tempting to keep it sorted for logarithmic search performance. But since the expected number of elements is less than 10, I might just leave it unsorted and use linear search.

So

vector<pair<uint8_t, int>> data;

If the number of expected elements is large, then having a sorted vector might help.

Boost offers a map-like interface with vector-like layout. See boost flat_map at http://www.boost.org/doc/libs/1_48_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx

Upvotes: 0

Jarod42
Jarod42

Reputation: 218323

You have a trade-off between memory and speed.

Your unordered_map should have the less speed complexity.

Using std::vector<std::pair<uint8_t, int>> would be more compact (and more cache friendly).

std::pair<std::vector<uint8_t>, std::vector<int>> would be even more compact (no padding between uint8_t and int)

You can even do better by factorizing size/capacity, but it is no longer in std::.

With vector, you have then an other trade of: complexity for searching and add key:

  • unsorted vector: constant add, Linear search
  • sorted vector: linear add (due to insert value in middle of vector), logarithmic search.

Upvotes: 4

Related Questions