Table of Contents

Some time ago I’ve seen an inspiring talk from CppCon 2013: “C++ Seasoning” by Sean Parent. One of the main points of this presentation was not to use raw loops. Instead, prefer to use existing algorithms or write functions that ‘wraps’ such loops. I was curious about this idea and searched for nice code examples. Here is my short list of usage of algorithms from the C++ std library that might help in writing better code.

Of course. I could not skip two prominent examples from the original “C++ Seasoning” talk: slide and gather.

The code  

Source code can be found here: beautiful_std_alg.cpp @github

Solution (VS2013) is located here vc_solution @github

Insertion sort  

In just two lines of code!

for (auto i = start; i != end; ++i)
    std::rotate(std::upper_bound(start, i, *i), i, std::next(i));

How it works?

Rotate(first, middle, last)- takes a range [first, last) and rotates it so that the middle element becomes the first in that range.

upper_bound - Returns an iterator pointing to the first element in the range [first,last) which compares greater than val. The range should be already sorted (or at least partitioned).

How do those two elements combine into Insertion sort?

std::upper_bound(start, i, *i) returns position of the first element greater than *i. Then, the range is shifted, so that i-th element becomes first.

Let’s look at one example:

Pretty nice!

Quick sort  

Found on Stack Overflow:

template<class FwdIt, class Compare = std::less<>>
void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return; 
    auto const pivot = std::next(first, N / 2);
    std::nth_element(first, pivot, last, cmp);
    quickSort(first, pivot, cmp); 
    quickSort(pivot, last, cmp); 
}

How it works?

I will not describe quick sort algorithm… you should know how it works already! In this implementation std::nth_element is used to do most of the job. This function partially sorts the range so that given n-th elements is placed in proper position. All of the elements before n-th element are less than or equal to the elements after the n-th element.

Slide  

Example from the Sean Parent’s talk:

template <typename It> 
auto slide(It f, It l, randIter p) -> std::pair<It, It>
{
    if (p < f) return { p, std::rotate(p, f, l) };
    if (l < p) return { std::rotate(f, l, p), p };
    return { f, l };
}

How it works?

As an example, you can imagine a list of items on a UI dialog. User selects a continuous range and then algorithm takes this range and move it into some other place of the list.

  • this function uses std::rotate: to move elements forward or backward.
  • it returns two iterators - the start and the end of the new sequence. In C++11 std::rotate got new version and now can return iterator to the new position of p element.
  • if you are not interested in returning of this iterator pair, you can simplify this code much more.

Implementation note:

  • In GCC 4.9 (and previous versions) std::rotate does not return an iterator, but only void. So currently, this code will not work there.

Gather  

Another example from Sean Parent’s talk:

template <typename BiIt, typename UnPred> 
auto gather(BiIt f, BiIt l, BiIt p, UnPred s) -> std::pair <BiIt, BiIt>
{
    return { stable_partition(f, p, not1(s)), 
             stable_partition(p, l, s) };
}

How it works?

It’s use case can be similar to slide: select elements - using a predicate s (so this time continuous range is not needed), then gather those elements into a range and move this range to position around p. It returns the start and the end of the selected range.

UnPred is a predicate that returns if a given element is selected or not.

std::stable_partition: from cppreference

Reorders the elements in a given range in such a way that all elements for which the predicate returns true precede the elements for which predicate returns false. Relative order of the elements is preserved.

std::stable_partition is used twice:

Implementation note:

  • std::not1 does not work with the code correctly, so there is proposal to use simple lambda. Read more here in Sean’s comment.

String trim  

Found on Stack Overflow

std::string trim(const std::string &s) {
    return trimLeft(trimRight(s));
}

std::string trimLeft(const std::string &s) {
    auto temp = s;
    temp.erase(std::begin(temp), 
                std::find_if(std::begin(temp), std::end(temp), 
                    [](char c){return !std::isspace(c, std::locale()); 
                }));
    return temp;
}

std::string trimRight(const std::string &s) {
    auto temp = s;
    temp.erase(std::find_if(std::rbegin(temp), std::rend(temp), 
                [](char c){return !std::isspace(c, std::locale()); }).base(), 
                   std::end(temp));
    return temp;
}

How it works?

Another beautiful usage of Standard Library:

  • in order to trim the string we trim from right and then from the left (what a discovery!)
  • trim left: std::find_if returns iterator to the first non space character in the string. Then we erase those characters.
  • trim right: also uses std::find_if but this time we use reverse iterators

Note: you can also use boost string algorithm to make life even easier.

Bonus :)  

What does this code do?

while (std::next_permutation(start, end));

Simple, one line of code… should be nice! But…

Answer: it’s another and ‘wonderful’ method of sorting containers - permutation sort! But please do not use it at home :)

Complexity: O((n+1)!)

This algorithm is a variation of Bogosort and other similar ‘sorting’ algorithms. Read more on wiki. As victor_zverovich noticed, in Bogosort the next permutation is chosen at random, but std::next_permutation gives the next lexicographically greater permutation.

Sumup  

I’ve showed several, I think nice, code examples where algorithms from C++ Standard Library are heavily used. Maybe next time, when I’ll be writing some ugly piece of code I’ll stop, think for a minute, and maybe some existing algorithm/function could be called instead.

Side note: there’s a Pluralsight course from Kate Gregory with a similar name: Beautiful C++: STL Algorithms. So you might want to check it out later

Do you know some more interesting examples? My list, definitely, does not show all of them!

Thanks for a discussion at reddit: here @r/programming and here @r/cpp

Resources  

CodeProject