Algorithms over a range
Sort, reverse, search, sum, remove, and deduplicate with the right return types and costs.
Free algorithms receive iterators
std::sort(v.begin(), v.end()) orders integer elements nondecreasingly and modifies the vector. A vector has no sort() member. Sorting preserves duplicates. std::reverse changes order but does not sort an arbitrary sequence.
Sorting n integers needs O(n log n) comparisons for nontrivial sizes. Reversal takes a linear number of swaps. A comparison involving long strings can cost more than an integer comparison, so include the element cost when appropriate.
A search returns a position; a sum needs a type
std::find scans an unsorted or sorted range and returns the first matching iterator, or the supplied last iterator if absent. Compare to end() before dereferencing. For a vector, subtracting begin() from a valid returned iterator gives its zero-based index.
std::accumulate starts with the initial value you supply. Use 0LL for a long long accumulator. Assigning accumulate(..., 0) into a long long variable does not widen additions that already happened in int. An empty range returns the initial value.
// Complete C++23 program. No input; output: 1 17
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> values{5, 7, 7, -2};
auto it = std::find(values.begin(), values.end(), 7);
if (it == values.end()) std::cout << -1;
else std::cout << (it - values.begin());
std::cout << ' ' << std::accumulate(values.begin(), values.end(), 0LL)
<< '\n';
}Optional: erase all matches, then deduplicate
The free function std::erase(values, target), declared for vectors in <vector>, removes every matching value and returns the number removed. It differs from the member values.erase(iterator), which removes one position.
std::unique compacts consecutive equal values and returns a new logical end; it does not shrink the vector. Sort first if all equal values should become adjacent, then erase the tail. Without sorting, 1 2 1 has no adjacent duplicate and remains unchanged. Sorting changes original order, so only use this when that is acceptable.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
After unique on the sorted vector 2 2 5 5 5, what is size() before erasing the tail?
Turn the idea into code
Read n, a target, and n integers. Remove every target value, print the number removed, then print the remaining distinct values in ascending order. Use C++23 library operations and handle an empty result.
Give me a hint
std::erase removes target matches. Then sort, unique, and erase the tail after the returned iterator.
Show the explained solution
Removing matches is linear. Sorting groups duplicate values; unique keeps one in its logical prefix and the final erase changes the actual size. Overall time is O(1 + n log(n + 1)); stored input is O(n + 1), plus sorting implementation workspace.
// Complete C++23 program. Input: 0 <= n <= 200000, target, then n integers.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
int n = 0, target = 0;
std::cin >> n >> target;
std::vector<int> values(n);
for (int& x : values) std::cin >> x;
std::cout << std::erase(values, target) << '\n';
std::sort(values.begin(), values.end());
auto newEnd = std::unique(values.begin(), values.end());
values.erase(newEnd, values.end());
for (int i = 0; i < static_cast<int>(values.size()); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
}Your notes
Mark complete when you can explain it yourself.