Search icon CANCEL
Subscription
0
Cart icon
Your Cart (0 item)
Close icon
You have no products in your basket yet
Save more on your purchases now! discount-offer-chevron-icon
Savings automatically calculated. No voucher code required
Arrow left icon
Explore Products
Best Sellers
New Releases
Books
Videos
Audiobooks
Learning Hub
Conferences
Free Learning
Arrow right icon
Mastering the C++17 STL
Mastering the C++17 STL

Mastering the C++17 STL: Make full use of the standard library components in C++17

Arrow left icon
Profile Icon Arthur O'Dwyer
Arrow right icon
AU$36.99 AU$53.99
Book Sep 2017 384 pages 1st Edition
eBook
AU$36.99 AU$53.99
Print
AU$67.99
Subscription
Free Trial
Renews at AU$24.99p/m
Arrow left icon
Profile Icon Arthur O'Dwyer
Arrow right icon
AU$36.99 AU$53.99
Book Sep 2017 384 pages 1st Edition
eBook
AU$36.99 AU$53.99
Print
AU$67.99
Subscription
Free Trial
Renews at AU$24.99p/m
eBook
AU$36.99 AU$53.99
Print
AU$67.99
Subscription
Free Trial
Renews at AU$24.99p/m

What do you get with eBook?

Product feature icon Instant access to your Digital eBook purchase
Product feature icon Download this book in EPUB and PDF formats
Product feature icon Access this title in our online reader with advanced features
Product feature icon DRM FREE - Read whenever, wherever and however you want
Table of content icon View table of contents Preview book icon Preview Book

Mastering the C++17 STL

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 insufficiently abstract 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_ints IS-A container_of_ints (that is, it inherits from container_of_ints and implements the relevant virtual member functions), and a list_of_ints IS-A container_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_ints is a model of the Container concept. This is why I gave the name ContainerModel to the template type parameter in the preceding example.

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.

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.

Left arrow icon Right arrow icon
Download code icon Download Code

Key benefits

  • Boost your productivity as a C++ developer with the latest features of C++17
  • Develop high-quality, fast, and portable applications with the varied features of the STL
  • Migrate from older versions (C++11, C++14) to C++17

Description

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.

What you will learn

  • - Make your own iterator types, allocators, and thread pools.
  • - Master every standard container and every standard algorithm.
  • - Improve your code by replacing new/delete with smart pointers.
  • - Understand the difference between monomorphic algorithms, polymorphic algorithms, and generic algorithms.
  • - Learn the meaning and applications of vocabulary type, product type and sum type.

Product Details

Country selected
Publication date, Length, Edition, Language, ISBN-13
Publication date : Sep 28, 2017
Length 384 pages
Edition : 1st Edition
Language : English
ISBN-13 : 9781787126824
Category :

What do you get with eBook?

Product feature icon Instant access to your Digital eBook purchase
Product feature icon Download this book in EPUB and PDF formats
Product feature icon Access this title in our online reader with advanced features
Product feature icon DRM FREE - Read whenever, wherever and however you want

Product Details

Publication date : Sep 28, 2017
Length 384 pages
Edition : 1st Edition
Language : English
ISBN-13 : 9781787126824
Category :

Packt Subscriptions

See our plans and pricing
Modal Close icon
AU$24.99 billed monthly
Feature tick icon Unlimited access to Packt's library of 7,000+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Simple pricing, no contract
AU$249.99 billed annually
Feature tick icon Unlimited access to Packt's library of 7,000+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Choose a DRM-free eBook or Video every month to keep
Feature tick icon PLUS own as many other DRM-free eBooks or Videos as you like for just AU$5 each
Feature tick icon Exclusive print discounts
AU$349.99 billed in 18 months
Feature tick icon Unlimited access to Packt's library of 7,000+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Choose a DRM-free eBook or Video every month to keep
Feature tick icon PLUS own as many other DRM-free eBooks or Videos as you like for just AU$5 each
Feature tick icon Exclusive print discounts

Frequently bought together

Stars icon
Total AU$ 115.97 168.97 53.00 saved
Mastering the C++17 STL
AU$36.99 AU$53.99
Mastering C++ Multithreading
AU$36.99 AU$53.99
C++17 STL Cookbook
AU$41.99 AU$60.99
=
Book stack Total AU$ 115.97 168.97 53.00 saved Stars icon

Table of Contents

13 Chapters
Preface Chevron down icon Chevron up icon
1. Classical Polymorphism and Generic Programming Chevron down icon Chevron up icon
2. Iterators and Ranges Chevron down icon Chevron up icon
3. The Iterator-Pair Algorithms Chevron down icon Chevron up icon
4. The Container Zoo Chevron down icon Chevron up icon
5. Vocabulary Types Chevron down icon Chevron up icon
6. Smart Pointers Chevron down icon Chevron up icon
7. Concurrency Chevron down icon Chevron up icon
8. Allocators Chevron down icon Chevron up icon
9. Iostreams Chevron down icon Chevron up icon
10. Regular Expressions Chevron down icon Chevron up icon
11. Random Numbers Chevron down icon Chevron up icon
12. Filesystem Chevron down icon Chevron up icon
Get free access to Packt library with over 7500+ books and video courses for 7 days!
Start Free Trial

FAQs

How do I buy and download an eBook? Chevron down icon Chevron up icon

Where there is an eBook version of a title available, you can buy it from the book details for that title. Add either the standalone eBook or the eBook and print book bundle to your shopping cart. Your eBook will show in your cart as a product on its own. After completing checkout and payment in the normal way, you will receive your receipt on the screen containing a link to a personalised PDF download file. This link will remain active for 30 days. You can download backup copies of the file by logging in to your account at any time.

If you already have Adobe reader installed, then clicking on the link will download and open the PDF file directly. If you don't, then save the PDF file on your machine and download the Reader to view it.

Please Note: Packt eBooks are non-returnable and non-refundable.

Packt eBook and Licensing When you buy an eBook from Packt Publishing, completing your purchase means you accept the terms of our licence agreement. Please read the full text of the agreement. In it we have tried to balance the need for the ebook to be usable for you the reader with our needs to protect the rights of us as Publishers and of our authors. In summary, the agreement says:

  • You may make copies of your eBook for your own use onto any machine
  • You may not pass copies of the eBook on to anyone else
How can I make a purchase on your website? Chevron down icon Chevron up icon

If you want to purchase a video course, eBook or Bundle (Print+eBook) please follow below steps:

  1. Register on our website using your email address and the password.
  2. Search for the title by name or ISBN using the search option.
  3. Select the title you want to purchase.
  4. Choose the format you wish to purchase the title in; if you order the Print Book, you get a free eBook copy of the same title. 
  5. Proceed with the checkout process (payment to be made using Credit Card, Debit Cart, or PayPal)
Where can I access support around an eBook? Chevron down icon Chevron up icon
  • If you experience a problem with using or installing Adobe Reader, the contact Adobe directly.
  • To view the errata for the book, see www.packtpub.com/support and view the pages for the title you have.
  • To view your account details or to download a new copy of the book go to www.packtpub.com/account
  • To contact us directly if a problem is not resolved, use www.packtpub.com/contact-us
What eBook formats do Packt support? Chevron down icon Chevron up icon

Our eBooks are currently available in a variety of formats such as PDF and ePubs. In the future, this may well change with trends and development in technology, but please note that our PDFs are not Adobe eBook Reader format, which has greater restrictions on security.

You will need to use Adobe Reader v9 or later in order to read Packt's PDF eBooks.

What are the benefits of eBooks? Chevron down icon Chevron up icon
  • You can get the information you need immediately
  • You can easily take them with you on a laptop
  • You can download them an unlimited number of times
  • You can print them out
  • They are copy-paste enabled
  • They are searchable
  • There is no password protection
  • They are lower price than print
  • They save resources and space
What is an eBook? Chevron down icon Chevron up icon

Packt eBooks are a complete electronic version of the print edition, available in PDF and ePub formats. Every piece of content down to the page numbering is the same. Because we save the costs of printing and shipping the book to you, we are able to offer eBooks at a lower cost than print editions.

When you have purchased an eBook, simply login to your account and click on the link in Your Download Area. We recommend you saving the file to your hard drive before opening it.

For optimal viewing of our eBooks, we recommend you download and install the free Adobe Reader version 9.