std::map - how to change key sorting?

Question

I have a problem with std::map. I'm using it to map some list of pairs under a specific index:

map<string, list<pair<string, int> > > List;

It's used in Dijkstra algorithm. The main problem is that map sorts string keys in alphabetical order, like this:

AAA, AA0, AA1, AAB, AC1 = AA0->AA1->AAA->AAB->AC1

But I would like to sort it in a different way:

AAA, AA0, AA1, AAB, AC1 = AAA->AAB->AA0->AA1->AC1

Is there any solution to this? I read about making my own comparing class, but I have no idea how to do this. Or maybe there's some other way to solve it?

Answer 1

You have to provide your own comparison functor, which must be passed as 3rd template parameter when instantiating the map. For example:

struct Comp
{
  bool operator()(const std::string& lhs, const std::string& rhs) const
  {
    // implement your comparison logic here
  }
};

Instances of this class is callable (hence "functor") with two string parameters, and should return true or false based in a strict weak ordering logic.

Then instantiate the map using the functor type:

std::map<string, list<pair<string, int>>, Comp> List;

Now the map will use your comparison logic internally to define the ordering of its elements.