How I Discovered the C++ Algorithm Library and Learned Not To Reinvent the Wheel

As a C++ developer with over a decade of experience, I‘ve seen the language and its associated libraries evolve significantly. However, my own evolution as a developer didn‘t always keep pace. For many years, I had a tendency to write a lot of code from scratch, even for common tasks like sorting, searching, and data manipulation.

While this approach gave me a deep understanding of the fundamentals, it also meant I spent a lot of time reinventing the wheel. It wasn‘t until I took a deep dive into the C++ standard library that I realized how much functionality I had been overlooking, particularly in the <algorithm> header.

The Perils of Reinvention

The tendency to write custom code for every task is a common pitfall, especially for less experienced developers. It‘s an understandable impulse – after all, writing your own code can be a great way to learn and can give you a feeling of control and understanding over every aspect of your program.

However, this approach has several downsides:

1. It‘s time-consuming. Writing, debugging, and optimizing code takes time. If you‘re reinventing the wheel for every task, that time can add up quickly.

2. It‘s error-prone. Even the best programmers make mistakes. The more code you write, the more opportunities there are for bugs to creep in.

3. It can lead to inconsistency. If every developer in a team is writing their own implementations of common tasks, you can end up with a codebase that‘s difficult to understand and maintain.

4. It can result in suboptimal performance. Writing efficient, optimized code is hard. It‘s easy to end up with implementations that are slower or use more memory than necessary.

When I finally realized the scope of what the standard library algorithms offered, it was a lightbulb moment. Here was a set of tools that could save me time, make my code more reliable and consistent, and in many cases, offer better performance than my handwritten implementations.

The Power of the Algorithm Library

The <algorithm> library is one of the most powerful parts of the C++ standard library. It provides a collection of functions for performing common operations on ranges of elements. These include simple tasks like finding and counting elements, modifying and rearranging data, and more complex operations like sorting, searching, and set manipulation.

To give you an idea of the scope, here are some statistics:

• The C++20 standard defines over 100 algorithms in the <algorithm> header.
• The library includes 7 different sorting algorithms, including std::sort, std::stable_sort, and std::partial_sort.
• There are 14 functions for searching and binary search, including std::find, std::binary_search, and std::equal_range.
• The library provides 5 algorithms for partitioning ranges, like std::partition and std::stable_partition.
• There are over 20 functions for modifying sequences, such as std::copy, std::transform, and std::unique.

These algorithms are designed to be efficient, flexible, and reusable. They work with any data type that provides certain basic operations (like comparison for sorting), and they can be easily customized by providing your own function objects or lambdas.

For example, consider the task of sorting a vector of integers in descending order. With the std::sort algorithm, it‘s as simple as:

std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
std::sort(numbers.begin(), numbers.end(), std::greater<int>());

The std::greater<int> function object tells std::sort to use the > operator for comparisons instead of the default <.

Compare this to the code you might write to implement a descending order sort from scratch:

void sort_descending(std::vector<int>& numbers) {
    for (size_t i = 0; i < numbers.size(); ++i) {
        for (size_t j = i + 1; j < numbers.size(); ++j) {
            if (numbers[j] > numbers[i]) {
                std::swap(numbers[i], numbers[j]);
            }
        }
    }
}

Not only is the standard library version much shorter and easier to read, but it‘s also likely to be more efficient. The standard library sort functions use highly optimized algorithms like introsort which provide excellent average and worst-case performance.

Real-World Examples

To further illustrate the power of the algorithm library, let‘s look at a few more real-world examples.

Example 1: Removing Duplicates

Suppose you have a vector of words and you want to remove all the duplicates. You could write a function to do this manually, iterating through the vector, keeping track of which words you‘ve seen before, and removing any duplicates you encounter.

Or you could use the std::unique algorithm:

std::vector<std::string> words = {"the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
auto end_unique = std::unique(words.begin(), words.end());
words.erase(end_unique, words.end());

The std::unique function shuffles all the unique elements to the front of the range and returns an iterator to the end of the unique range. We can then use the vector‘s erase function to remove everything after that iterator.

Example 2: Performing Set Operations

Let‘s say you have two sorted vectors of integers, and you want to find all the numbers that are present in both vectors.

Manually, you might write something like this:

std::vector<int> intersection(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> result;
    for (int x : a) {
        if (std::binary_search(b.begin(), b.end(), x)) {
            result.push_back(x);
        }
    }
    return result;
}

But with the std::set_intersection algorithm, it‘s much simpler:

std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {3, 4, 5, 6, 7};
std::vector<int> intersection;

std::set_intersection(vec1.begin(), vec1.end(),
                      vec2.begin(), vec2.end(),
                      std::back_inserter(intersection));

The std::set_intersection function computes the intersection of the two ranges and stores the result in the intersection vector using the std::back_inserter iterator adapter.

Example 3: Partial Sums

Computing the partial sums of a range (i.e., the sums of all prefixes of the range) is a common operation, especially in numeric and financial applications.

Without the standard library, you might write a function like this:

std::vector<int> partial_sums(const std::vector<int>& numbers) {
    std::vector<int> sums;
    int sum = 0;
    for (int x : numbers) {
        sum += x;
        sums.push_back(sum);
    }
    return sums;
}

But the <numeric> library (a sibling of <algorithm>) provides the std::partial_sum function which makes this a one-liner:

std::vector<int> numbers = {1, 2, 3, 4, 5};
std::vector<int> sums;
std::partial_sum(numbers.begin(), numbers.end(), std::back_inserter(sums));

The Importance of the Standard Library

The <algorithm> library is just one part of the extensive C++ standard library. The standard library as a whole is an invaluable resource for C++ programmers. As Bjarne Stroustrup, the creator of C++, has said:

"The standard library is as much a part of the C++ language as the built-in types and operations. A programmer who doesn‘t know the standard library is seriously handicapped."

This sentiment is echoed by many C++ experts. Herb Sutter, a leading authority on C++ and a member of the C++ standards committee, has written:

"The C++ standard library provides an extensible framework […] within which you can implement just about any algorithm you can think of. Moreover, it does so in a generic manner that allows you to plug in your own types and operations, making it possible to reuse the algorithms across a broad range of types and situations. […] The standard library algorithms are the very heart of generic programming in C++."

Using the standard library effectively is a key part of writing modern, idiomatic C++. It can help make your code more expressive, more maintainable, and less buggy.

Conclusion

My journey from reinventing the wheel to embracing the standard library was a significant turning point in my growth as a C++ developer. Learning to leverage the power of the <algorithm> library and other standard library features allowed me to write better code in less time.

If you‘re a C++ programmer who‘s not yet fully familiar with the standard library, I highly encourage you to invest some time in exploring it. Read the documentation, try out the algorithms and containers in your own code, and see how they can improve your programming experience.

Remember, C++ is a large and complex language, and there‘s always more to learn. But by standing on the shoulders of giants and leveraging the collective wisdom embodied in the standard library, we can all write better, more efficient, and more maintainable code.