Sorting vectors of vectors in C++

Question

Can we sort vectors of vectors like:

{[7, 2], [1, 8], [3, 4]}

using std::sort(vec.begin(), vec.end()), according to first element in each vector in ascending order, or do we need to pass custom comparator function to std::sort?

Answer 1

You can sort vectors of vectors without any custom comparators. If you don't provide one, then std::vector::operator< will be used. This operator performs a lexicographical comparison of the elements inside.

For example:

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

int main()
{
    std::vector<std::vector<int>> vecs{{7, 2}, {1, 8, 5}, {3}};
    
    // until C++20
    std::sort(vecs.begin(), vecs.end());

    // since C++20
    std::ranges::sort(vecs);

    for (const auto &v : vecs) {
        for (int x : v) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    }
}

Output

1 8 5 
3 
7 2 

Note: the operator< will first compare the first element, and if it's the same in both vectors, it will compare the remaining elements. If you only want to compare the first element to save performance, you still need a custom comparator, which you could do as follows:

// since C++11, could also be written as a lambda expression
struct first_element_compare {
    
    /* static since C++23*/
    constexpr bool operator()(const std::vector<int>& a,
                              const std::vector<int>& b) const
    {
        // FIXME: this code crashes when a or b is empty
        //        we must decide how these vectors compare to each other
        return a.front() < b.front();
    }
};

// ...

// until C++20
std::sort(vecs.begin(), vecs.end(), first_element_compare{});

// since C++20
std::ranges::sort(vecs, first_element_compare{});