C++ Basics: Find a Sorted Insertion Position with lower_bound

Locate the first element not less than a value and insert without breaking sorted order.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as lower-bound-insertion-demo.cpp:

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

int main() {
    std::vector<int> values{10, 20, 20, 40};
    const int incoming_value = 20;
    const auto position = std::lower_bound(values.begin(), values.end(),
                                            incoming_value);
    std::cout << "Insertion index: " << (position - values.begin()) << '\n';
    values.insert(position, incoming_value);
    std::cout << "Values:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    const bool found = std::binary_search(values.begin(), values.end(), 30);
    std::cout << "Contains 30: " << std::boolalpha << found << '\n';
}

Compile and run it. The second command runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic lower-bound-insertion-demo.cpp -o lower-bound-insertion-demo &&
./lower-bound-insertion-demo

Observed output:

Insertion index: 1
Values: 10 20 20 20 40
Contains 30: false

Read the result

The returned iterator points at the first 20, so the insertion index is one. Inserting there keeps ascending order and places the new duplicate before the existing equal values.

Apply it carefully

The range must be partitioned for the comparison; keeping it sorted with the same comparator is the usual way to satisfy this. lower_bound can return end(), which is a valid insertion position but must not be dereferenced. Vector insertion can invalidate iterators, so this example does not reuse position afterward. Binary search reduces comparisons, but insertion still moves later vector elements.

The C++ working draft describes the relevant library rules. This example uses only C++20 facilities, even though the linked draft also documents newer additions.

Clean up

Remove only the source and executable created here, then remove the empty practice directory:

rm -- lower-bound-insertion-demo.cpp lower-bound-insertion-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.