STL Algorithms
1. Introduction
1.1 Brief overview of the algorithms provided by STL
The Standard Template Library (STL) is a rich assembly of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures. When we talk about the algorithms in STL, we're referring to a collection of functions specially designed to be used on a range of elements. These algorithms encompass a range of operations, including searching, sorting, modifying, and more.
1.2 Understanding the importance of iterators in STL algorithms:
Iterators are a fundamental concept in C++. They act like pointers and allow us to access elements within containers without worrying about the underlying structure of the container. Almost all STL algorithms require iterators as arguments, allowing these algorithms to be used with any STL container that supports the required iterator type. Think of iterators as a bridge between containers and algorithms. Without them, the generality and versatility of STL algorithms would be drastically reduced.
2. Non-modifying Sequence Operations
These are algorithms that inspect or read the content of sequences without changing them.
for_each: Apply a function to a range.
This algorithm takes in two iterators representing a range and a unary function, and it applies this function to each element in the range.
std::vector<int> nums = {1, 2, 3, 4};
std::for_each(nums.begin(), nums.end(), [](int &n) { std::cout << n << " "; });
count, count_if: Count occurrences.
count returns the number of elements that are equal to a specified value, while count_if counts elements that satisfy a predicate.
int n = std::count(nums.begin(), nums.end(), 2); // Counts occurrences of 2
int m = std::count_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; }); // Counts even numbers
find, find_if, find_if_not: Search elements.
find searches for an element, find_if searches based on a predicate, and find_if_not searches for elements that don't satisfy a predicate.
auto it = std::find(nums.begin(), nums.end(), 3); // Finds 3 in nums
all_of, any_of, none_of: Check elements by condition.
These algorithms check elements based on a predicate. For instance, all_of returns true if all elements satisfy the predicate.
bool all_even = std::all_of(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; });
mismatch: Find the first mismatching pair.
Compares two sequences and returns a pair of iterators pointing to the first mismatching elements.
std::vector<int> nums2 = {1, 2, 4, 4};
auto mm = std::mismatch(nums.begin(), nums.end(), nums2.begin());
equal: Compare range with another.
Checks if two sequences are the same.
bool same = std::equal(nums.begin(), nums.end(), nums2.begin());
search: Search range for a subsequence.
Searches for the first occurrence of the subsequence in the range.
std::vector<int> pattern = {2, 3};
auto it2 = std::search(nums.begin(), nums.end(), pattern.begin(), pattern.end());
find_end: Find last subsequence.
Similar to search, but finds the last occurrence of the subsequence.
auto it3 = std::find_end(nums.begin(), nums.end(), pattern.begin(), pattern.end());
adjacent_find: Find adjacent matching elements.
Returns an iterator pointing to the first of the two duplicate adjacent elements.
std::vector<int> nums3 = {1, 2, 2, 3};
auto it4 = std::adjacent_find(nums3.begin(), nums3.end());
3. Modifying Sequence Operations
These are algorithms that directly modify the content of sequences based on certain conditions or patterns.
copy, copy_if: Copy elements.
copy duplicates elements from one range to another, while copy_if does the same but only for elements satisfying a certain predicate.
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2(5);
std::copy(v1.begin(), v1.end(), v2.begin());
std::vector<int> v3(5);
std::copy_if(v1.begin(), v1.end(), v3.begin(), [](int x){ return x % 2 == 0; }); // Copies even numbers
move: Move elements.
Transfers elements from one range to another.
std::vector<std::string> strings1 = {"a", "b", "c"};
std::vector<std::string> strings2(3);
std::move(strings1.begin(), strings1.end(), strings2.begin());
swap, swap_ranges: Swap content.
swap exchanges the content of two elements, while swap_ranges swaps two ranges.
int a = 5, b = 10;
std::swap(a, b);
std::swap_ranges(v1.begin(), v1.end(), v2.begin());
fill, fill_n: Fill sequence.
Sets all elements in a range to a particular value.
std::fill(v1.begin(), v1.end(), 0); // Fills entire vector with zeros
std::fill_n(v1.begin(), 3, 7); // Fills first three elements with sevens
transform: Apply a function.
Applies a given function to a range and stores the result in another range.
std::transform(v1.begin(), v1.end(), v1.begin(), [](int x){ return x * 2; }); // Doubles each element
generate, generate_n: Assign value generated by function.
Fills a range with values produced by a generator function.
int current = 1;
std::generate(v1.begin(), v1.end(), [¤t](){ return current++; }); // Fills with sequence 1, 2, ...
std::generate_n(v1.begin(), 3, [¤t](){ return current += 2; }); // Fills first three elements with values 3, 5, 7
remove, remove_if: Remove elements.
Removes certain elements from a range. This doesn't change the size of the container but returns an iterator pointing past the last valid element. This 2-step process is a common idiom in the STL.
auto it = std::remove(v1.begin(), v1.end(), 3); // Removes all threes
v1.erase(it, v1.end());
auto it2 = std::remove_if(v1.begin(), v1.end(), [](int x){ return x % 2 == 0; }); // Removes even numbers
v1.erase(it2, v1.end());
In C++20, we can use std::erase or std::erase_if to remove elements in a single line:
std::erase(v1, 3); // Removes all threes
std::erase_if(v1, [](int x){ return x % 2 == 0; }); // Removes even numbers
replace, replace_if: Replace elements.
Substitutes elements in a range.
std::replace(v1.begin(), v1.end(), 2, 8); // Replaces all twos with eights
std::replace_if(v1.begin(), v1.end(), [](int x){ return x < 5; }, 0); // Replaces numbers less than 5 with zero
reverse: Reverse elements.
Reverses the order of elements in a range.
std::reverse(v1.begin(), v1.end());
rotate: Rotate elements left.
Rotates the elements in the range to the left.
std::rotate(v1.begin(), v1.begin() + 2, v1.end()); // Rotates left by two positions
shuffle: Randomly rearrange elements.
Rearranges the elements randomly.
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v1.begin(), v1.end(), g);
4. Sorting and Related Operations
These are algorithms that either help order elements in a specific manner or exploit the ordered nature of sequences for certain operations.
sort: Sort elements in a range.
Sorts elements in ascending order by default.
std::vector<int> v = {5, 2, 9, 1};
std::sort(v.begin(), v.end()); // v: {1, 2, 5, 9}
partial_sort: Partially sort elements.
Sorts the first N elements in ascending order.
std::vector<int> v = {9, 7, 5, 3, 1, 8, 6, 4, 2};
std::partial_sort(v.begin(), v.begin() + 3, v.end()); // v: {1, 2, 3, ...}
nth_element: Sort nth element.
Ensures the nth element is in the position it would be in a sorted range.
std::nth_element(v.begin(), v.begin() + 4, v.end()); // The fifth element is in its sorted position
merge: Merge sorted sequences.
Merges two sorted sequences into one.
std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> result(6);
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin()); // result: {1, 2, 3, 4, 5, 6}
inplace_merge: Merge consecutive sorted ranges.
Merges two consecutive sorted ranges within a single sequence.
std::vector<int> v = {1, 3, 5, 2, 4, 6};
std::inplace_merge(v.begin(), v.begin() + 3, v.end()); // v: {1, 2, 3, 4, 5, 6}
partition: Partition by predicate.
Partitions the sequence such that elements satisfying a predicate come before those that don't.
std::partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // Evens first, then odds
stable_partition: Partition preserving order.
Similar to partition, but maintains the relative order of equivalent elements.
std::stable_partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // Evens first in their original order, then odds
binary_search: Binary search on sorted range.
Returns true if an element exists in the sorted range, false otherwise.
bool exists = std::binary_search(v.begin(), v.end(), 4); // true if 4 is in the vector
lower_bound, upper_bound: Binary search returning iterator.
lower_bound returns an iterator to the first element not less than the given value. upper_bound returns an iterator to the first element greater than the value.
auto low = std::lower_bound(v.begin(), v.end(), 4); // Points to first element >= 4
auto up = std::upper_bound(v.begin(), v.end(), 4); // Points to first element > 4
5. Numeric Algorithms
Numeric algorithms are specifically designed to operate on sequences of numbers, offering a range of functions from basic arithmetic operations to more complex calculations.
iota: Store increasing sequence.
Fills a range with a sequence of increasing values.
std::vector<int> v(5);
std::iota(v.begin(), v.end(), 10); // v: {10, 11, 12, 13, 14}
accumulate: Accumulate values.
Computes the sum of a range's elements and can also accumulate results with custom operations.
std::vector<int> nums = {1, 2, 3, 4, 5};
int sum = std::accumulate(nums.begin(), nums.end(), 0); // sum: 15
// With custom operation
int product = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>());
// product: 120 (because 1*2*3*4*5)
inner_product: Inner product of two sequences.
Computes the dot product of two sequences.
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
int result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0); // result: 32 (because 1*4 + 2*5 + 3*6)
adjacent_difference: Compute adjacent difference.
Computes the differences between adjacent elements in a sequence.
std::vector<int> v = {1, 2, 4, 7, 11};
std::vector<int> result(5);
std::adjacent_difference(v.begin(), v.end(), result.begin()); // result: {1, 1, 2, 3, 4}
partial_sum: Compute partial sums.
Calculates the partial sum of elements in a sequence.
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(5);
std::partial_sum(v.begin(), v.end(), result.begin()); // result: {1, 3, 6, 10, 15}
6. Queries on Sequences
These algorithms provide efficient ways to query sequences about their characteristics, such as finding the minimum, maximum, or both values within the range.
max, min: Return max/min elements.
These functions are used to obtain the maximum or minimum of two values.
int a = 5, b = 10;
int maximum = std::max(a, b); // maximum: 10
int minimum = std::min(a, b); // minimum: 5
minmax: Return both min and max.
This function returns a pair containing the minimum and maximum of its two input values.
auto result = std::minmax(5, 10); // result: {5, 10}
max_element, min_element: Return iterator to max/min elements.
These functions return an iterator pointing to the maximum or minimum element of a sequence.
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
auto it_max = std::max_element(v.begin(), v.end()); // it_max points to 9
auto it_min = std::min_element(v.begin(), v.end()); // it_min points to 1
minmax_element: Return pair of iterators.
Returns a pair of iterators pointing to the minimum and maximum elements of a sequence.
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
auto it_pair = std::minmax_element(v.begin(), v.end());
// it_pair.first points to 1
// it_pair.second points to 9
7. Raw Memory Operations
Raw memory operations deal with the allocation and management of raw memory regions, typically working directly with uninitialized memory. These operations are useful when working at a lower level, especially when combined with custom memory allocators. They can optimize performance by sidestepping default initializations and constructions.
uninitialized_copy: Copy construct elements.
This function copies elements from one range to another uninitialized memory location using the copy constructor.
std::vector<std::string> source = {"Hello", "World"};
std::allocator<std::string> alloc;
std::string* p = alloc.allocate(2); // allocate raw memory for 2 strings
std::uninitialized_copy(source.begin(), source.end(), p);
// Now, "Hello" and "World" are copy constructed at p and p+1 respectively
alloc.deallocate(p, 2); // deallocate memory after use
uninitialized_move: Move construct elements.
It moves elements from one range to another uninitialized memory location using the move constructor.
std::vector<std::string> source = {"Hello", "World"};
std::allocator<std::string> alloc;
std::string* p = alloc.allocate(2);
std::uninitialized_move(source.begin(), source.end(), p);
// The contents of 'source' are moved to p and p+1
alloc.deallocate(p, 2);
uninitialized_fill: Fill memory with a value.
This function fills an uninitialized memory range with the specified value.
std::allocator<int> alloc;
int* p = alloc.allocate(5); // allocate raw memory for 5 integers
std::uninitialized_fill(p, p + 5, 42);
// The range [p, p+5) is now filled with the value 42
alloc.deallocate(p, 5);
destroy: Destroy elements in a range.
It calls the destructor for the specified range of objects without deallocating the memory.
std::allocator<std::string> alloc;
std::string* p = alloc.allocate(2);
std::uninitialized_fill(p, p + 2, "Hello");
std::destroy(p, p + 2); // Calls the destructor for each element in the range
alloc.deallocate(p, 2);
Certainly! Here's a conclusion and some best practices when dealing with STL algorithms:
8. Conclusion and Best Practices
After exploring the vast array of algorithms that the STL provides, it's evident that the library offers tools to handle almost any computational problem we might face. However, having a multitude of choices also requires an understanding of when and how to use each algorithm optimally. Here are some concluding thoughts and best practices to guide you:
Understand When to Use Which Algorithm
Just because an algorithm exists doesn't mean it's always the best choice. Consider the problem at hand, the constraints, and the properties of the data. For instance:
- For searching within sorted sequences, prefer binary_search, lower_bound, or upper_bound over linear searches like find.
- Use sort for full ordering, but if you only need to find a position or partially order elements, nth_element or partial_sort may be more efficient.
Emphasize the Importance of Knowing the Complexities and Trade-offs
- Always be aware of the time and space complexities of the algorithms you're using. It could be the difference between an efficient solution and one that doesn't scale.
- Understand that some algorithms guarantee stability (like
stable_sort) while others don't (sort). Depending on the application, this might be crucial.
Reminder on the Power of Combining STL Containers with STL Algorithms
- The STL is designed such that its algorithms and containers complement each other. Utilizing them together can significantly enhance performance and code readability.
- For instance, using
std::list's member functionsort()takes advantage of the linked list's properties, offering a potentially faster sort than usingstd::sort(). - Many algorithms work on a range of elements, represented by iterators. The universality of iterators in the STL means you can often use the same algorithm across different container types without modification.
Additional Best Practices
- Always prefer algorithms over hand-written loops when possible. They often lead to more readable, concise, and sometimes even faster code due to compiler optimizations.
- Be cautious when using algorithms that work on raw memory, like the uninitialized family of functions. They offer performance benefits but increase the chance of errors.
- Always test your code thoroughly, especially when integrating multiple STL algorithms or using them in unconventional ways.