2

I want to create a std::unordered_map < int, std::string > or std::unordered_map< std::string, int >. In this map I will store strings and their integer representations. I'll fill this map only in the code(hard coded pairs).

I'll need convert input strings to their int values - find in map. So I only need to search in the map at the run time. At this point I need the best performance while converting. In the best case - O(1).

My questions:

  1. Should I use string as key or int ?
  2. Should I define my own hash-function ?
  3. What is the best-performance find function for the both cases string/int and int/string as key-pairs?
Cœur
  • 37,241
  • 25
  • 195
  • 267
Hardwired
  • 804
  • 1
  • 8
  • 19

1 Answers1

1

std::map or std::unordered_map or their multi-counterparts all are built up the same - they map a key (first template parameter) to a value (second one). If you want to get O(1) (unordered) or O(log(n)) (map) behaviour, you need to define as key that data type you want to get a value for.

As you want to find an integral value for a given string, the way to go in your case is std::unordered_map<std::string, int>.

A counter-example would be looking up names for error codes, there you typically have a specific error code returned by a function (or placed in errno) and want to get a string value for e. g. for printing the error to console. Then you'd have std::unordered_map<int, std::string> (provided you could not store the error strings in an array because of error codes being too far distributed...).

Edit:

Defining your own hash function is that kind of premature optimisation Konstantin mentions in his comment - std::string provides its own hash code function, which should fit well for most of the use cases. Only if you discover that your hashing gets too slow, try to find a faster way.

As all your strings are hard-coded, you might want to have a look at perfect hashing, e. g. in the gperf variant.

Aconcagua
  • 24,880
  • 4
  • 34
  • 59
  • Thank you. So, for simply hardcoded paris I should prefer to use unordered_map for searching integer values by incoming string and vice versa. – Hardwired Mar 14 '17 at 15:10
  • @SashaDerkach Vice versa??? I thought you'd just look up ints for the strings? Maps are - by their nature - only fast/efficient in one direction. In the other direction, you need to iterate over (potentially) all contained pairs. If this really is a requirement, then I'll edit my answer... – Aconcagua Mar 14 '17 at 15:24
  • @ Aconcagua No, it's not a requirement. But what is the best way to do searching in the both directions? – Hardwired Mar 14 '17 at 16:24
  • Well, you only can get compromises then. "Best" depends then on your concrete requirements. If you know that you are mostly looking up in one direction and the other one is a rare case - use the map for the common case. If you expect both lookups being equal common, use as value the type with cheaper comparison (here: int), and the other one as key. If you really are required to have both lookups fast, use *both* maps! This makes both lookup direktions fast at the cost of redundant data and higher memory consumption (so memory usage should not be a concern then). – Aconcagua Mar 14 '17 at 16:37