CODEWITHSUNDEEP
c++stringsortingdictionarystl
bartekmp
bartekmp

Reputation: 413

std::map - how to change key sorting?

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?

Upvotes: 4

Views: 10168

Answers (4)

David
David

Reputation: 28178

Like others have said, you need to implement a custom comparer...

struct custom_comparer
{
    bool operator()(const std::string& left, const std::string& right) const
    {
        return std::lexicographical_compare(
            left.cbegin(), left.cend(), 
            right.cbegin(), right.cend(),
            [](char l, char r) -> bool
            {
                 bool ldigit = isdigit(l) != 0,
                      rdigit = isdigit(r) != 0;

                 return (!ldigit && rdigit) || (ldigit == rdigit && l < r);
            });
    }
};

And use it...

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

Normal string comparison operators use lexicographical_compare. My custom_comparer above also uses it, but with a custom comparer plugged in. The custom comparer uses isdigit to do the comparison you want.

Upvotes: 3

Marius Bancila
Marius Bancila

Reputation: 16338

You have to write your own comparer:

struct custom_string_comparer
{
    bool operator()(const std::string& s1, const std::string& s2)
    {
         return ...; // your comparison here
    }
};

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

Upvotes: 2

Andrew Lazarus
Andrew Lazarus

Reputation: 19362

Yes. You need to supply a third template argument, see the docs.

Upvotes: -3

juanchopanza
juanchopanza

Reputation: 227608

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.

Upvotes: 9

Related Questions