Order like a list but access by a key?

Question

I used list to place cities into a trip. Then I iterate over the list to display the trip itinerary. I would like to access the cities by the name rather than by the trip order. So, I thought I could use a map rather than a list but the key determines the order. I would still like to control the order of the sequence but be able to access the entries by a key.

Can these features be combined? Is there some standard way to address this?

#include <list>
#include <iostream>
struct City{
   City(std::string a_n, int a_d):name(a_n), duration(a_d){}
   std::string name;
   int duration;
};
int main(){
    std::list<City*> trip;
    trip.push_back(new City("NY", 5));
    trip.push_back(new City("LA", 2));
    for (std::list<City*>::iterator ii=trip.begin(); ii!=trip.end(); ++ii)
        std::cout << (*ii)->name << " for " << (*ii)->duration << " days." <<std::endl;
}

Answer 1

Create a map<string,int> m;, where the values are indexes to a vector<City>, for example m["NY"] == 0 and m["LA"] == 1.

Answer 2

Use two collections:

• A list to store the actual objects in the order you are interested in.
• A map to map names to the objects.

Answer 3

Often times you will need to compose multiple lists and maps. The common way is to store a pointer to the Cities in your by city lookup map from the pointers in your list. Or you can use a class like Boost.MultiIndex to do what you want in what I would say is much cleaner. It also scales much better and there is a lot less boiler plate code if you want to add new indexes. It is also usually more space and time efficient

typedef multi_index_container<
  City,
  indexed_by<
    sequenced<>, //gives you a list like interface
    ordered_unique<City, std::string, &City::name> //gives you a lookup by name like map
  >
> city_set;

Answer 4

The best solution is to use Boost.MultiIndex, though that's slightly more involved. Unfortunately, I don't have time now to provide sample code; sorry.