04 December 2014

Top 5 Beautiful C++ std Algorithms Examples

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.

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

Interested in new blog posts and occasional updates? Please sign up for my free newsletter.

Copyright Bartlomiej Filipek, 2016, Blogger platform
Any opinions expressed herein are in no way representative of those of my employers.
This site contains ads or referral links, which provide me with a commission. Thank you for your understanding.