Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

Sorting, comparisons, and search ranges

Correct sorting requires a comparator that defines a strict weak ordering. Binary search requires a range partitioned for the relevant condition; sorting the entire range is sufficient but not always necessary.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);

std::sort from <algorithm> orders the half-open range [first, last) using comp: no later element precedes an earlier one. It requires random-access iterators and elements meeting its move and swap requirements. It performs O(N log N) comparisons. It does not guarantee preservation of the order of equivalent elements; use std::stable_sort for that.

The comparator must define a strict weak ordering. comp(a, b) means that a precedes b, and comp(a, a) must be false. The relation must be transitive. Equivalence, defined as !comp(a, b) && !comp(b, a), must also be transitive and need not match operator==. Do not use <=: it violates the requirement for identical arguments. Failing the comparator requirements invalidates the algorithm's guarantees.

Strict weak ordering and partitioned search ranges are related but distinct requirements. A range partitioned for a predicate has all elements yielding true before all elements yielding false; either part may be empty. For std::lower_bound(first, last, value, comp), that predicate is comp(e, value). The function returns the boundary: the first element yielding false, or last. This does not establish that the searched value is present; do not dereference last.

Sorting with the same ordering ensures this partition for every key. For one key, partitioning alone suffices: [2, 1, 4, 3] satisfies the std::lower_bound precondition for value = 3 and comparison <, despite not being sorted. Other binary-search functions have their own partition requirements. std::lower_bound performs O(log N) comparisons, but without random-access iterators it can take a linear number of iterator steps.

The example sorts integers, then uses the same comp to obtain index 3. The content targets C++23; the supplied reference is an evolving working draft, not a frozen C++23 publication. Compiler and production-runtime support are not attested.

Examples

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

int main() {
    std::vector<int> values{4, 1, 3, 1, 2};
    const auto comp = [](int a, int b) { return a < b; };

    std::sort(values.begin(), values.end(), comp);
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';

    const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
    std::cout << "index=" << (it - values.begin()) << '\n';
}

Result

1 1 2 3 4
index=3

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources