What does comparator return really mean in C++

Question

I am trying to do stable sort in C++ and my array is like this

{{first = "art zero", second = "let3 "}, {first = "own kit dig", second = "let2 "}, {first = "art can", second = "let1 "}}

sort(let.begin(), let.end(),
[](pair<string,string>& a, pair<string,string>& b) {
    int comp = a.first.compare(b.first);
    if(!comp) {
        return a.second.compare(b.second);
    } else {
        return comp;
    }
});

Why it did not sort lexicographically for the first value? And what does the return value really mean in C++ comparator? Thanks

Answer 1

If you simply choose std::map as your container, the default ordering provides storage in lexical sort order, e.g.

#include <iostream>
#include <string>
#include <map>

int main (void) {
    
    std::map<std::string, std::string> let {{"art zero", "let3 "}, 
                                            {"own kit dig", "let2 "},
                                            {"art can", "let1 "}};
    for (const auto& p : let)
        std::cout << p.first << ", " << p.second << '\n';
}

Example Use/Output

$ ./bin/map_sort_lex
art can, let1
art zero, let3
own kit dig, let2

Sorting On Both You Cannot Use map/mutimap

If you must sort telegraphically on both .first and .second you cannot use std::map/std::multimap. They are limited to sorting on .first for storage. An alternative is a std::vector<std::pair<>> with your pairs of strings.

You can implement your custom compare by writing a simple bool Compare function as follows:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

bool lexcmp (const std::pair<std::string, std::string>& lhs, 
             const std::pair<std::string, std::string>& rhs)
{
    if (lhs.first != rhs.first)
        return lhs.first < rhs.first;
    
    return lhs.second < rhs.second;
}

int main (void) {
    
    std::vector<std::pair<std::string, std::string>> let {{"art zero", "let3 "}, 
                                                          {"art zero", "let2 "},
                                                          {"own kit dig", "let2 "},
                                                          {"art can", "let1 "}};
    
    std::sort (let.begin(), let.end(), lexcmp);
    
    for (const auto& p : let)
        std::cout << p.first << ", " << p.second << '\n';
}

Example Use/Output

After adding an additional "art zero", "let2 " pair to force the sort on .second, you would have:

$ ./bin/vector_sort_lex
art can, let1
art zero, let2
art zero, let3
own kit dig, let2

If you can get away with only sorting on .first, then std::map (or std::multimap) handle the sorting for you. To sort on both .first and .second, then the solution above isn't bad either.

Answer 2

std::pair and std::string already provide lexicographical ordering by default so you don't need to write a compare function for this task.

If you do want to write a compare function it must satisfy the Compare requirements. It must provide a strict weak ordering. That means it returns true if the first value appears before the second and false otherwise.

You can fix your code so it returns true for "less than" and false otherwise.

sort(let.begin(), let.end(), [](const pair<string,string> &a, const pair<string,string> &b){
    int comp = a.first.compare(b.first);
    if (comp == 0) {
        return a.second.compare(b.second) < 0; // less than (ascending order)
    } else
        return comp < 0; // less than (ascending order)
});