CODEWITHSUNDEEP
c++dictionarystdmapstd
yuiyin
yuiyin

Reputation: 35

C++ efficient way to map a group of integer variables to values

In order to map a group of integer variables to values (say I have a1, a2, a3, a4, a5, a6 to determine a value v; that's a map like map<tuple<int, int, int, int, int, int>,VALUE_TYPE> or map<struct{int, int, int, int, int, int},VALUE_TYPE>), we may use

  1. string constructed from integers as key
  2. tuple as key
  3. struct or class as key
  4. and so on ...

I am very curious about the performance of these methods. In my situation,

  1. less insertion, more query
  2. wide range but sparse distribution of integer keys
  3. time concerns me more, memory less
  4. map access is the most consuming part, so even 10% speedup matters

The question is which way performs better in my situation?
If struct or class key chosen, is there any trick to make comparator more efficient?
Does unordered_map fit the situation better? How should I calculate hash of keys?

I will appreciate a lot to any suggestion or comment on solutions. And discussion on a more general situation is also welcomed. Thanks in advance.

Upvotes: 2

Views: 1877

Answers (2)

alexeykuzmin0
alexeykuzmin0

Reputation: 6440

Also, consider implementing the trie data structure if your numbers are relatively small and you have a lot of them in a key. Just like std::unordered_map this will allow you to access the element in O(l) time where l is a length of the key, but also it will allow you to iterate throw all the values in ascending order and find a value by a partial key. The problem here is that your memory consumption will be proportional to the alphabet size (of course, you can store the inner edges in some complex data structure, but this will negatively affect performance).

Upvotes: 0

Rene
Rene

Reputation: 2474

Basically: Implement the different solutions, write a performance test program and measure!

For sure:

  • Using the integers as integers will be faster than converting them to strings.
  • A struct (or class) should be faster than a tuple (my experience).
  • Also try the std::array<> container (already provides operators for comparison too).
  • Hash map (std::unordered_map<>) is faster than a sorted map (std::map<>), but can of course only be used if you don't need to search with partial keys.

Upvotes: 4

Related Questions