Mastering the C++17 STL

4.4 (8 reviews total)
By Arthur O'Dwyer
  • Instant online access to over 7,500+ books and videos
  • Constantly updated with 100+ new titles each month
  • Breadth and depth in over 1,000+ technologies
  1. Classical Polymorphism and Generic Programming

About this book

Modern C++ has come a long way since 2011. The latest update, C++17, has just been ratified and several implementations are on the way.

This book is your guide to the C++ standard library, including the very latest C++17 features.

The book starts by exploring the C++ Standard Template Library in depth. You will learn the key differences between classical polymorphism and generic programming, the foundation of the STL. You will also learn how to use the various algorithms and containers in the STL to suit your programming needs. The next module delves into the tools of modern C++. Here you will learn about algebraic types such as std::optional, vocabulary types such as std::function, smart pointers, and synchronization primitives such as std::atomic and std::mutex. In the final module, you will learn about C++'s support for regular expressions and file I/O.

By the end of the book you will be proficient in using the C++17 standard library to implement real programs, and you'll have gained a solid understanding of the library's own internals.

Publication date:
September 2017
Publisher
Packt
Pages
384
ISBN
9781787126824

 

Chapter 1. Classical Polymorphism and Generic Programming

The C++ standard library has two distinct, yet equally important, missions. One of these missions is to provide rock-solid implementations of certain concrete data types or functions that have tended to be useful in many different programs, yet aren't built into the core language syntax. This is why the standard library contains std::string, std::regex, std::filesystem::exists, and so on. The other mission of the standard library is to provide rock-solid implementations of widely used abstract algorithms such as sorting, searching, reversing, collating, and so on. In this first chapter, we will nail down exactly what we mean when we say that a particular piece of code is "abstract," and describe the two approaches that the standard library uses to provide abstraction: classical polymorphism and generic programming.

We will look at the following topics in this chapter:

  • Concrete (monomorphic) functions, whose behavior is not parameterizable
  • Classical polymorphism by means of base classes, virtual member functions, and inheritance
  • Generic programming by means of concepts, requirements, and models
  • The practical advantages and disadvantages of each approach
 

Concrete monomorphic functions


What distinguishes an abstract algorithm from a concrete function? This is best shown by example. Let's write a function to multiply each of the elements in an array by 2:

    class array_of_ints {
      int data[10] = {};
      public:
        int size() const { return 10; }
        int& at(int i) { return data[i]; }
    };

    void double_each_element(array_of_ints& arr)
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

Our function double_each_element works only with objects of type array_of_int; passing in an object of a different type won't work (nor even compile). We refer to functions like this version of double_each_element as concrete or monomorphic functions. We call them concrete because they are insufficientlyabstract for our purposes. Just imagine how painful it would be if the C++ standard library provided a concrete sort routine that worked only on one specific data type!

 

Classically polymorphic functions


We can increase the abstraction level of our algorithms via the techniques of classical object-oriented (OO) programming, as seen in languages such as Java and C#. The OO approach is to decide exactly which behaviors we'd like to be customizable, and then declare them as the public virtual member functions of an abstract base class:

    class container_of_ints {
      public:
      virtual int size() const = 0;
      virtual int& at(int) = 0;
    };

    class array_of_ints : public container_of_ints {
      int data[10] = {};
      public:
        int size() const override { return 10; }
        int& at(int i) override { return data[i]; }
    };

    class list_of_ints : public container_of_ints {
      struct node {
        int data;
        node *next;
      };
      node *head_ = nullptr;
      int size_ = 0;
      public:
       int size() const override { return size_; }
       int& at(int i) override {
        if (i >= size_) throw std::out_of_range("at");
        node *p = head_;
        for (int j=0; j < i; ++j) {
          p = p->next;
        }
        return p->data;
      }
      ~list_of_ints();
    };

    void double_each_element(container_of_ints& arr) 
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      } 
    }

    void test()
    {
      array_of_ints arr;
      double_each_element(arr);

      list_of_ints lst;
      double_each_element(lst);
    }

Inside test, the two different calls to double_each_element compile because in classical OO terminology, an array_of_intsIS-Acontainer_of_ints (that is, it inherits from container_of_ints and implements the relevant virtual member functions), and a list_of_intsIS-Acontainer_of_ints as well. However, the behavior of any given container_of_ints object is parameterized by its dynamic type; that is, by the table of function pointers associated with this particular object.

Since we can now parameterize the behavior of the double_each_element function without editing its source code directly--simply by passing in objects of different dynamic types--we say that the function has become polymorphic.

But still, this polymorphic function can handle only those types which are descendants of the base class container_of_ints. For example, you couldn't pass a std::vector<int> to this function; you'd get a compile error if you tried. Classical polymorphism is useful, but it does not get us all the way to full genericity.

An advantage of classical (object-oriented) polymorphism is that the source code still bears a one-to-one correspondence with the machine code that is generated by the compiler. At the machine-code level, we still have just one double_each_element function, with one signature and one well-defined entry point. For example, we can take the address of double_each_element as a function pointer.

 

Generic programming with templates


In modern C++, the typical way to write a fully generic algorithm is to implement the algorithm as a template. We're still going to implement the function template in terms of the public member functions .size() and .at(), but we're no longer going to require that the argument arr be of any particular type. Because our new function will be a template, we'll be telling the compiler "I don't care what type arr is. Whatever type it is, just generate a brand-new function (that is, a template instantiation) with that type as its parameter type."

    template<class ContainerModel>
    void double_each_element(ContainerModel& arr)
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

    void test()
    {
      array_of_ints arr;
      double_each_element(arr);

      list_of_ints lst;
      double_each_element(lst);

      std::vector<int> vec = {1, 2, 3};
      double_each_element(vec);
    }

In most cases, it helps us design better programs if we can put down in words exactly what operations must be supported by our template type parameter ContainerModel. That set of operations, taken together, constitutes what's known in C++ as a concept; in this example we might say that the concept Container consists of "having a member function named size that returns the size of the container as an int (or something comparable to int); and having a member function named at that takes an int index (or something implicitly convertible from int) and produces a non-const reference to the index'th element of the container." Whenever some class array_of_ints correctly supplies the operations required by the concept Container, such that array_of_ints is usable with double_each_element, we say that the concrete class array_of_intsis a model of the Container concept. This is why I gave the name ContainerModel to the template type parameter in the preceding example.

Note

It would be more traditional to use the name Container for the template type parameter itself, and I will do that from now on; I just didn't want to start us off on the wrong foot by muddying the distinction between the Container concept and the particular template type parameter to this particular function template that happens to desire as its argument a concrete class that models the Container concept.

When we implement an abstract algorithm using templates, so that the behavior of the algorithm can be parameterized at compile time by any types modeling the appropriate concepts, we say we are doing generic programming.

Notice that our description of the Container concept didn't mention that we expect the type of the contained elements to be int; and not coincidentally, we find that we can now use our generic double_each_element function even with containers that don't hold int!

    std::vector<double> vecd = {1.0, 2.0, 3.0};
    double_each_element(vecd);

This extra level of genericity is one of the big benefits of using C++ templates for generic programming, as opposed to classical polymorphism. Classical polymorphism hides the varying behavior of different classes behind a stable interface signature (for example, .at(i) always returns int&), but once you start messing with varying signatures, classical polymorphism is no longer a good tool for the job.

Another advantage of generic programming is that it offers blazing speed through increased opportunities for inlining. The classically polymorphic example must repeatedly query the container_of_int object's virtual table to find the address of its particular virtual at method, and generally cannot see through the virtual dispatch at compile time. The template function double_each_element<array_of_int> can compile in a direct call to array_of_int::at or even inline the call completely.

Because generic programming with templates can so easily deal with complicated requirements and is so flexible in dealing with types--even primitive types like int, where classical polymorphism fails--the standard library uses templates for all its algorithms and the containers on which they operate. For this reason, the algorithms-and-containers part of the standard library is often referred to as the Standard Template Library or STL.

Note

That's right--technically, the STL is only a small part of the C++ standard library! However, in this book, as in real life, we may occasionally slip up and use the term STL when we mean standard library, or vice versa.

Let's look at a couple more hand-written generic algorithms, before we dive into the standard generic algorithms provided by the STL. Here is a function template count, returning the total number of elements in a container:

    template<class Container>
    int count(const Container& container)
    {
      int sum = 0;
      for (auto&& elt : container) {
        sum += 1;
      }
      return sum;
    }

And here is count_if, which returns the number of elements satisfying a user-supplied predicate function:

    template<class Container, class Predicate>
    int count_if(const Container& container, Predicate pred) 
    { 
      int sum = 0;
      for (auto&& elt : container) {
        if (pred(elt)) {
            sum += 1;
        }
      }
      return sum;
    }

These functions would be used like this:

    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    assert(count(v) == 8);

    int number_above =
      count_if(v, [](int e) { return e > 5; });
    int number_below =
      count_if(v, [](int e) { return e < 5; });

    assert(number_above == 2);
    assert(number_below == 5);

There is so much power packed into that little expression pred(elt)! I encourage you to try re-implementing the count_if function in terms of classical polymorphism, just to get a sense of where the whole thing breaks down. There are a lot of varying signatures hidden under the syntactic sugar of modern C++. For example, the ranged for-loop syntax in our count_if function is converted (or lowered") by the compiler into a for-loop in terms of container.begin() and container.end(), each of which needs to return an iterator whose type is dependent on the type of container itself. For another example, in the generic-programming version, we never specify--we never need to specify--whether pred takes its parameter elt by value or by reference. Try doing that with a virtual bool operator()!

Speaking of iterators: you may have noticed that all of our example functions in this chapter (no matter whether they were monomorphic, polymorphic, or generic) have been expressed in terms of containers. When we wrote count, we counted the elements in the entire container. When we wrote count_if, we counted the matching elements in the entire container. This turns out to be a very natural way to write, especially in modern C++; so much so that we can expect to see container-based algorithms (or their close cousin, range-based algorithms) arriving in C++20 or C++23. However, the STL dates back to the 1990s and pre-modern C++. So, the STL's authors assumed that dealing primarily in containers would be very expensive (due to all those expensive copy-constructions--remember that move semantics and move-construction did not arrive until C++11); and so they designed the STL to deal primarily in a much lighter-weight concept: the iterator. This will be the subject of our next chapter.

 

Summary


Both classical polymorphism and generic programming deal with the essential problem of parameterizing the behavior of an algorithm: for example, writing a search function that works with any arbitrary matching operation.

Classical polymorphism tackles that problem by specifying an abstract base class with a closed set of virtual member functions, and writing polymorphic functions that accept pointers or references to instances of concrete classes inheriting from that base class.

Generic programming tackles the same problem by specifying a concept with a closed set of requirements, and instantiating function templates with concrete classes modeling that concept.

Classical polymorphism has trouble with higher-level parameterizations (for example, manipulating function objects of any signature) and with relationships between types (for example, manipulating the elements of an arbitrary container). Therefore, the Standard Template Library uses a great deal of template-based generic programming, and hardly any classical polymorphism.

When you use generic programming, it will help if you keep in mind the conceptual requirements of your types, or even write them down explicitly; but as of C++17, the compiler cannot directly help you check those requirements.

 

 

 

 

 

About the Author

  • Arthur O'Dwyer

    Arthur O'Dwyer has used modern C++ in his day job for about ten years--since the days when "modern C++" meant "classic C++." Between 2006 and 2011 he worked on the Green Hills C++ compiler. Since 2014 he has organized a weekly C++ meetup in the San Francisco Bay Area, and he speaks regularly on topics such as those to be found in this book. Later this year, he will attend an ISO C++ committee meeting for the second time.

    This is his first book.

    Browse publications by this author

Latest Reviews

(8 reviews total)
Well written, explained new C++ 17 feature.
Unexpectedly good, this. Mr O'Dwyer offers much more than a churn through what the STL can do. He really knows his C++, and is a fan, and this illuminates his writing. He seasons clear explanations of new STL features with detailed rationales and histories of the features. Particularly liked his backgrounding on streams. With this reference, I look forward to giving the new C++ baubles a run around the block.
Very readable and thorough treatment.

Recommended For You

Book Title
Unlock this full book FREE 10 day trial
Start Free Trial