C++ Basics: Insert After Existing Equal Values
Use std::upper_bound to find the position after an existing group of equal values in an ascending vector.
Prepare a scratch directory
Tested on Linux x86_64 with GCC 14.2.0. You need a C++20-capable compiler and standard-library development headers, with g++ on PATH, plus 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 1Run the example
Save this as upper-bound-after-equal-demo.cpp:
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> scores{10, 20, 20, 30};
auto position = std::upper_bound(scores.begin(), scores.end(), 20);
std::cout << "insert index: " << position - scores.begin() << '\n';
scores.insert(position, 20);
std::cout << "scores:";
for (int score : scores) std::cout << ' ' << score;
std::cout << '\n';
std::cout << "above all: "
<< (std::upper_bound(scores.begin(), scores.end(), 99) == scores.end())
<< '\n';
}Compile and run it. The program runs only after compilation succeeds:
g++ -std=c++20 -Wall -Wextra -Werror -pedantic upper-bound-after-equal-demo.cpp -o upper-bound-after-equal-demo &&
./upper-bound-after-equal-demoObserved output:
insert index: 3
scores: 10 20 20 20 30
above all: 1Read the result
The new 20 goes at index 3, after both existing 20s. A search above every value returns end, which is a valid insertion position.
Apply it carefully
Keep the range sorted with the same comparison used for searching. upper_bound locates the first element greater than the key; lower_bound locates the first element not less than it. Vector insertion can invalidate the position iterator, so compute the index before insertion and do not reuse that iterator afterward. End is suitable for insertion but never for reading an element.
The C++ working draft describes the relevant rules. This example uses C++20; the current working draft also includes later additions.
Clean up
Remove only the source and executable created here, then return to the starting directory:
rm -- upper-bound-after-equal-demo.cpp upper-bound-after-equal-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directoryIf the directory is not empty, inspect its remaining contents before removing anything else.
Acknowledgements
This post was created with assistance from AI.