C++ which data structure do I need for this application?

[frying_pan_cat]

I'm trying to work out which data structure is best/most efficient for my application. I want to be able to store a list of names and their positions which the corresponding position in another array and be able to look up the position using the name.

In perl I'd use a hash but I'm not sure if there is a better way to do it, and if there's a corresponding structure in C++

 

[D.P.]

A hash table in C++ is called an unordered_map
Make sure you enable c++11 in the compiler options.

Something like this is useful to help decide upon a container, although this one is a little outdated without unordered maps and sets
http://adrinael.net/containerchoice


You have to be careful over some subtleties. Lets say the key was a concatenation of first and last name, if there is a chance that you will get 2 people with the same first and last names then you will want a multi-map or make a more complex key. Then you have to figure that generating a hash for a string key is O(N).

if you ever want a list of names in alphabetical order then you lmght consider an ordered map vs unordered, you amortize the sorting costs but lookups will be O(NLogN)


If you want multiple containers with different attributes (generally not efficient), then instead of string keys by the names with you are best generating a user iD as an unsigned integer and having other containers keyed by that. In fact the other containers can then actually just be a vector if you have vaguely ordinal monotonic IDs.