Algorithms of STL – Technical Infos

[Copy from one iterator to another]
[Join container elements into a string]
[Sort containers with std::sort]
[Modify containers with std::transform]
[Find items in a container]
[Generate permutations of data sequences]
[Merge sorted containers]
[Run algorithms in parallel]
[std::sample]

STL containers have standardized interfaces. This allows a library of algorithms to operate on all container types sharing the same interface. Compared to handwritten code algorithms are not necessarily shorter, but often they are more efficient and easier to maintain.

From C++20 on the ranges library provides a set of alternative algorithms with simplified interfaces and the possibility to operate with ranges and views.

Copy from one iterator to another

    std::vector<std::string> v1 {"one", "two", "three", "four", "five"};
    PrintContainer(v1, "v1");

    // Copy to target vector of same size
    std::vector<std::string> v2(v1.size()); // allocate enough memory for the elements of v1!
    std::copy(v1.begin(), v1.end(), v2.begin());
    PrintContainer(v2, "v2");

    // Insert in empty target vector
    std::vector<std::string> v3;
    std::copy(v1.begin(), v1.end(), std::back_inserter(v3));
    PrintContainer(v3, "v3");

    // Use ranges::copy
    std::vector<std::string> v4;
    std::ranges::copy(v1, std::back_inserter(v4));
    PrintContainer(v4, "v4");

    // Copy only some of the elements (here: 3 elements starting with the second)
    std::vector<std::string> v5;
    std::copy_n(v1.begin()+1, 3, std::back_inserter(v5));
    PrintContainer(v5, "v5");

    // Conditional copy with boolean predicate function
    std::vector<std::string> v6;
    std::ranges::copy_if(v1, std::back_inserter(v6), [](std::string& s) {return s.size() >= 4; });
    PrintContainer(v6, "v6");

    // Copy to std::out stream
    std::ostream_iterator<std::string> out_it(std::cout, " "); // blank will follow also after last element
    std::cout << "Copy to std::out: ";
    std::ranges::copy(v1, out_it);
    std::cout << '\n';

    // Move contents to other vector
    std::vector<std::string> v7;
    std::ranges::move(v1, std::back_inserter(v7));
    PrintContainer(v1, "v1 after move");
    PrintContainer(v7, "v7 after move");

Output:

v1: one two three four five
v2: one two three four five
v3: one two three four five
v4: one two three four five
v5: two three four
v6: three four five
Copy to std::out: one two three four five
v1 after move:
v7 after move: one two three four five

Join container elements into a string

When writing several elements into a string proper separators are needed for readability.

As the standard does not fully support this requirement here are some helper functions:

namespace MyUtils
{
    // Provide separator between string elements, write result to stream
    template<typename I>
    std::ostream& join(I it, I end_it, std::ostream& o, std::string_view sep = "")
    {
        if (it != end_it) o << *it++;
        while (it != end_it) o << sep << *it++;
        return o;
    }

    // Provide separator between string elements, write result to string
    template<typename I>
    std::string join(I it, I end_it, std::string_view sep = "")
    {
        std::ostringstream o;
        join(it, end_it, o, sep);
        return o.str();
    }

    // Overload for container, stream version
    template<typename Container>
    std::ostream& join(Container& c, std::ostream& o, std::string_view sep = "")
    {
        return join(std::begin(c), std::end(c), o, sep);
    }

    // Overload for container, string version
    template<typename Container>
    std::string join(Container& c, std::string_view sep = "")
    {
        return join(std::begin(c), std::end(c), sep);
    }
}

Example code to format elements:

    std::vector<std::string> v {"one", "two", "three", "four", "five"};

    // Join words without separators
    auto joinedView = std::ranges::views::join(v);
    std::cout << "std joined view          : ";
    for (const char c : joinedView) std::cout << c;
    std::cout << '\n';

    // Join words with separators using selfwritten utility function
    std::cout << "MyUtils joined to std:out: ";
    MyUtils::join(v, std::cout, ", ") << '\n';

    std::string s = MyUtils::join(v, ", ");
    std::cout << "MyUtils joined to string : " << s << '\n';

Output:

std joined view          : onetwothreefourfive
MyUtils joined to std:out: one, two, three, four, five
MyUtils joined to string : one, two, three, four, five

Sort containers with std::sort

Helper functions:

#include <random>

void Randomize(auto& c)
{
    static std::random_device rd;
    static std::default_random_engine rng(rd());
    std::shuffle(c.begin(), c.end(), rng);
}

void CheckSorted(auto& c)
{
    if (!std::is_sorted(c.begin(), c.end())) std::cout << "un";
    std::cout << "sorted: ";
}

void PrintContainerS(const auto& c)
{
    CheckSorted(c);
    for (auto& e : c) std::cout << e << " ";
    std::cout << '\n';
}

Example code to sort elements:

    std::vector<int> v {1,2,3,4,5,6,7,8,9,10};
    PrintContainerS(v);

    Randomize(v);
    PrintContainerS(v);

    std::ranges::sort(v);
    PrintContainerS(v);
    // Optionally specify sort algorithm
    std::ranges::sort(v, std::greater{});
    PrintContainer(v);
    std::ranges::sort(v, [](const int& lhs, const int& rhs) {return lhs > rhs; });
    PrintContainer(v);

    std::cout << "\npartial_sort (sort the first N elements)\n";
    Randomize(v);
    PrintContainer(v);
    // Sort the first 4 elements
    std::ranges::partial_sort(v, v.begin() + 4);
    PrintContainer(v);

    std::cout << "\npartition (move elements with some property to the front)\n";
    Randomize(v);
    PrintContainer(v);
    // Move all elements dividable by 3 to the front
    std::ranges::partition(v, [](int& i) {return i % 3 == 0; });
    PrintContainer(v);

Output:

sorted: 1 2 3 4 5 6 7 8 9 10
unsorted: 1 8 2 3 6 4 5 10 9 7
sorted: 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1

partial_sort (sort the first N elements
8 9 10 6 3 4 1 2 7 5
1 2 3 4 10 9 8 6 7 5

partition (move elements with some property to the front)
5 3 6 9 4 8 2 10 7 1
9 3 6 5 4 8 2 10 7 1

Modify containers with std::transform

Example code to transform elements:

    std::vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> v1;
    PrintContainer(v);
    std::ranges::transform(v, std::back_inserter(v1), [](const int& x) {return x * x; });
    PrintContainer(v1);

    // Works also with std::string
    std::string s{"asdfg"};
    std::string s1(s.length(),' '); // ensure same size
    PrintContainer(s);
    std::ranges::transform(s, s1.begin(), [](const char& c) {return c+1; });
    PrintContainer(s1);
    std::string s2;
    std::ranges::transform(s, std::back_inserter(s2), [](const char& c) {return c + 2; });
    PrintContainer(s2);

    // Modify the container itself, adjust values using clamp
    constexpr int minVal = 3;
    constexpr int maxVal = 8;
    PrintContainer(v);
    std::ranges::transform(v, v.begin(), [=](const int& x) {return std::clamp(x, minVal, maxVal); });
    PrintContainer(v);

Output:

1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100
a s d f g
b t e g h
c u f h i
1 2 3 4 5 6 7 8 9 10
3 3 3 4 5 6 7 8 8 8

std::transform does not guarantee that the elements will be processed in order. If required you must explicitly program your own for loop.

Find items in a container

Example code to find elements:

    std::vector<int> v {1, 6, 2, 7, 3, 4, 5, 6, 7, 8, 9, 10};
    PrintContainer(v);

    // Find first element with a given value
    auto it7 = std::ranges::find(v, 7);
    if (it7 != v.end())
    {
        std::cout << std::format("Found {} at index {}\n", *it7, std::distance(v.begin(), it7));
    }

    // Find first element that fulfills a condition
    auto it3 = std::ranges::find_if(v, [](const int& i) {return i % 3 == 0; });
    if (it3 != v.end())
    {
        std::cout << std::format("Found {} at index {}\n", *it3, std::distance(v.begin(), it3));
    }

    // Find all elements that fulfill a condition
    auto resultView = std::ranges::views::filter(v, [](const int& i) {return i % 3 == 0; });
    if (!resultView.empty())
    {
        std::cout << std::format("Found following matches: {}\n", MyUtils::join(resultView," "));
    }

    // OPEN: how can we get all found iterator positions?

Output:

1 6 2 7 3 4 5 6 7 8 9 10
Found 7 at index 3
Found 6 at index 1
Found following matches: 6 3 6 9

If the container element is a general class object, then the class must have an operator==() member function to support ranges::find.

Generate permutations of data sequences

The next_permutation() algorithm generates permutations by re-ordering a container to the next lexicographical permutation:

    std::cout << "all permutations, starting with lexicographical sorted container:\n";
    std::vector<int> v {1, 2, 3};
    do
    {
        PrintContainer(v);
    } while (std::next_permutation(v.begin(), v.end()));

    std::cout << "only rest of permutations, starting with lexicographical later sort order:\n";
    std::vector<int> v1 {2, 3, 1};
    do
    {
        PrintContainer(v1);
    } while (std::next_permutation(v1.begin(), v1.end()));

    std::cout << "fewer permutations, same values are not permutated:\n";
    std::vector<int> v3 {1, 1, 3};
    do
    {
        PrintContainer(v3);
    } while (std::next_permutation(v3.begin(), v3.end()));

Output:

all permutations, starting with lexicographical sorted container:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
only rest of permutations, starting with lexicographical later sort order:
2 3 1
3 1 2
3 2 1
fewer permutations, same values are not permutated:
1 1 3
1 3 1
3 1 1

Merge sorted containers

std::merge takes two sorted sequences and generates a third merged and sorted sequence:

    std::vector<std::string> v1 {"bba", "czz", "yxx"}; // is sorted!
    std::vector<std::string> v2 {"add", "fhh", "zww"}; // is sorted!
    std::vector<std::string> v3;
    std::ranges::merge(v1, v2, std::back_inserter(v3));
    PrintContainer(v3);

Output:

add bba czz fhh yxx zww

Run algorithms in parallel

Many of the STL algorithms can run in parallel execution with improved performance. Those algorithms accept an execution policy object when invoked.

Example:

#include <execution>

std::sort(std::execution::par_unseq,v.begin(), v.end());
std::transform(std::execution::par, v.begin(), v.end(), v.begin(), [](const int& x) {return x * x; });

For more info on execution policy see https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

std::sample

If you have generated a large set of random data (see std::random_device, std::mt19937, std::normal_distribution,) you can get a smaller set of random data using std::sample, i.e. instead of 200.000 random data you work only with 500 randomly chosen data from the bigger set. For more details see [Bill Weinman, page 194 ff.]