2

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?

Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
Shefali Kanaujia
  • 23
  • 7
  • If you have `std::vector>`, you can use `std::sort`, but you will need a custom comparator. The `vec.begin()` and `vec.end()`, are for **one** vector, not nested vectors. – Thomas Matthews Jun 19 '23 at 16:03
  • If I understand the question correctly, it should work out of the box. `std::vector` does provide a comparison operator that would sort in lexicographical order, which in turn implies being sorted by the first element. In your example, the result would be `[ [1, 8], [3, 4], [7, 2] ]` - is this what you expect? – Igor Tandetnik Jun 19 '23 at 16:03
  • Please clarify how you want your matrix sorted. – Thomas Matthews Jun 19 '23 at 16:03
  • 1
    What have you tried? What version of C++ standard can you use? (this will impact how much boiler plate code is needed). – Marek R Jun 19 '23 at 16:05
  • [Possible duplicate](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c) – PaulMcKenzie Jun 19 '23 at 16:08
  • if the elements are always 2 items like that then using a vector of vector is a very bad idea. Use `std::vector` instead, or create a vector of struct like `struct coord { int x; int y }; std::vector`. Using `std::pair` has the advantage that the `operator<` is available and you can sort the vector directly – phuclv Jun 19 '23 at 16:12

1 Answers1

5

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{});
Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
  • The OP wants to: *sort accordingto first value of vector in increasing orde* – NathanOliver Jun 19 '23 at 16:16
  • @NathanOliver-IsonStrike yes. This code sorts according to the first value (`1`, `3`, `7`) of each vector in ascending order. – Jan Schultke Jun 19 '23 at 16:18
  • It does more than that, but I guess it has to otherwise just using the fiorst element wouldn't maintain a strict weak ordering. – NathanOliver Jun 19 '23 at 16:20
  • A strict weak ordering can have elements that compare equal even though they are not the same, and it can also have incomparable elements as long as incomparability is transitive. – Jan Schultke Jun 19 '23 at 16:31
  • 1
    Projection is nice feature to use here: https://godbolt.org/z/KKdax1v53 Sadly you can't use `&std::vector::front` since it returns reference and as result deduction fails. – Marek R Jun 19 '23 at 17:01