CODEWITHSUNDEEP
c++stlcontainers
Roddy
Roddy

Reputation: 68033

Which STL container for ordered data with key-based access?

Let's say I have a collection of Person objects, each of which looks like this:

class Person 
{
  string Name;
  string UniqueID;
}

Now, the objects must be stored in a container which allows me to order them so that I can given item X easily locate item X+1 and X-1.

However, I also need fast access based on the UniqueID, as the collection will be large and a linear search won't cut it.

My current 'solution' is to use a std::list in conjunction with a std::map. The list holds the Persons (for ordered access) and the map is used to map UniqueID to a reference to the list item. Updating the 'container' typically involves updating both map and list.

It works, but I feel there should be a smarter way of doing it, maybe boost:bimap. Suggestions?

EDIT: There's some confusion about my requirement for "ordering". To explain, the objects are streamed in sequentially from a file, and the 'order' of items in the container should match the file order. The order is unrelated to the IDs.

Upvotes: 9

Views: 557

Answers (3)

anon
anon

Reputation:

There is no Standard Library container that does what you want - so you will have to use two containers or the Boost solution. If using two containers, I would normally prefer a vector or a deque over a list, in almost all circumstances.

Upvotes: 7

anand
anand

Reputation: 11319

Why not to use two maps , one having Person as Key and another one having UniqueId as Key, but that requires updating both of them.

you can create a callback function which updates both the maps whenever there is any change.

Upvotes: 1

Kirill V. Lyadvinsky
Kirill V. Lyadvinsky

Reputation: 99585

boost:bimap is the most obvious choice. bimap is based on boost::multi_index, but bimap has simplified syntax. Personally I will prefer boost::multi_index over boost::bimap because it will allow to easily add more indices to the Person structure in the future.

Upvotes: 8

Related Questions