Using STL Algorithms Effectively

STL algorithms do not directly add or subtract elements from their argument sequences, so the sequence size is unchanged by the algorithm call alone.

Programming

A Prediction Before the Explanation

Standard-library algorithms are powerful, and it is tempting to treat them as a drop-in replacement for any loop. A common first guess is that an algorithm that seems to remove things, such as one that removes matching values, must also make the sequence shorter. That belief leads to a specific kind of error: the programmer expects the algorithm to change the shape of the data, and then writes the rest of the program around a size or contents that never changed.

Keep that first guess in mind. Imagine a sequence of five integers, where two of the values are zeros, and a call to the removal algorithm that removes every zero. Before reading on, ask yourself how many elements the sequence holds after that call returns. The rest of this article explains the answer and the reasoning behind it.

Watching a Vector Keep Its Size

The program below creates a vector of five integers, then calls std::remove to remove every zero. The call is made on its own, without any erase, so it shows what the algorithm does by itself. After the call, the program prints the size of the vector.

cpp

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

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    std::remove(v.begin(), v.end(), 0);
    std::cout << v.size() << "\n";
}

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

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    std::remove(v.begin(), v.end(), 0);
    std::cout << v.size() << "\n";
}

Output

Notes on the code

std::remove takes a pair of iterators marking the range to process and the value to remove
The return value of std::remove is ignored here, so the program never uses the new end position
v.size() still reports five because the algorithm does not delete any elements

Output

The kept values have been gathered at the front, while the two trailing positions still exist but no longer hold a meaningful value. The element count is five in both states.

Read the diagram from left to right. The before column holds the original arrangement, and the after column holds the arrangement once the algorithm has finished. Only the order of values changed: the kept values 1, 2 and 3 now sit at the front. The number of positions is still five, so the size is still five. The algorithm had no way to delete the two trailing positions, so they remain in the sequence with values your program should not rely on.

Rearranging Values Within a Fixed Range

An algorithm works on the values inside the range it is given, not on the sequence's list of elements as a whole. The range is described by a start position and an end position. Within that range, the algorithm can move values around, overwrite them, or select which ones to keep. It cannot change how many positions the range contains, and it has no way to remove the positions of a container.

For a removal algorithm such as std::remove, the work has two parts. It moves the values it keeps toward the front of the range, and it returns an iterator that marks where the kept values end. Everything from that returned position up to the real end of the sequence still exists, but it is no longer part of the useful result. The index map below shows this for the same five values.

After the call, indexes 0 to 2 hold the kept values in their original relative order. The returned iterator points to index 3, and indexes 3 and 4 hold values the program should not rely on.

Shrinking a Sequence in Two Steps

If you want the sequence itself to end up shorter, the change has to be made through the sequence, not through the algorithm. The usual pattern has two separate steps, and each has a clear job. First, call the algorithm and keep the iterator it returns as the new end of the useful values. Second, ask the sequence to erase everything from that point to its real end. The algorithm rearranges the values, and the erase call changes the size.

cpp

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

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    auto new_end = std::remove(v.begin(), v.end(), 0);
    std::cout << v.size() << "\n";
    v.erase(new_end, v.end());
    std::cout << v.size() << "\n";
}

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

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    auto new_end = std::remove(v.begin(), v.end(), 0);
    std::cout << v.size() << "\n";
    v.erase(new_end, v.end());
    std::cout << v.size() << "\n";
}

Output

5
3

Notes on the code

The returned iterator is stored in new_end before anything else happens
The first size report is still five, because only the arrangement has changed
The erase call removes the trailing positions from new_end to the real end, so the second size report is three

Output

5
3

Worked example

Tracing the two-step shrink

A vector holds the values 4, 0, 7, 0 and you want to remove every zero so that the vector ends up holding only the useful values.

1
Call the algorithm
std::remove moves the kept values 4 and 7 to the front, giving 4, 7 in the first two positions, and returns an iterator to position 2.
2
Check the size
The vector still holds four positions. The call has not changed the size.
3
Erase the trailing positions
Calling erase from the returned iterator to the end removes positions 2 and 3, which leaves the sequence with the two useful values.
4
Confirm the new size
The vector now holds two elements, and the size changed only because the erase call was made.

Result

The vector holds 4 and 7, with a size of 2. The algorithm did the rearranging and the erase did the shrinking.

Predicates Change the Rule, Not the Size Rule

A predicate is a function object that an algorithm can be given. The guidelines say to use predicates and other function objects to give standard algorithms a wider range of meanings. The same standard algorithm can do different work depending on the predicate it receives. The algorithm supplies the general process, and the predicate supplies the rule the process applies to each element.

cpp

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    auto new_end = std::remove_if(v.begin(), v.end(),
        [](int x) { return x == 0; });
    v.erase(new_end, v.end());
}

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    auto new_end = std::remove_if(v.begin(), v.end(),
        [](int x) { return x == 0; });
    v.erase(new_end, v.end());
}

Notes on the code

The lambda [](int x) is the predicate: it takes one element and decides whether that element matches
The body return x == 0 produces a bool, which is what the algorithm needs to decide what to move
The predicate reads x but does not change it, and it does not keep any running state between calls

Notice what the predicate does not change. Even with a different predicate, the algorithm still cannot add or remove positions. A predicate chooses which values the algorithm treats as matches, but the erase step remains the only way to shorten the sequence.

Choosing Between a Loop and a Named Algorithm

The guidelines ask you to know your standard-library algorithms and to prefer them to hand-crafted loops. They also suggest a habit: when you write a loop, consider whether it could be expressed as a general algorithm. This does not mean every loop must become an algorithm. It means the question is asked first, so a standard algorithm is considered before you write the loop by hand.

1
Describe the loop's job in one phrase, such as filter matching values, transform each value, or search for a value.
2
Ask whether a standard algorithm already performs that job, and read its description so you know what it changes and what it leaves alone.
3
If the algorithm exists, check whether a predicate can supply the rule the loop was checking.
4
Remember the size rule: if the loop was meant to shrink or grow the sequence, plan a separate erase or insert step rather than expecting the algorithm to do it.
5
Only write the loop by hand when no standard algorithm fits the job cleanly.

When Iterator Pairs Become Tedious

Many standard algorithms are described by a pair of iterators: one marks the start of the range and one marks the end. This style is precise, because the range is stated exactly. The code becomes repetitive, however, when the same pair must be written again and again. The guideline says that when the pair-of-iterators style becomes tedious, you should introduce a container/range algorithm.

cpp

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 2};
    std::sort(v.begin(), v.end());
}

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 2};
    std::sort(v.begin(), v.end());
}

Notes on the code

The pair style names the start with v.begin() and the end with v.end() at every call
A container/range version lets you pass the sequence as a whole, so these positions do not have to be spelled out each time

Question	Iterator-pair style	Container/range style
What the call names	A start position and an end position	The sequence as a whole
Precision of the range	Stated explicitly at every call	Implied by the sequence passed in
When it fits best	Sub-ranges, or when the start and end must differ from the whole sequence	Repeated calls over whole sequences
Tedium at scale	Pair repeated again and again becomes tedious	Little repetition of positions

Two calling styles for the same kind of algorithm

Common Mistakes With Algorithm Sizes

Common mistake
Assuming that std::remove shrinks the vector
What it looks like
std::remove(v.begin(), v.end(), 0); followed by a read of v.size() as if it counted only the kept values.
Why it fails
The algorithm does not directly add or subtract elements, so the size is the same after the call.
Do this instead
Store the returned iterator and erase from it to the end, then use the size only after that erase.
Common mistake
Reading past the returned end of the useful values
What it looks like
Looping from the start to v.end() after a removal, and treating the trailing positions as valid results.
Why it fails
The trailing positions still exist but hold values the program should not rely on.
Do this instead
Use the returned iterator as the boundary of the useful values, or erase the trailing positions.
Common mistake
Expecting a predicate to modify the elements it checks
What it looks like
A predicate that changes its argument to mark it, then relies on that change later.
Why it fails
A predicate must be a pure check that does not modify its argument or hold hidden state.
Do this instead
Keep the predicate a read-only test that returns a bool for each element.
Common mistake
Writing a hand-made loop for a filter without first checking whether a standard algorithm already performs that job

Trace the Sequence Yourself

What do you think happens?

A vector holds the values 4, 0, 7. A call to std::remove removes every zero, but no erase follows. What is the size of the vector after the call returns?

Reveal answer

Answer:

The algorithm does not directly add or subtract elements, so the size stays at three even though the kept values 4 and 7 now sit at the front. Only an erase from the returned iterator would make the size two.

MEDIUM

A vector holds the eight values 5, 0, 8, 0, 6, 0, 2, 9. Call std::remove to remove every zero, store the returned iterator, and state the size of the vector right after the call. Then erase from the returned iterator to the end and state the new size. Explain in one sentence which of the two steps changed the size.

Hints

The kept values are 5, 8, 6, 2 and 9, so count them before writing any answer.
The size immediately after the algorithm call is still eight.
Only the erase call changes the number of positions.

Your attempt (not saved)

Key Takeaways

STL algorithms do not directly add or subtract elements from their argument sequences, so the element count is the same after the call.
An algorithm rearranges or selects values within the range it is given and returns an iterator marking where the useful values end, leaving the trailing positions in place.
To shrink a sequence, call the algorithm, keep the returned iterator, and erase from that point to the real end of the sequence.
A predicate customizes what an algorithm matches, but it must be a pure check that returns a bool and does not modify its argument or hold hidden state.
Prefer a standard algorithm to a hand-written loop, and switch to a container/range version when repeated iterator pairs become tedious.

Related concepts

Iterators and Ranges in the Standard Library

More concepts starting with U

A Prediction Before the Explanation

Watching a Vector Keep Its Size

Rearranging Values Within a Fixed Range

Shrinking a Sequence in Two Steps

Predicates Change the Rule, Not the Size Rule

Choosing Between a Loop and a Named Algorithm

When Iterator Pairs Become Tedious

Common Mistakes With Algorithm Sizes

Trace the Sequence Yourself

Key Takeaways

Related Topics

Related concepts