Click here to Skip to main content
13,798,203 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

91.5K views
540 downloads
122 bookmarked
Posted 16 Dec 2014
Licenced CPOL

Top 5 Beautiful C++ std Algorithms Examples

, 16 Dec 2014
Rate this:
Please Sign up or sign in to vote.
Several examples of beautiful code made up of algorithms from the C++ standard library. Heavily uses modern C++.

Some time ago, I saw 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 Plan

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 first, It last, It pos) -> std::pair<It, It>
{
    if (pos < first) return { pos, std::rotate(pos, frist, last) };
    if (last < pos) return { std::rotate(first, last, pos), pos };
    return { first, llast };
}

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 moves 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?

Its 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 a 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!

Resources

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Bartlomiej Filipek
Software Developer
Poland Poland
Software developer interested in creating great code and passionate about teaching.

Author of C++17 In Detail - a book that will teach you the latest features of C++17!

I have around 11 years of professional experience in C++/Windows/Visual Studio programming. Plus other technologies like: OpenGL, game development, performance optimization.

In 2018 I was awarded by Microsoft as MVP, Developer Technologies.

If you like my articles please subscribe to my weekly C++ blog or just visit www.bfilipek.com.

You may also be interested in...

Comments and Discussions

 
BugrandIter undefined Pin
D4rkTrick27-Feb-15 15:21
professionalD4rkTrick27-Feb-15 15:21 
GeneralRe: randIter undefined Pin
Bartlomiej Filipek1-Mar-15 8:18
memberBartlomiej Filipek1-Mar-15 8:18 
GeneralRe: thx! Pin
D4rkTrick2-Mar-15 14:23
professionalD4rkTrick2-Mar-15 14:23 
Suggestionformatting and naming Pin
D4rkTrick27-Feb-15 15:14
professionalD4rkTrick27-Feb-15 15:14 
Questionrequest Pin
taranea24-Dec-14 10:33
membertaranea24-Dec-14 10:33 
QuestionSource Code Pin
geoyar22-Dec-14 15:40
membergeoyar22-Dec-14 15:40 
AnswerRe: Source Code Pin
Bartlomiej Filipek23-Dec-14 3:18
memberBartlomiej Filipek23-Dec-14 3:18 
QuestionAlternative for string trimming Pin
LWessels18-Dec-14 2:46
memberLWessels18-Dec-14 2:46 
AnswerRe: Alternative for string trimming Pin
Bartlomiej Filipek18-Dec-14 2:52
memberBartlomiej Filipek18-Dec-14 2:52 
QuestionString trimming Pin
Stian André Olsen17-Dec-14 23:01
memberStian André Olsen17-Dec-14 23:01 
AnswerRe: String trimming Pin
Bartlomiej Filipek18-Dec-14 2:54
memberBartlomiej Filipek18-Dec-14 2:54 
GeneralRe: String trimming Pin
Stian André Olsen18-Dec-14 3:40
memberStian André Olsen18-Dec-14 3:40 
GeneralRe: String trimming Pin
Michael Gazonda30-Dec-14 17:49
professionalMichael Gazonda30-Dec-14 17:49 
Suggestionstd Pin
pates17-Dec-14 9:47
memberpates17-Dec-14 9:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web04 | 2.8.181207.3 | Last Updated 16 Dec 2014
Article Copyright 2014 by Bartlomiej Filipek
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid