Friday, November 18, 2016

C++ tips, 2016 Week 45 (7-Nov - 13-Nov-2016)

This is part of my weekly C++ posts based on the daily C++ tips I make at my work. I strongly recommend this practice. If you dont have it in your company start it. 
List of all weekly posts can be found here.


1. Termination of a C++ program

There are multiple ways a C++ program may terminate. These include both normal and unexpected termination.
This GraphViz diagram shows the program termination flows as defined by the standard. It is a big one so probably better viewed on the github link.



2. Folding expressions

In C++17 Fold expression reduces a parameter pack over a binary operator. It is a way to apply the same binary operation ( for example +, <, || ) on a parameter pack .

Outputting all arguments:

template<typename ...Args> 

void printer(Args&&... args) { 

    (std::cout << ... << args) << '\n'; 
} 
 
printer( 1, 1.2, "alabala");


3. Sorting algorithms in STL


In the Standard Library we have five (or 3 + 1 + 1) sorting algorithms - sort, partial_sort, stable_sortstd::list:;sort and sort_heap (If I havent missed some)

std::sort - is the most common sorting algorithm. It is required to have average O(N·log(N)) by the Standard so its usually a quick sort. It takes two random access iterators and an optional comparison function. From C++17 it can be parallelised with first argument the parallelization policy.

std::list::sort - since std::sort requires random access iterators and std::list has bidirectional ones there is a member function in std::list for sorting. It is also required to have O(N·log(N)) complexity

std::partial_sort - some times we dont need the whole container to be sorted only for example the biggest 10 elements so - std::partial_sort to the rescue. Also parallelizable and with similar complexity to std::sort

std::stable_sort - guarantees the order of equal elements. When sorting for example pairs of something on their first we want the ones with equal first to retain the order. Usual use case is sorting elements by second and than partially sorting them by first - when displayed the elements will be sorted by first and than by second. Similar complexity also parallelizable.

std::sort_heap - sorts a heap but the sorted range looses the heap property. Its more efficient to use sort_heap if you already have a heap instead of std::sort. Complexity is 3 * distance(first, last). Not parallelizable.

Additional related STL algorithms: nth_element, partial_sort_copy, max_element/min_element (yea! max/min_element - specializations of partial_sort!!!) and I probably missed something. STL has a lot of stuff.

4. boost::hana

Honorable mention of boost::hana. Written by Louis Dionne it is (and I quote):

Hana is a header-only library for C++ metaprogramming suited for computations on both types and values. The functionality it provides is a superset of what is provided by the well established Boost.MPL and Boost.Fusion libraries. By leveraging C++11/14 implementation techniques and idioms, Hana boasts faster compilation times and runtime performance on par or better than previous metaprogramming libraries, while noticeably increasing the level of expressiveness in the process.

Which means that he pushes the modern features to the limits. Meaning that you should probably study how it is implemented just to keep yourself ahead of the curve. Example:

#include <boost/hana/assert.hpp> 
#include <boost/hana/fold_left.hpp> 
#include <boost/hana/tuple.hpp> 
 
#include <sstream> 
#include <string> 
 
namespace hana = boost::hana; 
auto to_string = [](auto x) { 
   std::ostringstream ss;  
   ss << x; 
   return ss.str(); 
}; 
 
int main() { 
   auto f = [=](std::string s, auto element) { 
       return "f(" + s + ", " + to_string(element) + ")"; 
   }; 
   // with an initial state 
   BOOST_HANA_RUNTIME_CHECK( 
       hana::fold_left(hana::make_tuple(2, '3', 4, 5.0), "1", f) 
       == 
       "f(f(f(f(1, 2), 3), 4), 5)" 
   ); 
   // without initial state 
   BOOST_HANA_RUNTIME_CHECK( 
       hana::fold_left(hana::make_tuple("1", 2, '3', 4, 5.0), f) 
       == 
       "f(f(f(f(1, 2), 3), 4), 5)" 
   ); 
}

5. There is no 5

I was short on time and energy and I decided in the future when the weekend comes to start the next week tips without filling the previous one. It will zero my tip-debt and I wont get stressed by debt accumulation. Apologies.