Welcome to Programming and Data Structures

In addition to the data structures we have learned about so far, the C++ Standard Library also provides a large collection of algorithms that can operate on these data structures. These algorithms are implemented as functions that can be called with different types of collections and perform common operations like searching, sorting, and transforming data.

We will not cover all (or even most) of these algorithms in detail here, but we will introduce some of the most commonly used ones to give you an idea of what is available and how to use them.

Not every algorithm is suitable for every type of collection. For example, you can’t use sort on an unordered_map because it does not have a defined order. It is completely meaningless to try putting in order things that do not provide any way to talk about which item comes before another.

However, the algorithms do work on any standard container where the operation makes sense. They do this by relying on abstractions like iterators and operator overloading. The code in the algorithms is written in terms of these abstractions. They do not know or care if they happen to be working with a vector, a set, or some other kind of collection. As long as the collection provides the necessary interface the algorithms can operate on the collection.

Must in the way that sets can rely on functors to specify how to order their elements, some algorithms also take functions (or functors) as parameters to customize their behavior. For example, the sort algorithm can take a comparison function to specify how to compare elements when sorting.

The prototype for std::sort looks like something like this:

void sort( RandomIt first, RandomIt last, Compare comp );

Here, RandomIt is a type that represents an iterator that can move through a collection in random order (like the iterators provided by a vector). This means you could not use this algorithm with containers that do not provide random access to their elements. The first and last parameters specify the range of elements to sort. The optional comp parameter is a comparison function that defines how to compare two elements.

So, to sort a vector, we can pass iterators to the beginning and end of the vector to the sort function.

sort(myVector.begin(), myVector.end());

That will sort the elements in the vector in ascending order using the default comparison operator. If we just wanted to sort the first 10 elements, we would adjust the last parameter to point to the iterator 10 positions from the beginning:

sort(myVector.begin(), myVector.begin() + 10);

If we wanted to sort the elements in descending order instead, we could provide a comparison functor that defines that ordering. The prototype that sort expects the comparison function looks like:

bool Compare(const T& a, const T& b);

This function should return true if a should come before b in the sorted order, and false otherwise. So, for descending order, we would want to return true if a is greater than b:

bool DescendingComparer(int a, int b) {
    return a > b; // a comes first if it is greater than b
}

This example first does a default sort of a vector of integers, then sorts it again in descending order.

sort(numbers.begin(), numbers.end(), std::greater<int>());