next_permutation, rotate & reverse
Scenario
An interviewer asks you to write a function that takes an array like `[1, 2, 3, 4, 5]` and shifts it left by 2 spaces, resulting in `[3, 4, 5, 1, 2]`. You start writing a temporary array, a loop, and some complex modulo math.
Is there a single STL function that does this in-place with zero extra memory?
Mental model
The `<algorithm>` header is a Swiss Army Knife. Instead of writing custom loops to flip, shift, or permute data, you just pull out the exact specialized tool for the job. It's faster, bug-free, and instantly communicates your intent to other engineers.
C++ provides highly optimized in-place algorithms for sequence manipulation. `std::reverse` flips a sequence. `std::rotate` shifts elements circularly. `std::next_permutation` is a "magic" algorithm that rearranges elements into their next lexicographically greater permutation, making brute-force combinatorics trivial.
Explanation
**1. std::reverse**
`std::reverse(begin, end)` flips the elements in the range in O(N) time. Simple, but incredibly useful when combined with other algorithms (like sorting in descending order, though `rbegin` is better for that).
**2. std::rotate**
`std::rotate(first, new_first, last)` performs a circular shift. The element at `new_first` becomes the new beginning of the sequence. It works in-place (O(1) auxiliary space) and takes O(N) time. It's notoriously tricky to implement manually without bugs, so always use the STL version.
**3. std::next_permutation**
`std::next_permutation(begin, end)` modifies the array into the next lexicographical permutation and returns `true`. If the array is sorted in descending order (the absolute last permutation), it wraps around to ascending order and returns `false`. This allows you to generate all possible permutations with a simple `do { ... } while(next_permutation(...))` loop.
**Real-world Engineering:**
These tools replace hundreds of lines of boilerplate. `std::rotate` is used in text editors to shift blocks of text or in UI carousels. `std::next_permutation` is widely used in competitive programming and operations research to brute-force small Traveling Salesperson variations without writing complex recursive backtracking.
Code examples
Generating all permutations
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3};
// vec MUST be sorted initially to guarantee we hit all permutations
std::sort(vec.begin(), vec.end());
int count = 0;
do {
count++;
// The vector is modified in-place to the next permutation
} while (std::next_permutation(vec.begin(), vec.end()));
std::cout << "Total permutations: " << count << '\n'; // Prints 6
return 0;
}This loop generates all 3! (6) permutations without any recursion, manual swapping, or extra memory allocation.
Left Rotation
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// We want the element at index 2 (the '3') to become the new front.
// v.begin() + 2 is the 'new_first' iterator.
std::rotate(v.begin(), v.begin() + 2, v.end());
// v is now {3, 4, 5, 1, 2}
return 0;
}`std::rotate` handles the complex block-swapping logic internally, ensuring O(N) speed with zero dynamic memory allocation.
Key points
- No raw loops: If you are writing a `for` loop to shift or flip an array, stop and use `<algorithm>`. It is faster and safer.
- Sort before permuting: Always `std::sort` your container before throwing it into a `do-while` loop with `next_permutation`.
Common mistakes
- Using next_permutation on an unsorted array: `next_permutation` only generates permutations *lexicographically greater* than the current one. If you pass it `[3, 2, 1]`, it instantly returns false because that is the highest possible permutation. You must always `std::sort` the array first if you want to generate *all* permutations.
Recall questions
- What does the `new_first` parameter (the middle argument) in `std::rotate` specify?
- What is the return value of `std::next_permutation` and when does it return false?
- What is the time complexity of `std::reverse`?
Questions & answers
A developer writes a `while(std::next_permutation(...))` loop to test all possible combinations of a 5-element array. The array starts as `[5, 1, 4, 2, 3]`. Will the loop test all 120 (5!) permutations? Why?
No. The loop will only test the permutations lexicographically greater than `[5, 1, 4, 2, 3]`. Because it wasn't sorted ascending first, a large chunk of permutations (anything starting with 1, 2, 3, or 4) will be completely skipped.
Approach: Understand the lexicographical prerequisite for permutation generation.
How can you use `std::rotate` to move the first element of a vector to the very end while shifting everything else left?
You call `std::rotate(vec.begin(), vec.begin() + 1, vec.end())`. The element at `vec.begin() + 1` becomes the new first element, which effectively shifts the old first element to the back.
Approach: Understand the iterator boundaries required to perform basic shifts.