September 16th, 2012, 11:19 AM
which std container to choose
i have a pile of data, which i need to access frequently and fast.
One entry consists of two unsigned ints, let`s call them source and destination.
One source can have several destinations, but this rarely ever happens.
Several sources can have the same destination - this happens more frequently, but still scarcely.
Once the data is set up, it rarely ever changes - yet it should be possible to add or remove entries.
I now need to find all sources for a given destination, or all destinations for a given source.
The question: which stl container to choose?
I have tried a multimap, using the source as key. This works good for finding all d for a given s, but is inefficient in the other direction.
Do you think it would be more efficient to have two multimaps, sorted respectively by source and destination?
September 16th, 2012, 11:40 AM
Re: which std container to choose
I would have one unordered_map with source as key, each key associated with a vector of destinations. Then I would have another unordered_map with destination as key, each key associated with a vector of sources.
Originally Posted by tuli
Using std::unordered_map and std::vector like this would be very fast and flexible.
Last edited by nuzzle; September 17th, 2012 at 05:07 AM.
Click Here to Expand Forum to Full Width