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?

score 9 · Accepted Answer · answered May 14 '13 at 14:07

9

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.

answered May 14 '13 at 14:07

juanchopanza

223,364
34
402
480

Ok, I got it, but how can I compare strings for differences? I mean, how can I find a digit inside string? – bartekmp May 14 '13 at 14:10
2

@user2342783 That's a _completely_ different question. You should ask that in a new question – stefan May 14 '13 at 14:13
@user2342783 that's a different question. But you can iterate over the elements of a string (each of which is a `char`), and do things like call [std::isdigit](http://en.cppreference.com/w/cpp/string/byte/isdigit) on them. – juanchopanza May 14 '13 at 14:13

score 3 · Answer 2 · answered May 14 '13 at 14:40

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.

score 2 · Answer 3 · answered May 14 '13 at 14:08

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;

score -3 · Answer 4 · answered May 14 '13 at 14:07

-3

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

answered May 14 '13 at 14:07

Andrew Lazarus

18,205
3
35
53

5

Although your statement is correct, it is not helpful on its own. At least write down a minimal example just like the others. Also, cplusplus.com is not _the docs_. – stefan May 14 '13 at 14:12

std::map - how to change key sorting?

4 Answers4

Linked

Related