C++ Algorithm
C++ Algorithms
In the previous chapters, you learned that data structures (like vectors, lists, etc) are used to store and organize data.
Algorithms are used to solve problems by sorting, searching, and manipulating data structures.
The <algorithm> library provides many
useful functions to perform these tasks
with iterators.
To use these functions, you must include the <algorithm>
header file:
#include <algorithm>
Sorting Algorithms
To sort elements in a data structure, you can use the sort()
function.
The sort() function takes iterators
(typically a start iterator returned by begin()
and an end iterator returned by end()) as
parameters:
Example
vector<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};
// Sort cars alphabetically
sort(cars.begin(), cars.end());
By default, the elements are sorted in ascending order. In the example above, the elements are sorted alphabetically since they are strings.
If we had a vector of integers, they would be sorted numerically:
Example
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Sort numbers numerically
sort(numbers.begin(), numbers.end());
To reverse the order, you can use rbegin() and rend() instead of begin() and end():
Example
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Sort numbers numerically in reverse order
sort(numbers.rbegin(), numbers.rend());
To only sort specific elements, you could write:
Example
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Sort numbers numerically, starting from the fourth element (only sort 5, 9, and 2)
sort(numbers.begin() + 3, numbers.end());
Searching Algorithms
To search for specific elements in a vector, you can use the find()
function.
It takes three parameters: start_iterator,
end_iterator, value, where value is the value to search for:
Example
Seach for the number 3 in "numbers":
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Search for the number 3
auto it = find(numbers.begin(), numbers.end(), 3);
To search for the first element that is greater than a specific value, you can use the upper_bound() function:
Example
Find the first value greater than 5 in "numbers":
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Sort the vector in ascending order
sort(numbers.begin(), numbers.end());
// Find the first value that is greater than 5 in the sorted vector
auto it = upper_bound(numbers.begin(), numbers.end(), 5);
The upper_bound() function is typically used on sorted data structures. That's
why we first sort the vector in the example above.
To find the smallest element in a vector, use the min_element() function:
Example
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Find the smallest number
auto it = min_element(numbers.begin(), numbers.end());
To find the largest element, use the max_element() function:
Example
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Find the largest number
auto it = max_element(numbers.begin(), numbers.end());
Modifying Algorithms
To copy elements from one vector to another, you can use the copy() function:
Example
Copy elements from one vector to another:
vector<int> numbers = {1, 7, 3, 5, 9, 2};
// Create a vector called copiedNumbers that should store 6 integers
vector<int> copiedNumbers(6);
// Copy elements from numbers to copiedNumbers
copy(numbers.begin(), numbers.end(), copiedNumbers.begin());
To fill all elements in a vector with a value, you can use the fill() function:
Example
Fill all elements in the numbers vector with the value 35:
vector<int> numbers(6);
// Fill all elements in the numbers vector with the value 35
fill(numbers.begin(), numbers.end(), 35);
Complete Algorithm Reference
For a complete reference of algorithm functions, go to our C++ Algorithm Reference.