best data structure for byIndex and byName retrieval

Question

suppose you need to implement container of a T items, which its value could be retrieved by numeric index (which is random access) and by name (as string).

which one is better in term of performance of common operation such as retrieval, adding, and removing the items:

(in this case retrieval by index need to be implemented by walking the map)

std::map<std::string,T> container;

or (fast random access by index, but need walking for retrieval by name)

std::vector<std::pair<std::string,T>> container;

or by providing two separate container (fast retrieval, but slower adding/removal operation)

std::vector<T> byIndexContainer;
std::map<std::string,T> byNameContainer;

or you can suggest other data structure that is better?

Answer 1

Or you could go with the most awesome Boost::MultiIndex containers.

Answer 2

Your example with two separate containers would be the fastes for indexing and as you say a little slower for adding/removing. It combines the best for integer indexing and string indexing. You could always make your own type that internally has these two.

Answer 3

Map access is only logarithmic time - everything is stored as sorted internally. So if you had 10000 elements, you might expect it to take a dozen calls to std::string::operator<. If you need better random access via a string key, use a hash_map (not quite standard).

If you don't want random access for speed, but because you actually want an index for some reason, one not-much-effort solutions are to keep a sorted vector, which invalidates indices when you insert or something. You can't have a static index (the same after deletion) in general, because when you delete something, you need to either change indices by shifting things, or call that index "invalid", in which case your "indices" are really keys, because the nth index isn't the nth thing, and you can't use all indices. In that case, just use strings directly.

If you REALLY need integer keys as well as string keys, you probably need to use your two-container method. I wrote something a while back that maintains a list of unique keys (you can specialize it for integers) if you want it. It's at work somewhere, though, unless you comment I won't look for it.