C++ Core Guidelines: Rules for Templates and Generic Programming

I give in this post an introduction to the rules for generic programming in C++. Generic programming is from my point of view the outstanding feature and the future of C++. Hence it follows, that this and the upcoming posts are about the future of C++.

 

future

First of all, I use the term templates and generic programming, whatever fits best. Of course, I know that templates are just a way to write generic code. I assume, you know what templates in C++ are but you don't know what does generic programming mean? Here is my favourite definition from Wikipedia.

  • Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters.

The rules to templates are about the current C++17 and the upcoming C++20 standard. Of course, I assume that we will get concepts with C++20. In sum, there are 100 rules to concepts, template interfaces, template definitions, template hierarchies, variadic templates, and template metaprogramming. The first five rules are quite general.

In the examples, concepts are often commented out. If you want to try them out, comment them in and use at least a  GCC 6.1 compiler with the flag -fconcepts or an online compiler: constraints and concepts.

Concepts are predicates on templates that are evaluated at compile time. They should model semantic categories such as Number, Callable, Iterator or Range but not syntactic restrictions such as HasPlus, or IsInvocable. Here are more details to concepts.

Maybe, you are puzzled by the difference between semantic categories and syntactic restrictions. The first rule helps to distinguish both terms.

T.1: Use templates to raise the level of abstraction of code

Here is the example from the guidelines but I called the second concept Addable.

template<typename T>
    // requires Incrementable<T>
T sum1(vector<T>& v, T s)
{
    for (auto x : v) s += x;
    return s;
}

template<typename T>
    // requires Addable<T>
T sum2(vector<T>& v, T s)
{
    for (auto x : v) s = s + x;
    return s;
}

 

What is wrong with both concepts? Both concepts are too specific. Both concepts are based on specific operations such as the increment and the + operation. Let's go one step further from the syntactic constraints to the semantic category Arithmetic.

 

template<typename T>
    // requires Arithmetic<T>
T sum(const vector<T>& v, T s)
{
    for (auto x : v) s += x;
    return s;
}

 

Now, the algorithm has the minimal requirements. Hold: the algorithm is better but not good. It only works only on a std::vector. It's generic on the type of the container but not on the container. Let me generalise the sum algorithm once more.

 

template<typename Cont, typename T>
    // requires Container<Cont>
    // && Arithmetic<T>
T sum(const Cont& v, T s)
{
    for (auto x : v) s += x;
    return s;
}

 

Now, it's fine. Maybe you prefer are a more concise definition of sum. Instead of the keyword typename, I use the concepts directly.

template<Container Cont, Arithmetic T>
T sum(const Cont& cont, T s){
    for (auto x : cont) s += x;
    return s;
}

T.2: Use templates to express algorithms that apply to many argument types

When you study the first overload of std::find at cppreference.com, it looks like this:

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

 

The types of the Iterators are encoded in their names: InputIt stands for input iterator and means that is an iterator that can read from the pointed-to element. There are two issues with this declaration:

  1. The requirements for the iterators are encoded in the name. This reminds me of the infamous Hungarian notation
  2. There is no requirement stated that the pointed-to element can be compared with the value.

Let me use the iterator concept directly:

template<Input_iterator Iter, typename Val>
    // Equality_comparable<Value_type<Iter>, Val>
Iter find(Iter b, Iter e, Val v)
{
    // ...
}

 

T.3: Use templates to express containers and ranges

Okay. It's quite obvious to make a container generic. For example, here is a Vector.

 

template<typename T>
    // requires Regular<T>
class Vector {
    // ...
    T* elem;   // points to sz Ts
    int sz;
};

Vector<double> v(10);
v[7] = 9.9;

 

Okay fine but when is a user-defined type T regular? The document Fundamentals of Generic Programming defines a type T regular if it behaves like a built-in type such as bool, int, or double. I should mention it. The paper Fundamentals of Generic Programming is from James C. Dehnert and Alexander Stepanov. I assume you know already Alexander Stephanov by name. He is the well-known father of the Standard Template Library.

The document states that a type T is called regular, if it defines the following operations:

regular

The equality, inequality, and ordering operation on T could be defined component-wise.

What's next?

My original plan was to write about rule 5: T.5: Combine generic and OO techniques to amplify their strengths, not their costs. I changed my plan because rule 5 is quite short and mentioned type erasure as a use-case for this technique. Type erasure is a technique to represent various concrete types through a single interface. Type erasure with templates could not be explained in a few sentences; therefore, I will write in my next post about this challenging technique.

 

Thanks a lot to my Patreon Supporters: Eric Pederson, Paul Baxter,  Meeting C++, Matt Braun, Avi Lachmish, Roman Postanciuc, Venkata Ramesh Gudpati, Tobias Zindl, and Mielo.

 

Get your e-book at Leanpub:

The C++ Standard Library

 

Concurrency With Modern C++

 

Get Both as one Bundle

cover   ConcurrencyCoverFrame   bundle
With C++11, C++14, and C++17 we got a lot of new C++ libraries. In addition, the existing ones are greatly improved. The key idea of my book is to give you the necessary information to the current C++ libraries in about 200 pages.  

C++11 is the first C++ standard that deals with concurrency. The story goes on with C++17 and will continue with C++20.

I'll give you a detailed insight in the current and the upcoming concurrency in C++. This insight includes the theory and a lot of practice with more the 100 source files.

 

Get my books "The C++ Standard Library" (including C++17) and "Concurrency with Modern C++" in a bundle.

In sum, you get more than 600 pages full of modern C++ and more than 100 source files presenting concurrency in practice.

 

 Get your interactive course at educative

Modern C++ Concurrency in Practice: Get the most out of any machine

educative

Based on my book "Concurrency with Modern C++" educative.io created an interactive course.

What's Inside?

  • 140 lessons
  • 110 code playgrounds => Run in browser
  • 78 code snippets
  • 55 illustrations

Comments   

+1 #1 Roman 2018-09-03 06:35
Hi.
What is the differenc between first template (requires Incrementable) and the third template (requires Arithmetic)?
Quote

Add comment


Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 2316

All 1233249

Currently are 165 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments