C++ sort (std::sort): sort a vector or array

std::sort in C++ puts the elements of a vector or array in order: std::sort(v.begin(), v.end()) sorts a vector from smallest to largest. Include <algorithm>. Pass a third argument, a comparison such as std::greater<>() or a lambda, to sort in descending order or by one member of a struct.

Test scores in a std::vector, sorted in a whole program:

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

int main() {
    std::vector<int> scores{72, 95, 41, 88};

    std::sort(scores.begin(), scores.end());

    for (int s : scores) {
        std::cout << s << '\n';
    }
}

It printed:

41
72
88
95

The answer is written for C++17 (Since When’s C++17 table), with std::ranges::sort the one C++20 call. The samples were built with MSVC 19.44, Clang 19.1 (MSVC STL), GCC 16.2 and Clang 23.1 (libc++), and every one that ran printed the same on all four.

How do you sort a vector in descending order?

Pass std::greater<>() as the third argument, or a lambda, a small function written in place, that returns a > b. std::greater is in <functional>; the form with empty angle brackets needs C++14 or later.

#include <functional>
// ...
std::sort(scores.begin(), scores.end(), std::greater<>());
// ...
std::sort(scores.begin(), scores.end(),
          [](int a, int b) { return a > b; });

Both printed 95, 88, 72 and 41.

How do you sort an array or a string?

For a built-in array, pass std::begin(scores) and std::end(scores); a std::string takes begin() and end() like a vector. std::sort takes two random-access iterators, positions that can jump straight to any element, as a vector’s, an array’s and a string’s can, so week.begin() + 3 as the end sorts only the first three elements:

#include <string>
// ...
int scores[]{72, 95, 41, 88};

std::sort(std::begin(scores), std::end(scores));
// ...
std::string word = "banana";

std::sort(word.begin(), word.end());
// ...
std::vector<int> week{72, 95, 41, 88, 60};

std::sort(week.begin(), week.begin() + 3);    // the first three

The array came out 41, 72, 88, 95 and the word aaabnn. The week printed 41, 72, 95, 88, 60: the first three in order, the last two where they were.

How do you sort a vector of structs or pairs by one member?

Pass a lambda that takes two elements and returns true when the first goes before the second. Players by score compare a.score < b.score; pairs by their second value compare a.second < b.second:

struct Player {
    std::string name;
    int score;
};
// ...
std::vector<Player> players{
    {"Ada", 88}, {"Dee", 72}, {"Cy", 95}, {"Bo", 72}};

std::sort(players.begin(), players.end(),
          [](const Player& a, const Player& b) {
              return a.score < b.score;    // does a go before b?
          });
// ...
std::vector<std::pair<std::string, int>> scoreboard{
    {"Ada", 88}, {"Bo", 72}, {"Cy", 95}};

std::sort(scoreboard.begin(), scoreboard.end(),
          [](const auto& a, const auto& b) {
              return a.second < b.second;
          });

The players came out Dee 72, Bo 72, Ada 88, Cy 95, and the pairs Bo 72, Ada 88, Cy 95. Write > in place of < to put the highest score first. The lambda must not change the elements it is handed; taking them by const reference makes sure it cannot.

Why must the comparison be a strict “less than”?

Because the comparison must return false for two equal elements, and <= returns true for them. cppreference’s Compare requirements spell out the rule that <= breaks: comparing an element with itself must return false. The standard requires the comparison to be a strict weak ordering ([alg.sorting.general]), and a comparison that is not one makes the call undefined behavior. Write < or >, not <= or >=:

std::vector<int> scores{72, 95, 41, 88, 72};
std::sort(scores.begin(), scores.end(),
          [](int a, int b) { return a <= b; });    // wrong: <=

All four compilers built this code with no warning at /W4 and -Wall -Wextra. With the tie, a debug build with Microsoft’s library, the only way the samples ran it, stopped inside the sort with Assertion failed: invalid comparator. On the four scores of the first example, with no tie, the same build sorted them and reported nothing. So the mistake shows only when two elements are equal, which is why it hides.

The full rule, and how to compare on two members at once, is in how to write comparators for std::sort and std::map.

When do you need std::stable_sort?

When elements that compare equal must keep the order they had. std::sort does not promise that: “The order of equivalent elements is not guaranteed to be preserved.” std::stable_sort, also in <algorithm>, guarantees it. In the score sort above, Dee stayed ahead of Bo, as in the input; a small example can keep its ties by luck.

Sort by name first, then stable-sort by score, and players with the same score stay in name order:

std::sort(players.begin(), players.end(),
          [](const Player& a, const Player& b) {
              return a.name < b.name;      // first by name
          });

std::stable_sort(players.begin(), players.end(),
                 [](const Player& a, const Player& b) {
                     return a.score < b.score;    // then by score
                 });

It printed:

Bo 72
Dee 72
Ada 88
Cy 95

std::stable_sort tries to allocate a buffer as large as the range and makes more comparisons without one, so when the order of ties does not matter, std::sort is the call.

What does std::ranges::sort change in C++20?

std::ranges::sort takes the container itself instead of two iterators, and it can sort by a member without a lambda, through a projection: something applied to each element before the comparison, here &Player::score. It is C++20 and in <algorithm>:

std::ranges::sort(scores);    // C++20: the container itself
// ...
std::ranges::sort(players, {}, &Player::score);  // C++20: by score

The {} keeps the default comparison, so both sort ascending: 41, 72, 88, 95, then Dee 72, Bo 72, Ada 88, Cy 95. Built as C++17, all four compilers rejected it; compile with -std=c++20 or /std:c++20. Like std::sort, it is not stable.

What can std::sort not sort?

A std::list. std::sort needs random-access iterators, ones that can jump straight to any position, and a list’s iterators can only step to the next or previous element. A std::set and a std::map need no sorting at all: they keep their elements sorted already. The other containers are in Standard library.

This does not compile:

std::list<int> numbers{72, 95, 41, 88};
std::sort(numbers.begin(), numbers.end());

None of the four compilers’ first error lines says “random access”. GCC’s:

error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')

The sort subtracts one iterator from another to count the elements, which a list’s iterators cannot do. Call the list’s own sort() instead, which keeps equal elements in order:

numbers.sort();    // the list's own sort

It printed 41, 72, 88, 95.

Which sort call for which job?