Algorithms: sort, boundary search, and erase-remove

Sorting first requires a correct comparison

std::sort needs random-access iterators and elements that can be moved and swapped. The comparison count is O(n log n). It does not promise that equivalent elements keep their original order; use stable_sort when that stability is required. The standard constrains the result and the complexity. It does not require sort to be quicksort or any particular hybrid.

The comparator must form a strict weak ordering: comp(x,x) is false, the before-relation is transitive, and the equivalence of "neither comes first" is also transitive. Writing a <= b violates the irreflexive condition. Depending on random numbers or changing global state is equally invalid. Floating-point NaN breaks ordinary less-than as a strict weak order on data that contain NaN. Exclude those values first, or define a consistent policy that includes NaN.

A boundary search returns a position, not a guaranteed equal value

On ascending data, lower_bound returns the first position that is not less than the target and upper_bound returns the first position that is greater. The interval between them is the equivalent-element range. If lower_bound returns end, it must not be dereferenced. Even when it does not return end, you still have to check whether the target is equivalent; an insertion point is not a match.

What generic boundary algorithms actually require is that the range is already partitioned with respect to the current query expression. Full ordering is the usual sufficient condition. The query's comparison direction must match the sort. The comparison count is logarithmic, but non-random-access iterators may still need a linear number of increments. On set and map, prefer the member boundary queries.

remove and erase each do half the work

remove_if stably packs kept elements to the front of the range and returns the new logical end. Container size does not change. Objects in the tail still exist, with values that are valid but unspecified. Do not treat the tail as "the set of deleted values," and do not depend on the particular numbers left behind by one run. Only a container erase actually destroys the tail elements and shrinks the size.

The example first sorts and queries a duplicate interval, then deletes every even number, checking logical length and physical length separately. The whole filter plus tail erasure is linear work, usually better than calling erase in a vector on every match. C++20 std::erase_if can express common container filtering. list's member remove_if can delete nodes directly and should be preferred there.

Pitfalls

• Using <= as a sort comparator is not the correct way to "allow equals." Equivalence is both directions comparing false.
• The position remove_if returns is not a deleted element, and it does not change size. Pair it with erase, and do not read the tail to reconstruct the original deleted items.

Minimum C++11 · complete program · Download .cpp

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

int main() {
    std::vector<int> values{5, 2, 3, 2, 4, 1};
    std::sort(values.begin(), values.end());
    assert((values == std::vector<int>{1, 2, 2, 3, 4, 5}));
    auto first = std::lower_bound(values.begin(), values.end(), 2);
    auto last = std::upper_bound(values.begin(), values.end(), 2);
    assert(last - first == 2);
    assert(std::lower_bound(values.begin(), values.end(), 9) == values.end());

    auto new_end = std::remove_if(values.begin(), values.end(),
                                  [](int x) { return x % 2 == 0; });
    assert(values.size() == 6 && new_end - values.begin() == 3);
    values.erase(new_end, values.end());
    assert((values == std::vector<int>{1, 3, 5}));
    std::cout << values[0] << ' ' << values[1] << ' ' << values[2] << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-algorithms.cpp -o example && ./example

Expected result

1 3 5

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

The sequence {9,7,7,3} is already sorted descending with std::greater<int>. How do you find every 7, and where do lower_bound and upper_bound land?

Check the sources

• Working draft [alg.sorting]: strict weak ordering and sort
• Working draft [alg.binary.search]: partition precondition
• Working draft [alg.remove]: logical removal and tail state

Drafts and official chapters change. The version mark is only the example’s minimum.