STL Algorithms: Sorting, Lambdas, Comparators and Range Operations

34
0

STL-II: Algorithms, Lambdas, Comparators, and Range Operations

The Standard Template Library is not limited to containers. It also provides a broad collection of algorithms that work on iterator ranges. These algorithms can search, count, sort, transform, copy, merge, rotate, remove, and rearrange data without requiring each operation to be implemented manually.

Most STL algorithms operate on half-open ranges written as [first, last). The iterator first is included, while last marks the position immediately after the final element to process.

Predicates

A predicate is a callable that answers a yes-or-no question. In C++, this means it returns a Boolean value.

For example, a function that checks whether an integer is even is a predicate:

  • It returns true when the integer is divisible by two.

  • It returns false when the integer is odd.

Predicates are used extensively by algorithms such as count_if, find_if, all_of, remove_if, and copy_if.

Lambda Expressions

A lambda expression is a small callable written at the point where it is needed. It can be stored in a variable, passed directly to an algorithm, or invoked immediately.

The general structure is:

[capture](parameters) { body }

  • The capture list appears inside square brackets.

  • The parameters work like ordinary function parameters.

  • The body contains the operation performed by the lambda.

  • The compiler can usually infer the return type.

Lambda Declaration and Execution

Defining a lambda does not execute its body. The body runs only when the lambda is called. This is similar to declaring a normal function and calling it later.

Capturing Local Variables

A lambda cannot directly use a surrounding local variable unless that variable is captured.

  • [threshold] captures threshold by value.

  • [&threshold] captures it by reference.

  • [=] captures used local variables by value.

  • [&] captures used local variables by reference.

  • [] captures nothing.

A value capture stores a copy and is read-only inside the lambda unless the lambda is declared mutable. A reference capture refers to the original variable, so changing it inside the lambda changes the surrounding variable as well.

Predicates and General Lambdas

A predicate must return true or false, but a lambda can return any suitable type. For example, a lambda may return the square of an integer instead of answering a Boolean question.

Problem: Count Values Greater Than a Threshold

Given the array {4, 3, 8, 2, 10} and threshold 5, the values 8 and 10 satisfy the condition. Therefore, the answer is 2.

The count_if algorithm calls the predicate once for every element in the supplied range and counts how many calls return true.

#include <bits/stdc++.h>
using namespace std;
bool isEven(int number) {
return number % 2 == 0;
}
int main() {
int threshold = 5;
vector<int> values = {4, 3, 8, 2, 10};
auto greaterThanThreshold = [threshold](int number) {
return number > threshold;
};
cout << isEven(8) << '\n';
cout << greaterThanThreshold(10) << '\n';
auto square = [](int number) {
return number * number;
};
cout << square(5) << '\n';
int answer = count_if(
values.begin(),
values.end(),
greaterThanThreshold
);
cout << answer << '\n';
return 0;
}

The algorithm examines all n elements, so its time complexity is O(n). The lambda capture occupies constant additional space.

Sorting with STL

The sort algorithm rearranges elements in a random-access range. Vectors and arrays provide the required iterator capabilities.

Ascending Order

Calling sort(values.begin(), values.end()) sorts the entire vector in ascending order.

For {6, 4, 7, 10, 1}, the result is:

1 4 6 7 10

Descending Order

A third argument can define the ordering. The standard comparator greater<int>() places larger integers first:

sort(values.begin(), values.end(), greater<int>())

The result becomes:

10 7 6 4 1

Understanding Comparators

A sorting comparator receives two elements, conventionally named left and right. It must return true when left should appear before right.

For ascending integers, the required relationship is left < right. For descending integers, it is left > right.

A valid comparator should express a strict ordering. In particular, it must return false when the two values are equivalent. Comparators should therefore normally use < or >, not <= or >=.

Checking Whether a Range Is Sorted

is_sorted(first, last) checks ascending order by default. A comparator can be supplied to check a custom order:

  • is_sorted(begin, end) checks ascending order.

  • is_sorted(begin, end, greater<int>()) checks descending order.

The function returns a Boolean result and does not modify the range.

Custom Sorting with Multiple Conditions

Suppose every student is represented by a pair containing a name and marks. The required ordering is:

  • Higher marks must appear first.

  • If two students have equal marks, their names must be in ascending lexicographic order.

For example, if Ria and Aman both score 90, Aman appears first because "Aman" is lexicographically smaller than "Ria".

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<pair<string, int>> students = {
{"Ria", 90},
{"Aman", 90},
{"Dev", 80}
};
auto comparator = [](
const pair<string, int>& left,
const pair<string, int>& right
) {
if (left.second != right.second) {
return left.second > right.second;
}
return left.first < right.first;
};
sort(students.begin(), students.end(), comparator);
for (const auto& student : students) {
cout << student.first << ' '
<< student.second << '\n';
}
return 0;
}

The first condition decides the order whenever marks differ. The second condition is considered only when marks are equal.

Sorting n elements takes O(n log n) time. Every comparison takes constant time with respect to the number of students, although comparing strings may itself inspect multiple characters.

Stable Sorting

A stable sort preserves the original relative order of elements that compare as equivalent.

Suppose Ria appears before Aman in the original input and both have 90 marks. If the comparator considers only marks, stable_sort guarantees that Ria remains before Aman.

This differs from ordinary sort, which does not guarantee the relative order of equivalent elements.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<pair<string, int>> students = {
{"Ria", 90},
{"Aman", 90},
{"Dev", 80}
};
stable_sort(
students.begin(),
students.end(),
[](const auto& left, const auto& right) {
return left.second > right.second;
}
);
for (const auto& student : students) {
cout << student.first << ' ';
}
return 0;
}

Since equal marks make the comparator return false in both directions, those students are equivalent for sorting purposes. Their original order is therefore preserved.

Custom Ordering in a Priority Queue

A priority queue uses its comparator differently from sort. Its comparator indicates whether one element has lower priority than another. The element considered highest priority appears at top().

Suppose a task is represented as {priority, id} and must be processed according to these rules:

  • A larger priority value is processed first.

  • If priorities are equal, the smaller ID is processed first.

For tasks {2, 10}, {5, 8}, and {5, 3}, the processing order by ID is:

3 8 10

#include <bits/stdc++.h>
using namespace std;
int main() {
using Task = pair<int, int>;
auto lowerPriority = [](const Task& left, const Task& right) {
if (left.first != right.first) {
return left.first < right.first;
}
return left.second > right.second;
};
priority_queue<
Task,
vector<Task>,
decltype(lowerPriority)
> tasks(lowerPriority);
tasks.push({2, 10});
tasks.push({5, 8});
tasks.push({5, 3});
while (!tasks.empty()) {
Task current = tasks.top();
cout << "Priority: " << current.first
<< ", ID: " << current.second << '\n';
tasks.pop();
}
return 0;
}

The comparator returns true when the left task should have lower priority. A lower numerical priority loses to a higher one. When priorities match, a larger ID loses to a smaller ID.

Binary Search Algorithms

Binary-search algorithms require the supplied range to be sorted according to the same ordering used by the search.

binary_search(first, last, target) returns a Boolean indicating whether the target exists.

For {1, 7, 9, 10, 15}:

  • Searching for 7 returns true.

  • Searching for 17 returns false.

The search takes O(log n) comparisons on random-access ranges such as vectors and arrays.

lower_bound

lower_bound(first, last, target) returns an iterator to the first element that is greater than or equal to the target.

upper_bound

upper_bound(first, last, target) returns an iterator to the first element that is strictly greater than the target.

equal_range

equal_range(first, last, target) returns a pair of iterators:

  • The first iterator is the lower bound.

  • The second iterator is the upper bound.

Problem: Count Occurrences in a Sorted Array

For {1, 2, 2, 2, 5} and target 2, the lower bound points to the first 2, while the upper bound points to 5. The distance between these iterators is 3.

If the target is 3, both bounds point to 5. Their distance is zero, correctly indicating that 3 does not occur.

#include <bits/stdc++.h>
using namespace std;
int countOccurrences(const vector<int>& values, int target) {
auto first = lower_bound(values.begin(), values.end(), target);
auto afterLast = upper_bound(values.begin(), values.end(), target);
return static_cast<int>(distance(first, afterLast));
}
int main() {
vector<int> values = {1, 2, 2, 2, 5};
cout << binary_search(
values.begin(),
values.end(),
2
) << '\n';
cout << countOccurrences(values, 2) << '\n';
cout << countOccurrences(values, 3) << '\n';
auto bounds = equal_range(values.begin(), values.end(), 2);
cout << distance(bounds.first, bounds.second) << '\n';
return 0;
}

Both bound searches take O(log n). Two logarithmic searches still simplify to O(log n) because constant factors are ignored.

Minimum, Maximum, Swap, Search, and Count

Operations on Individual Values

  • min(first, second) returns the smaller value.

  • max(first, second) returns the larger value.

  • min({a, b, c}) finds the smallest value in an initializer list.

  • max({a, b, c}) finds the largest value in an initializer list.

  • swap(first, second) exchanges two values.

Operations on Ranges

  • min_element(first, last) returns an iterator to the minimum element.

  • max_element(first, last) returns an iterator to the maximum element.

  • minmax_element(first, last) returns both iterators as a pair.

  • find(first, last, value) returns the first matching position or last.

  • find_if(first, last, predicate) returns the first element satisfying a condition.

  • count(first, last, value) counts exact matches.

  • count_if(first, last, predicate) counts values satisfying a condition.

#include <bits/stdc++.h>
using namespace std;
int main() {
int first = 10;
int second = 15;
cout << min(first, second) << '\n';
cout << max(first, second) << '\n';
swap(first, second);
vector<int> values = {10, 7, 6, 1, 100, 6};
auto minimum = min_element(values.begin(), values.end());
auto maximum = max_element(values.begin(), values.end());
auto both = minmax_element(values.begin(), values.end());
cout << *minimum << ' ' << *maximum << '\n';
cout << *both.first << ' ' << *both.second << '\n';
auto firstEven = find_if(
values.begin(),
values.end(),
[](int value) {
return value % 2 == 0;
}
);
cout << *firstEven << '\n';
cout << count(values.begin(), values.end(), 6) << '\n';
return 0;
}

Before dereferencing the result of find or find_if, compare it with the range’s end iterator. If no matching element exists, the returned iterator equals end().

These range algorithms perform a linear scan and therefore take O(n) time.

Checking Conditions Across an Entire Range

The algorithms all_of, any_of, and none_of apply a predicate across a range and return a Boolean result.

all_of

all_of returns true only when every element satisfies the predicate. If the range contains {6, 7, 8, 10, 12}, checking whether every value is even returns false because 7 is odd.

any_of

any_of returns true when at least one element satisfies the predicate.

none_of

none_of returns true when no element satisfies the predicate. For an all-even array, checking whether none of its values are odd returns true.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> values = {6, 8, 10, 12};
auto isEven = [](int value) {
return value % 2 == 0;
};
auto isOdd = [](int value) {
return value % 2 != 0;
};
bool everyValueIsEven =
all_of(values.begin(), values.end(), isEven);
bool atLeastOneValueIsEven =
any_of(values.begin(), values.end(), isEven);
bool noValueIsOdd =
none_of(values.begin(), values.end(), isOdd);
cout << everyValueIsEven << ' '
<< atLeastOneValueIsEven << ' '
<< noValueIsOdd << '\n';
}

These algorithms may stop early once the final answer is known. For example, all_of stops at the first failure. Their worst-case time complexity remains O(n).

Numeric Utilities and Initialization

iota

iota(first, last, startingValue) fills a range with consecutive values.

If a vector of length five is filled starting from 70, it becomes:

70 71 72 73 74

fill

fill(first, last, value) assigns the same value throughout a range. Filling a five-element vector with 100 produces:

100 100 100 100 100

partial_sum

partial_sum computes running totals. For {6, 7, 1, 10, 12}, the result is:

6 13 14 24 36

The destination must have enough valid positions unless an insertion iterator such as back_inserter is used.

adjacent_difference

adjacent_difference keeps the first value and then stores the difference between every value and its predecessor.

For {6, 7, 1, 10, 12}, the result is:

6 1 -6 9 2

gcd and lcm

gcd(a, b) returns the greatest positive integer dividing both numbers. lcm(a, b) returns their least common multiple.

For 10 and 15:

  • The greatest common divisor is 5.

  • The least common multiple is 30.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> consecutive(5);
iota(consecutive.begin(), consecutive.end(), 70);
vector<int> repeated(5);
fill(repeated.begin(), repeated.end(), 100);
vector<int> values = {6, 7, 1, 10, 12};
vector<int> runningSum(values.size());
vector<int> differences(values.size());
partial_sum(
values.begin(),
values.end(),
runningSum.begin()
);
adjacent_difference(
values.begin(),
values.end(),
differences.begin()
);
cout << gcd(10, 15) << '\n';
cout << lcm(10, 15) << '\n';
for (int value : runningSum) {
cout << value << ' ';
}
return 0;
}

Reversing and Rotating Ranges

reverse

reverse(first, last) reverses the specified half-open range. Supplying the entire vector changes {10, 20, 30, 40, 50} into:

50 40 30 20 10

A smaller subrange can also be reversed without changing the elements outside that range.

rotate

rotate(first, middle, last) divides a range into two parts:

  • [first, middle)

  • [middle, last)

The second part is moved before the first while preserving the internal order of both parts.

For {10, 20, 30, 40, 50}, rotating with middle = begin + 2 produces:

30 40 50 10 20

Problem: Rotate an Array Left by k Positions

#include <bits/stdc++.h>
using namespace std;
void rotateLeft(vector<int>& values, int positions) {
if (values.empty()) {
return;
}
positions %= static_cast<int>(values.size());
rotate(
values.begin(),
values.begin() + positions,
values.end()
);
}
int main() {
vector<int> values = {10, 20, 30, 40, 50};
rotateLeft(values, 2);
for (int value : values) {
cout << value << ' ';
}
}

Reducing positions modulo the size handles values greater than the array length. Rotation takes O(n) time.

Removing Elements with the Erase-Remove Idiom

The generic remove algorithm does not reduce a vector’s physical size. Instead, it moves retained elements toward the beginning and returns an iterator representing the new logical end.

For {10, 20, 30, 20, 40}, removing 20 places 10, 30, 40 at the beginning. The vector still has five elements until its trailing range is erased.

Removing Exact Values

The complete erase-remove pattern is:

values.erase(remove(values.begin(), values.end(), target), values.end())

Removing Values by Condition

remove_if applies the same logical removal process using a predicate. For example, negative values can be removed from {5, 6, -1, 2, -8, 10}, leaving {5, 6, 2, 10}.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> values = {10, 20, 30, 20, 40};
auto newEnd = remove(
values.begin(),
values.end(),
20
);
values.erase(newEnd, values.end());
vector<int> mixed = {5, 6, -1, 2, -8, 10};
mixed.erase(
remove_if(
mixed.begin(),
mixed.end(),
[](int value) {
return value < 0;
}
),
mixed.end()
);
return 0;
}

Both remove and remove_if preserve the relative order of retained elements. Their time complexity is O(n).

Removing Adjacent Duplicates with unique

unique(first, last) removes consecutive duplicates logically and returns a new logical end. Like remove, it does not shrink a vector by itself.

For the sorted sequence {1, 1, 2, 2, 2, 3, 3}, the retained logical range becomes:

1 2 3

However, unique only compares adjacent elements. For a sequence such as {1, 1, 3, 2, 2, 1, 1, 3, 2}, separated occurrences of the same value remain.

Obtaining All Distinct Values

To obtain every distinct value in increasing order:

  • Sort the range so equal values become adjacent.

  • Apply unique.

  • Erase the range from the returned logical end to the physical end.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> values = {3, 1, 2, 1, 3, 2, 2};
sort(values.begin(), values.end());
auto newEnd = unique(values.begin(), values.end());
values.erase(newEnd, values.end());
for (int value : values) {
cout << value << ' ';
}
return 0;
}

Sorting dominates the complexity, so the complete operation takes O(n log n).

Copying, Transforming, and Replacing

Copying an Entire Vector

A complete vector can be copied directly with assignment:

vector<int> copied = original;

copy

copy(first, last, destination) copies a range into an existing destination beginning at the supplied output iterator.

If the destination is a vector iterator, the vector must already contain enough elements. Merely reserving capacity is not sufficient because algorithms writing through begin() require constructed destination elements.

back_inserter

back_inserter(container) produces an output iterator that calls push_back for every assigned value. It is appropriate when the destination begins empty or should grow automatically.

copy_if

copy_if copies only elements for which a predicate returns true. From {10, 20, 31, 40, 51}, an even-number predicate copies {10, 20, 40}.

transform

transform computes a new value for every element and writes the results to a destination. A squaring lambda converts {10, 20, 30} into {100, 400, 900}.

replace and replace_if

  • replace replaces every occurrence of an exact value.

  • replace_if replaces every value satisfying a predicate.

For example, every occurrence of 30 can be replaced with 100, or every even value can be replaced with -1.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> values = {10, 20, 31, 40, 51};
vector<int> firstThree(3);
copy(
values.begin(),
values.begin() + 3,
firstThree.begin()
);
vector<int> evenValues;
copy_if(
values.begin(),
values.end(),
back_inserter(evenValues),
[](int value) {
return value % 2 == 0;
}
);
vector<int> squares;
transform(
values.begin(),
values.end(),
back_inserter(squares),
[](int value) {
return value * value;
}
);
replace(values.begin(), values.end(), 31, 100);
replace_if(
values.begin(),
values.end(),
[](int value) {
return value % 2 == 0;
},
-1
);
return 0;
}

These algorithms process each element in the supplied range at most once, giving them O(n) time complexity.

Merging Sorted Ranges

merge combines two sorted ranges into one sorted output while preserving all occurrences. Both input ranges must already be sorted according to the same ordering.

For example:

  • First range: {1, 3, 3}

  • Second range: {2, 3, 5}

  • Merged result: {1, 2, 3, 3, 3, 5}

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> first = {1, 3, 3};
vector<int> second = {2, 3, 5};
vector<int> result;
merge(
first.begin(),
first.end(),
second.begin(),
second.end(),
back_inserter(result)
);
for (int value : result) {
cout << value << ' ';
}
return 0;
}

If the first range has n elements and the second has m, merging takes O(n + m) time.

Set Operations on Sorted Ranges

STL set algorithms operate on sorted ranges. They are not restricted to set containers; sorted vectors and arrays are valid inputs.

Consider:

  • First range: {1, 2, 2, 4}

  • Second range: {2, 3, 4}

set_union

The union contains values present in either range. Multiplicity in the result is the maximum multiplicity found in either input.

Result: {1, 2, 2, 3, 4}

set_intersection

The intersection contains values present in both ranges. Multiplicity is the minimum multiplicity found in either input.

Result: {2, 4}

set_difference

set_difference(first, second) contains occurrences from the first range that remain after matching occurrences from the second are removed.

Result: {1, 2}

set_symmetric_difference

The symmetric difference contains unmatched occurrences from both ranges.

Result: {1, 2, 3}

includes

includes checks whether the first sorted range contains every value and required occurrence from the second sorted range.

  • {1, 2, 4} includes {1, 4}.

  • {1, 2, 4} does not include {1, 3, 4}.

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> first = {1, 2, 2, 4};
vector<int> second = {2, 3, 4};
vector<int> unionResult;
vector<int> intersectionResult;
vector<int> differenceResult;
vector<int> symmetricResult;
set_union(
first.begin(), first.end(),
second.begin(), second.end(),
back_inserter(unionResult)
);
set_intersection(
first.begin(), first.end(),
second.begin(), second.end(),
back_inserter(intersectionResult)
);
set_difference(
first.begin(), first.end(),
second.begin(), second.end(),
back_inserter(differenceResult)
);
set_symmetric_difference(
first.begin(), first.end(),
second.begin(), second.end(),
back_inserter(symmetricResult)
);
vector<int> required = {1, 4};
bool contained = includes(
first.begin(), first.end(),
required.begin(), required.end()
);
cout << contained << '\n';
}

Each operation advances through the two sorted ranges, giving a time complexity of O(n + m).

Permutations

A permutation is an arrangement of a collection’s elements. Three distinct values have 3! = 6 permutations.

The lexicographic permutations of {1, 2, 3} are:

  • 1 2 3

  • 1 3 2

  • 2 1 3

  • 2 3 1

  • 3 1 2

  • 3 2 1

next_permutation

next_permutation(first, last) rearranges a range into its next lexicographically greater permutation.

It returns true when such a permutation exists. If the current arrangement is the greatest permutation, it rearranges the range into the smallest permutation and returns false.

Therefore, calling it on {3, 2, 1} changes the sequence to {1, 2, 3} and returns false.

prev_permutation

prev_permutation performs the reverse operation. It moves to the immediately preceding lexicographic arrangement.

Problem: Print All Distinct Permutations

To print all distinct permutations in lexicographic order:

  • Sort the values to obtain the smallest arrangement.

  • Print the current arrangement.

  • Repeatedly call next_permutation until it returns false.

Starting from sorted order is essential. Otherwise, permutations appearing before the initial arrangement would not be printed.

#include <bits/stdc++.h>
using namespace std;
int main() {
int size;
cin >> size;
vector<int> values(size);
for (int& value : values) {
cin >> value;
}
sort(values.begin(), values.end());
do {
for (int value : values) {
cout << value << ' ';
}
cout << '\n';
} while (next_permutation(values.begin(), values.end()));
return 0;
}

Repeated values are handled correctly. Starting from sorted order and using next_permutation generates each distinct arrangement once.

If there are n distinct elements, there are n! permutations. Printing each permutation takes O(n), so generating and printing all of them takes O(n × n!) time.

About bitset

bitset represents a fixed number of bits and supports efficient bitwise operations. Its meaningful use depends on understanding binary representation, bitwise operators, masks, and bit manipulation. It is therefore best studied together with those concepts rather than as an isolated container.

Algorithm Complexity Summary

  • count_if, find, and find_if: O(n)

  • all_of, any_of, and none_of: worst-case O(n)

  • sort and stable_sort: O(n log n)

  • binary_search, lower_bound, and upper_bound on random-access ranges: O(log n)

  • min_element, max_element, and minmax_element: O(n)

  • iota, fill, partial_sum, and adjacent_difference: O(n)

  • reverse, rotate, remove, and unique: O(n)

  • copy, copy_if, transform, and replace: O(n)

  • merge and sorted-range set operations: O(n + m)

  • One next_permutation operation: O(n)

Key Takeaways

  • Predicates express Boolean conditions that algorithms can reuse.

  • Lambdas make small callables available exactly where they are needed.

  • Capture lists control whether surrounding variables are unavailable, copied, or referenced.

  • Comparators define ordering and must provide a strict, consistent relationship.

  • Stable sorting preserves the original order of equivalent elements.

  • Binary-search algorithms require sorted input.

  • Algorithms using output iterators require valid destination storage or an insertion iterator.

  • remove and unique produce logical ends; they do not shrink vectors directly.

  • Merge and set algorithms require sorted input ranges.

  • Sorting before repeated next_permutation calls generates all distinct permutations in lexicographic order.

The STL algorithm library is most powerful when ranges, predicates, comparators, iterators, and complexity are understood together. These tools make solutions shorter, but more importantly, they encode well-tested operations with clear behavior and predictable performance.

C++

Read Similar Blogs

C++

STL Foundations: Containers, Iterators, Algorithms and Time Complexity

cpp #include using namespace std; int linearSearch(int values[], int size, int target) { for (int index = 0; index nested = {10, {20, 30}}; cout data = {8, 'R', 9.8, "Raj"}; cout (data) (data) > si...

15
C++

Recursion Problem Solving II: Array Traversal, Sorting Check and Reversal

Recursion Problem Solving - II Arrays are naturally suited to recursive processing because an array range can be divided into a current element and a smaller remaining range. A recursive function c...

1.8k
C++

Recursion Problem Solving I: Power, Digit Sum and Number Reversal

Recursion Problem Solving - I Recursive problem solving begins by defining exactly what a function should return. The current problem is then expressed in terms of the same function applied to a sm...

1.6k
Comments0