Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 281
Roddy Avatar asked Jul 12 '10 11:07

Roddy


1 Answers

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.

like image 54
Kirill V. Lyadvinsky Avatar answered Oct 19 '22 15:10

Kirill V. Lyadvinsky