Professional C++ Third Edition by Marc Gregoire

Links

Marc Gregoire’s Blog | Cpp Reference (cppreference.com) | Cpp Reference (cplusplus.com/reference) | GNU Project | Open Source Initiative | Open Source Boost Libraries | Open Source Libraries

Part I - Introduction to Professional C++

Chapter 01 - A Crash Course in C++ and the STL

Notes

• A function declaration tells the compiler how a function is called, declaring the number and types of parameters, and the function return type. A definition contains the actual code for the function. In C++, declarations usually go into files with extension .h, known as header files, while definitions usually go into files with extension .cpp, known as source files. A lot of other programming languages do not separate declarations and definitions into separate files, for example C# and Java.
• In C, header files usually end in .h as <stdio.h>. In C++, the suffix is ommitted for standard library headers, such as <iostream>. Standard headers from =C still exist in C++, but with new names. For example, you can access the functionality from <stdio.h> by including <cstdio>.
• Namespaces address the problem of naming conflicts between different pieces of code.
• Most compilers will issue a warning or an error when code is using uninitialized variables. Some compilers will generate code that will report and error at run time.
• C++ does not provide a basic string type. However, a standard implementation of a string is provided as part of the standard library.
• Both C-style arrays and the =std::array=s have a fixed size, which should be known at compile time. They cannot grow or shrink at run time.
• Function declarations are often called “function prototypes” or “signatures” to emphasize that they represent how the function can be accessed, but not the code behind it.
• In C++, unlike C, a function that takes no parameters just has an empty parameter list. It is not necessary to use void to indicate that no parameters are taken. However, you must still use void to indicate when no value is returned.
• Avoid using malloc() and free() from C. Instead, use new and delete, or new[] and delete[].
• Naked, plain old pointers are only allowed if there is no ownership involved. Otherwise, use unique_ptr by default, and shared_ptr if you need shared ownership. If you know about auto_ptr, forget it because the C++ standard has deprecated it.
• In C++ a class defines the characteristics of an object. Classes are usually defined in a header file (.h), while the definitions of its non-inline methods and of any static data members is in a corresponding source file (.cpp).
• To follow the const-correctness principle, it’s always a good idea to declare member functions that do not change any data member of the object as being const. These member functions are also called “inspectors,” compared to “mutators” for non-const member functions.

Warnings

• Never put a using directive or using declaration in a header file, otherwise you force it on everyone that is including your header.
• In C++, the first element of an array is always at position 0, not position 1! The last position of the array is always the size of the array minus 1!
• A pointer must be valid before dereferencing it. A null or uninitialized pointer will cause a crash if dereferenced.
• To prevent memory leaks, every call to new should be paired with a call to delete, and every call to new[] should be paired with a call to delete[]. Pairing a new[] with a delete also causes a memory leak.

Chapter 02 - Working with Strings

Notes

• C++ provides a much-improved implementation of the concept of a string as part of the Standard Library. In C++, std::string is a class (actually an instantiation of the basic_string class template) that supports many of the same functionalities as the <cstring> functions, but takes care of memory allocation for you. The string class is defined in the <string> header in the std namespace.
• Raw string literals are string literals that can span across multiple lines of code, that don’t require escaping of embedded double quotes, and where escape sequences like \t and \n are not processed as escape sequences, but as normal text.

Warnings

• When starting a project in C++, it is very important to decide ahead of time how your group will represent strings.

Chapter 03 - Coding with Style

Notes

• Commenting every line of code is usually untenable, but if the code is complicated enough to require it, don’t just translate the code to English: explain what’s really going on.
• Good code is naturally readable and only requires comments to provide useful additional information.
• Language features exist to help the programmer. Understand and make use of features that contribute to good programming style.

Part II - Professional C++ Software Design

Chapter 04 - Designing Professional C++ Programs

Notes

• The point of designing is to think about your program before you write it.
• Keep in mind that good design is hard, and getting it right takes practice. Don’t expect to become an expert overnight, and don’t be surprised if you find it more difficult to master C++ design than C++ coding.
• A program uses a library but fits into a framework. Libraries provide specific functionality, while frameworks are fundamental to your program design and structure.
• Although people use the terms API and library interchangeably, they are not equivalent. The library refers to the implementation, while the API refers to the published interface to the library.
• Big-O notation applies only to algorithms whose speed depends on their inputs. It does not apply to algorithms that take no input or whose runnign time is random. In practice, you will find that the running times of most algorithms of interest depend on their input, so this limitation is not significant.

Warnings

• Make sure that you understand the license restrictions of any third-party libraries you use if you plan to distribute or sell the code you develop. When in doubt, consult a legal expert.
• Due to time constraints, programmers sometimes find their prototypes morphing into the final product. If you have hacked together a prototype that is insufficient as the basis for the final product, make sure that it doesn’t get used way.

Chapter 05 - Designing with Objects

Notes

• Unlike the procedural approach, which is based on the question What does this program do?, the object-oriented approach asks another question: What real-world objects am I modeling? OOP is based on the notion that you should divide your program not into tasks, but into models of physical objects. While this seems abstract at first, it becomes clearer when you consider physical objects in terms of their classes, components, properties, and behaviors.
• The Has-A Relationship: Objects engaged in a has-a, or aggregation, relationship follow the pattern A has a B, or A contains a B. In this type of relationship, you can envision one object as part of another. Components generally represent a has-a relationship because they describe objects that are made up of other objects.
• The Is-A Relationship (Inheritance): The is-a relationship is such a fundamental concept of object-oriented programming that it has many names, including deriving, subclassing, extending, and inheriting. Classes model the fact that the real world contains objects with properties and behaviors. Inheritance models the fact that these objects tend to be organized in hierarchies. These hierarchies indicate is-a relationships. Fundamentally, inheritance follows the pattern A is a B or A is really quite a bit like B.
• A good object-oriented hierarchy accomplishes the following:
  • Organizes classes into meaningful functional relationships.
  • Supports code reuse by factoring common functionality to base classes.
  • Avoid having derived classes that override much of the parent’s functionality, unless the parent is an abstract class.

Chapter 06 - Designing for Reuse

Notes

• Unfortunately, C++ is fundamentally unfriendly to the principle of good abstraction when writing classes. The syntax requires you to combine your public interfaces and non-public (private or protected) data members and methods together in one class definition, thereby exposing some of the internal implementation details of the class to its clients. Chapter 8 describes some techniques for working around this in order to present clean interfaces.
• Always think about your interfaces from the perspective of someone using them. Do they make sense? Are they what you would expect?

Structuring your code

• Avoid combining unrelated or logically separate concepts: When you design a library or framework, keep it focused on a single task or group of tasks, i.e., strive for high cohesion.
• Divide your programs into logical subsystems: Design your subsystems as discrete components that can be reused independently, i.e., strive for low coupling.
• Use class hierarchies to separate logical concepts: In addition to dividing your program into logical subsystems, you should avoid combining unrelated concepts at the class level. You should also avoid combining unrelated concepts at the level of methods, just as you should do at the class level. Both at the class level and the method level you should strive for high cohesion.
• Use aggregation to separate logical concepts: Aggregation models the has-a relationship: Objects contain other objects to perform some aspects of their functionality. You can use aggregation to separate unrelated or related but separate functionality when inheritance is not appropriate.
• Eliminate user interface dependencies: If your library is a data manipulation library, you want to separate data manipulation from the user interface. This means that for those kinds of libraries you should never assume in which type of user interface the library will be used. As such, do not use cout, cerr, cin, stdout, stderr, or stdin, because if the library is used in the context of a graphical user interface these concepts may make no sense.
• Use templates for generic data structures and algorithms: C++ has a concept called templates allowing you to create structures that are generic with respect to a type or class. The notion of a template is that the type becomes a parameter to the specification, and you can create a single body of code that can work on any type. Templates allow you to write both data structures and algorithms that work on any types.
• Provide appropriate checks and safeguards: There are two opposite styles for writing safe code. The optimal programming style is probably using a healthy mix of both of them. The first is called design-by-contract which means that the documentation for a function or a class represents a contract with a detailed description of what the responsibility of the client code is and what the responsibility of your function or class is. This is often used in the STL. The second style is that you design your functions and classes to be as safe as possible. The most important aspect of this guideline is to perform error checking in your code.

Designing Interfaces

• Develop Easy-To-Use Interfaces: The best strategy for developing easy-to-use interfaces is to follow standard and familiar ways of doing things. When people encounter an interface similar to something they have used in the past, they will understand it better, adopt it more readily, and be less likely to use it improperly. Applied to C++, this strategy implies that you should develop interfaces that follow standards to which C++ programmers are accustomed. For example, C++ programmers expect the constructor and destructor of a class to initialize and clean up an object, respectively. When you design your classes, you should follow this standard. If you require programmers to call initialize() and cleanup() methods for initialization and cleanup instead of placing that functionality in the constructor and destructor, you will confuse everyone who tries to use your class. Because your class behaves differently from other C++ classes, programmers will take longer to learn how to use it and will be more likely to use it incorrectly by forgetting to call initialize() or cleanup().
• Don’t omit required functionality: First, include interfaces for all behaviors that clients could need. This strategy requires you to anticipate all the uses to which clients might put your code. If you are thinking about the interface in one particular way, you might miss functionality that could be needed when clients use it differently. The second part of this strategy is to include as much functionality in the implementation as possible. Don’t require client code to specify information that you already know in the implementation, or could know if you designed it differently.
• Present uncluttered interfaces: Don’t provide unnecessary functionality in your interfaces; keep them clean and simple. It might appear at first that this guideline directly contradicts the previous strategy of avoiding omitting necessary functionality. Although one strategy to avoid omitting functionality would be to include every imaginable interface, that is not a sound strategy. You should include necessary functionality and omit useless or counterproductive interfaces.
• Provide documentation and comments: Regardless of how easy to use you make your interfaces, you should supply documentation for their use. There are two ways to provide documentation for your interfaces: comments in the interfaces themselves and external documentation. You should strive to provide both. Whether you provide comments, external documentation, or both, the documentation should describe the behavior of the library, not the implementation. The behavior includes the inputs, outputs, error conditions and handling, intended uses, and performance guarantees.
• Provide multiple ways to perform the same functionality: In order to satisfy all your “customers,” it is sometimes helpful to provide multiple ways to perform the same functionality. Use this technique judiciously, however, because over application can easily lead to cluttered interfaces.
• Provide customizability: In order to increase the flexibility of your interfaces, provide customizability. Customizability can be as simple as allowing a client to turn on or off error logging. The basic premise of customizability is that it allows you to provide the same basic functionality to every client, but gives clients the ability to tweak it slightly.
• Make common functionality easy to use: When you provide a general-purpose interface, some functionality will be used more often than other functionality. You should make the commonly used functionality easy to use, while still providing the option for the more advanced functionality.

Warnings

• When designing your interface, do not expose implementation details to your clients.

Part III - Coding The Professional Way

Chapter 07 - Gaining Proficiency with Classes and Objects

Notes

• A class definition is a statement in C++, so it must end with a semicolon. If you fail to terminate your class definition with a semicolon, your compiler will probably give you several errors, most of which will appear to be completely unrelated.
• A class can have a number of members. A member is either a member function (which in turn is either a method, constructor, or destructor), or a member variable also called data member.
• In C++, a struct can have methods just like a class. In fact, the only difference is that the default access specifier for a struct is public while the default for a class is private.
• Every normal method call passes a pointer to the object for which it is called as a “hidden” parameter with the name this. You can use this pointer to access data members or call methods, and can pass it to other methods or functions. It is also sometimes useful for disambiguating names. if this is a pointer to the object on which a method executes, then *this is the object itself!
• If you don’t use smart pointers, it is always a good idea to reset a pointer to the null pointer after deleting the object to which it pointed. You are not required to do this, but it will make debugging easier in case the pointer is accidentally used after deleting the object.
• The object life cycle involves three activities: creation, destruction, and assignment. It is important to understand how and when objects are created, destroyed, and assigned, and how you can customize these behaviors.
• C++ supports delegating constructors which allow you to call other constructors from the same class from inside the ctor-initializer.
• There is a special constructor in C++ called a copy constructor that allows you to create an object that is an exact copy of another object. If you don’t write a copy constructor yourself, C++ generates one for you that initializes each data member in the new object from its equivalent data member in the source object. For object data members, this initialization means that their copy constructors are called.
• For performance reasons, it is best to pass objects by const reference instead of by value.
• The assignment operator is sometimes called the copy assignment operator because both the left-hand side and the right-hand side object stay alive after the assignment. This distinction is made because there is also a move assignment operator in which the right-hand side object will be destroyed after the assignment for performance reasons.
• In the world of C++, “copying” only occurs when an object is being initialized. If an object already has a value that is being overwritten, the more accurate term is “assigned” to. Note that the facility that C++ provides for copying is the copy constructor. Since it is a constructor, it can only be used for object creation, not for later assignments to the object. Therefore, C++ provides another method in every class to perform assignment. This method is called the assignment operator. Its name is operator= because it is actually an overloading of the = operator for that class.
• The implementation of the assignment operator is similar to that of a copy constructor, with several important differences. First, a copy constructor is called only for initialization, so the destination object does not yet have valid values. An assignment operator can overwrite the current values in an object. This consideration doesn’t really come into play until you have dynamically allocated memory in your objects. Second, it’s legal in C++ to assign an object to itself. Your assignment operator shouldn’t prohibit self-assignment, but also shouldn’t perform a full assignment if it happens. Thus, assignment operators should check for self-assignment at the beginning of the method and return immediately.

Warnings

• If you allocate an object with new, free it with delete when you are finished with it, or use smart pointers to manage the memory automatically.
• When creating an object on the stack, omit parentheses for the default constructor.
• If you don’t specify any constructors, the compiler will write one for you that doesn’t take any arguments. This compiler-generated default constructor calls the default constructor on all object members of the class, but does not initialize the language primitives such as int and double. Nonetheless, it allows you to create objects of that class. However, if you declare a default constructor, or any other constructor, the compiler no longer generates a default constructor for you.
• A default constructor is the same thing as a 0-argument constructor. The term default constructor does not refer only to the constructor automatically generated if you fail to declare any constructors. It refers to the constructor which is defaulted to if no arguments are required.
• Ctor-initializers allow initialization of data members at the time of their creation. Ctor-initializers initialize data members in the order that they appear in the class definition, not their order in the ctor-initializer.
• Make sure you always free dynamically allocated memory by calling delete or delete[] depending on whether the memory was allocated using new or new[] or better yet, use smart pointers.
• You could actually declare the assignment operator to return whatever type you wanted, including void. However, you should always return a reference to the object on which it is called because that’s what clients expect.

Chapter 08 - Mastering Classes and Objects

Notes

• Whenever you are finished with dynamically allocated memory, you should free it. If you dynamically allocate memory in an object, the place to free that memory is in the destructor. The compiler guarantees that the destructor will be called when the object is destroyed. Normally the destructor frees the memory that was allocated in the constructor. However, no rule requires you to free memory in the destructor. You can write whatever code you want in the destructor, but it is a good idea to use it only for freeing memory or disposing of other resources.
• In assignment operators you must first free the memory referenced by the left-hand side, and then do a deep copy. You can think of an assignment operator as a combination of a destructor and a copy constructor. You are essentially “reincarnating” the object with new life (or data) when you assign to it.
• Next to copying, C++ also supports move semantics, which requires a move constructor and move assignment operator. These can be used to increase performance in certain situations.
• Sometimes when you dynamically allocate memory in your class, it’s easiest just to prevent anyone from copying or assigning to your objects. You can do this by explicitly deleting your operator= and copy constructor. That way, if anyone tries to pass the object by value, return it from a function or method, or assign to it, the compiler will complain. If your compiler doesn’t support explicitly deleting member functions, then you can disallow copying and assigning by making your copy constructor and assignment operator private without any implementation.
• C++ gives you many choices for data members. In addition to declaring simple data members in your classes, you can create static data members that all objects of the class share, const members, reference members, const reference members, and more.
• Data members in your class can be declared const, meaning they can’t be changed after they are created and initialized. You should use static const data members in place of global constants when the constants apply only to the class.
• Destructors will not be called when you thrown an exception from a constructor. Be carefull!
• Non-static data members can also be declared const. Since you cannot assign to a const data member, you need to initialize them in your ctor-initializers.
• A reference cannot exist without referring to something, so a reference data member must be given a value in the ctor-initializer of the constructor. Remember that after you have initialized a reference you cannot change the object to which it refers. It’s not possible to assign to references in the assignment operator.
• There is an important difference between using a const reference versus a non-const reference. The const reference data member can only be used to call const methods on the object. If you try to call a non-const method through a const reference, you will get a compiler error.
• A const object is an object whose value cannot be changed. If you have a const, reference to const or pointer to const object, the compiler will not let you call any methods on that object unless those methods guarantee that they won’t change any data members. The way you guarantee that a method won’t change data members is to mark the method itself with the const keyword. A non-const object can call const and non-const methods. However, a const object can only call const methods. You should get into the habit of declaring const all methods that don’t modify the object so that you can use references to const objects in your program.
• Sometimes you write a method that is “logically” const but happens to change a data member of the object. This modification has no effect on any user-visible data, but is technically a change, so the compiler won’t let you declare the method const. The solution to this is to declare the data member variable mutable, which tells the compiler that it’s okay to change it in a const method.
• Note also that you can overload a method based on const. That is, you can write two methods with the same name and same parameters, one of which is declared const and one of which is not. The compiler will call the const method if you have a const object and the non-const method if you have a non-const object.
• Class definitions can contain more than just member functions and data members. You can also write nested classes and structs, declare typedefs, or create enumerated types. Anything declared inside a class is in the scope of that class. If it is public, you can access it outside the class by scoping it with the ClassName:: scope resolution syntax.
• If you want to define a number of constants inside a class, you should use an enumerated type instead of a collection of #defines.
• C++ allows classes to declare that other classes, or member functions of other classes, or nonmember functions are friends, and can access protected and private data members and methods. friend classes and methods are easy to abuse; they allow you to violate the principle of encapsulation by exposing internals of your class to other classes or functions. Thus, you should use them only in limited circumstances such as operator overloading because in that case you need access to protected and private members.
• In C++, you cannot change the precedence of operators. For example, * and / are always evaluated before + and -. The only thing user-defined operators can do is specify the implementation once the precedence of operations has been determined. C++ also does not allow you to invent new operator symbols.
• Most of the time, performing equality or inequality tests on floating point values is not a good idea. You should use an epsilon test, but this falls outside the scope of this book.
• Provide operator overloading as a service to clients of your class.

Warnings

• Whenever you have dynamically allocated memory in a class, you should write your own copy constructor and assignment operator to provide a deep copy of the memory.
• Whenever a class dynamically allocates memory, write a destructor, copy constructor, and assignment operator.

Chapter 09 - Discovering Inheritance Techniques

Notes

• When you write a class definition in C++, you can tell the compiler that your class is inheriting from, or extending, an existing class. By doing so, your class will automatically contain the data members and methods of the original class, which is called the parent class or base class or superclass. Extending an existing class gives your class (which is now called a derived class or a subclass) the ability to describe only the ways in which it is different from the parent class.
• From the perspective of other code, an object belongs to its defined class as well as to any base classes.
• The private access specifier gives you control over how a potential derived class could interact with your class. I recommend that you make all your data members private by default. You can provide public getters and setters if you want to allow anyone to access those data members, and you can provide protected getters and setters if you only want derived classes to access them. The reason to make data members private by default is that this provides the highest level of encapsulation. This means that you can change how you represent your data while keeping the public and protected interface unchanged. Without giving direct access to data members, you can also easily add checks on the input data in your public and protected setters. Methods should also be private by default. Only make those methods public that are designed to be public, and make methods protected if you only want derived classes to have access to them.
• C++ allows you to mark a class as final, which means trying to inherit from it will result in a compiler error. Also, C++ allows you to mark a method as final which means that the method cannot be overridden in a derived class.
• There is one small twist to overriding methods in C++ and it has to do with the keyword virtual. Only methods that are declared as virtual in the base class can be overridden properly by derived classes.
• As a rule of thumb, make all your methods virtual (including the destructor, but not constructors) to avoid problems associated with omission of the virtual keyword.
• Derived classes retain their overridden methods when referred to by base class pointers or references. They lose their uniqueness when cast to a base class object. The loss of overridden methods and derived class data is called slicing.
• An abstract class provides a way to prevent other code from instantiating an object directly, as opposed to one of its derived classes.
• When overriding from a parent class, a good rule of thumb is to override a method with the exact method declaration, or method prototype, that the base class uses. The implementation can change, but the prototype stays the same. That does not have to be the case, however. In C++, an overriding method can change the return type as long as the original return type is a pointer or reference to a class, and the new return type is a pointer or reference to a descendent class. Such types are called covariant return types. This feature sometimes comes in handy when the base class and derived class work with objects in a parallel hierarchy. That is, another group of classes that is tangential, but related, to the first class hierarchy. A good way to figure out whether you can change the return type of an overridden method is to consider whether existing code would still work, the Liskov substitution principle (LSP).
• It is rare to find a method in a derived class with the same name as a method in the base class but using a different parameter list.
• static methods are scoped by the name of the class in which they are defined, but are not methods that apply to a specific object. A method in a class that calls a static method calls the version determined by normal name resolution. When called syntactically by using an object, the object is not actually involved in the call, except to determine the type at compile time.
• When overriding a method that has a default argument, you should provide a default argument as well, and it should probably be the same value. It is recommended to use a symbolic constant for default values so that the same symbolic constant can be used in derived classes.
• There is no reasonable way (or good reason) to restrict access to a public parent method.
• The only truly useful way to change a method’s access level is by providing a less restrictive accessor to a protected method.
• Relative to other object-oriented languages, C++ is very compile-time oriented. Overriding methods works because of a level of indirection between a method and its implementation, not because the object has built-in knowledge of its own class.
• If you are using typeid other than for logging and debugging purposes, consider re-implementing it using virtual methods.
• Non-public inheritance is rare and I recommend using it cautiously, if for no other reason than because most programmers are not familiar with it.
• Virtual base classes are a great way to avoid ambiguity in class hierarchies. The only drawback is that many C++ programmers are unfamiliar with the concept.

Warnings

• Virtual methods behave differently in constructors. If your derived class has overridden a virtual method from the base class, calling that method from a base class constructor will call the base class implementation of that virtual method and not your overridden version in the derived class.
• Always make your destructors virtual. The compiler generated default destructor is not virtual, so you should define your own virtual destructor, at least for your parent classes.
• Just as with constructors, virtual methods behave differently when called from a destructor. If your derived class has overridden a virtual method from the base class, calling that method from the base class destructor will call the base class implementation of that virtual method and not your overridden version in the derived class.
• When upcasting, use a pointer or reference to the base class to avoid slicing.
• Use downcasting only when necessary and be sure to use dynamic_cast.
• You can always cast up the hierarchy, and you can sometimes cast down the hierarchy. Casting across the hierarchy is possible by changing the behavior of the cast operator, or by using reinterpret_cast, which is not recommended.
• To avoid obscure bugs, you should override all versions of an overloaded method, either explicitly or with the using keyword, but keep the risks of the using clause in mind.
• Overriding private and protected methods is a good way to change certain features of a class without a major overhaul.
• If your derived class does not specify its own copy constructor or operator=, the parent functionality continues to work. If the derived class does provide its own copy constructor or operator=, it needs to explicitly reference the parent versions.
• Attempting to override a non-virtual method will hide the base class definition and will only be used in the context of the derived class.
• Unless you have a specific reason not to, or the class is marked as final, I recommend making all methods, including destructors but not constructors, virtual. Constructors cannot and need not be virtual because you always specify the exact class being constructed when creating an object.
• The typeid operator only works correctly if the class has at least one virtual method. Using dynamic_cast on a class without any virtual method will cause a compiler error.

Chapter 10 - C++ Quirks, Oddities, and Incidentals

Notes

• Using rvalue references, it is possible to pass constants as arguments to functions that employ pass-by-rvalue-reference.
• You should use pass-by-value only for simple built-in types like int and double for which you don’t need to modify the arguments. Use pass-by-reference in all other cases.
• Use references instead of pointers unless you need to change to where the reference refers to.
• An easy-to-remember rule to figure out complicated variable declarations: read from right to left. Take for example int* const ip. Reading this from right to left gives us ip is a const pointer to an int. On the other hand, const int* ip will read as ip is a pointer to a const int.
• Avoid using stand-alone static variables. Maintain state within an object instead.
• C++14 defines the following standard user-defined literals:
  • ”s” for creating std::string; for example: auto myString = "Hello World"s;
  • “h”, “min”, “s”, “ms”, “us”, “ns”, for creating std::chrono::duration time intervals, for example: auto myDuration = 42min;
  • “i”, “il”, “if”, for creating complex numbers complex<double>, complex<long double>, and <complex<float> respectively; for example: auto myComplexNumber = 1.3i;
• It’s recommended to use forward declarations as much as possible in your header files instead of including other headers. This can reduce your compilation and recompilation times, because it breaks dependencies of your header file on other headers. Of course, your implementation file needs to include the correct headers for types that you’ve forward-declared, otherwise it won’t compile.

Warnings

• You must always initialize a reference when it is created. Usually, references are created when they are declared, but reference data members need to be initialized in the constructor initializer for the containing class.
• You cannot change the variable to which a reference refers after it is initialized; you can change only the value of that variable.
• From a function or method, never return a reference to a variable that is locally scoped to that function or method, such as an automatically allocated variable on the stack that will be destroyed when the function ends.
• Your default choice for passing objects as parameters should be const reference. You should only omit const if you explicitly need to change the object.
• Initialization order of non-local variables in different source files is undefined.
• In theory, you could also use reinterpret_cast to cast pointers to ints and ints to pointers, but this is considered erroneous programming, because on many platforms (especially 64-bit platforms) pointers and ints are of different sizes. For example, on a 64-bit platform, pointers are 64 bit, but integers could be 32 bits. Casting a 64-bit pointer to a 32-bit integer will result in losing 32 critical bits!
• Avoid using C-style variable-length argument lists. It is preferable to pass in an std::array or std::vector of values, to use initializer lists, or to use variadic templates for type-safe variable-length argument lists.
• Avoid old C-style pre-processor macros entirely in favor of inline functions.

Chapter 11 - Writing Generic Code with Templates

Notes

• Functions parameterize values. Templates take the concept of parameterization a step further to allow you to parameterize on types as well as values. Just as you use parameter names in functions to represent the arguments that the caller will pass, you use template parameter names (such as T) in templates to represent the types that the caller will specify.
• Class templates define a class where the types of some of the variables, return types of methods, and/or parameters to the methods are specified as parameters. Class templates are useful primarily for containers, or data structures, that store objects.
• In C++, you can write class templates, which allows you to write a class without specifying one or more types. Clients then instantiate the template by specifying the types they want to use. This is called generic programming. The biggest advantage of generic programming is type safety. The types used in the class and its methods are concrete types, and not abstract base classes types as is the case with polymorphic solutions.
• For historical reasons, you can use the keyword class instead of typename to specify template type parameters. Thus, many books and existing programs use syntax like this: template <class T>. However, the use of the word “class” in this context is confusing because it implies that the type must be a class, which is not true. The type can be a class, a struct, a union, a primitive type of the language like int or double, and so on.
• The template <typename T> specifier must precede each method definition for a class template.
• Templates require you to put the implementation of the methods in the header file itself, because the compiler needs to know the complete definition, including the definition of methods, before it can create an instance of the template.
• Normally you put class definitions in a header file and method definitions in a source file. Code that creates or uses objects of the class #includes the header file and obtains access to the method code via the linker. Templates don’t work that way. Because they are “templates” for the compiler to generate the actual methods for the instantiated types, both class template definitions and method definitions must be available to the compiler in any source file that uses them. There are several mechanisms to obtain this inclusion.
  • Template Definitions in Header Files. You can place the method definitions directly in the same header file where you define the class itself. When you #include this file in a source file where you use the template, the compiler will have access to all the code it needs.
  • Template Definitions in a Separate Header File. Alternatively, you can place the template method definitions in a separate header file that you #include in the header file with the class definitions. Make sure the #include for the method definitions follows the class definition; otherwise the code won’t compile.
  • Template Definitions in Source Files. Method implementations look strange in header files. If that syntax annoys you, there is a way that you can place the method definitions in a source file. However, you still need to make the definitions available to the code that uses the templates, which you can do by #includeing the method implementation source file in the class template definition header file. That sounds odd if you’ve never seen it before, but it’s legal in C++. When using this technique, make sure you don’t add the source file to your project, because it is not supposed to be, and cannot be compiled separately; it should be #included only in a header file.
  • Limit Class Template Instantiations. If you want your class templates to be used only with certain known types, you can use the this technique also called “Explicit Instantiation”. With this technique, you disallow client code from using your class template with other types that you don’t explicitly instantiate.
• Non-type template parameters become part of the type specification of instantiated objects.
• C++ allows you to templatize individual methods of a class. These methods can be inside a class template or in a non-templatized class. When you write a templatized class method, you are actually writing many different versions of that method for many different types. Method templates come in useful for assignment operators and copy constructors in class templates. Virtual methods and destructors cannot be method templates.
• Alternate implementations of templates are called template specializations. You might find the syntax to be a little weird. When you write a class template specialization, you must specify that it’s a template, and that you are writing the version of the template for that particular type.
• Class template specialization allows you to write a special implementation for a template with the template types replaced by specific types. Keep in mind that there is also a more advanced feature of specialization called partial specialization.
• When you specialize a template, you don’t “inherit” any code: Specializations are not like derivations. You must rewrite the entire implementation of the class. There is no requirement that you provide methods with the same names or behavior. As a matter of fact, you could write a completely different class with no relation to the original. Of course, that would abuse the template specialization ability, and you shouldn’t do it without good reason.
• You can inherit from class templates. If the derived class inherits from the template itself, it must be a template as well. Alternatively, you can derive from a specific instantiation of the class template, in which case your derived class does not need to be a template.
• Use inheritance for extending implementations and for polymorphism. Use specialization for customizing implementations for particular types.
• You can also write templates for stand-alone functions. Like class template method definitions, function template definitions (not just the prototypes) must be available to all source files that use them. Thus, you should put the definitions in header files if more than one source file uses them.

Chapter 12 - Demystifying C++ I/O

Notes

• Every input stream has an associated source. Every output stream has an associated destination.
• If you get confused between << and >>, just think of the angles as pointing toward their destination. In an output stream, << points toward the stream itself because data is being sent tho the stream. In an input stream, >> points toward the variables because data is being stored.
• You can use the << operator to output a C++ string even though it is not a basic type. In C++, objects are able to prescribe how they are output and input. This is accomplished by overloading the << and >> operator to understand a new type or class.
• The ostringstream class is used to write data to a string, while the istringstream class is used to read data from a string. They are both defined in the <sstream> header file. Because ostringstream and istringstream inherit the same behavior as ostream and istream, working with them is pleasantly similar.
• Tuning an object into a “flattened” type, like a string, is often called marshalling. Marshalling is useful for saving objects to disk or sending them accross a network.
• The main advantage of a string stream over a standard C++ string is that, in addition to data, the object knows where the next read or write operation will take place, also called current position. There may also be performance benefits depending on the particular implementation of string streams. For example, if you need to append a lot of strings together, it might be more efficient to use a string stream, instead of repeatedly calling the += operator on a string object.
• Files lend themselves very well to the stream abstraction because reading and writing files always involves a position in addition to the data. In C++, the ofstream and ifstream classes provide output and input functionality for files. They are defined in the <fstream> header file.
• The seek() and tell() methods are present on all input and output streams, but they rarely make sense outside of the context of file streams. The seek() methods let you move to an arbitrary position within an input or output stream. There are several forms of seek(). The methods of seek() within an input stream are actually called seekg() (the g is for get), and the versions of seek() in an output stream are called seekp() (the p is for put). You might wonder why there is both a seekg() and a seekp() method, instead of one seek() method. The reason is that you can have streams that are both input and output, for example, file streams. In that case, the stream needs to remember both a read position and a separate write position. This is also called bidirectional I/O.
• A link can be established between any input and output streams to give them flush-on-access behavior. In other words, when data is requested from an input stream, its linked output stream will automatically flush. This behavior is available to all streams, but is particularly useful for file streams that may be dependent upon each other. Stream linking is accomplished with the tie() method. To tie an output stream to an input stream, call tie() on the input stream, and pass the address of the output stream. To break the link, pass nullptr. One example of this stream linking is the link between cout and cin. Whenever you try to input data from cin, cout is automatically flushed.
• A bidirectional stream operates as both an input stream and an output stream. Bidirectional streams are deriving from iostream, which in turn derives from both istream and ostream, thus serving as an example of useful multiple inheritance. As you would expect, bidirectional streams support both the >> operator and the << operator, as well as the methods of both input streams and output streams.
• Bidirectional streams have separate pointers for the read position and the write position. When switching between reading and writing, you will need to seek to the appropriate position.

Warnings

• Note that graphical user interface applications normally do not have a console; i.e., if you write something to cout, the user will not see it. If you are writing a library, you should never assume the existence of cout, cin, cerr or, clog because you never know if your library will be used in a console or in a GUI application.

Chapter 13 - Handling Errors

Notes

• Inevitably, your C++ programs will encounter errors. The program might be unable to open a file, the network connection might go down, or the user might enter an incorrect value, to name a few possibilities. The C++ language provides a feature called exceptions to handle these exceptional but not unexpected situations.
• I recommend exceptions as a useful mechanism for error handling. I feel that the structure and error-handling formalization that exceptions provide outweigh the less desirable aspects. Also, many popular libraries, such as the STL and Boost use exceptions, so you need to be prepared to handle them.
• Although by default, streams do not throw exceptions, you can tell the streams to throw exceptions for error conditions by calling their exceptions() method. However, not all compilers give useful information in the stream exceptions they throw. For those compilers it might be better to deal with the stream state directly instead of using exceptions. This book does not use stream exceptions.
• It is recommended to catch exceptions by const reference. This avoids object slicing which could happend when you catch exceptions by value.
• It is also possible to change the behavior of your program if there is an uncaught exception. When the program encounters an uncaught exception, it calls the built-in terminate() function, which calls abort() from <cstdlib> to kill the program. You can set your own terminate_handler by calling set_terminate() with a pointer to a callback function that takes no arguments and returns no value. terminate(), set_terminate(), and terminate_handler are all declared in the <exception> header.
• A function without a throw list can throw exceptions of any type. A function with noexcept shouldn’t throw any exception.
• Since C++11, any exception specification is deprecated, except for noexcept.
• Throw lists don’t prevent functions from throwing unlisted exception types, but they prevent the exception from leaving the function, resulting a run-time error.
• When a function marked as noexcept throws an exception, C++ calls terminate() to terminate the application. When a function throws an exception that is not listed in its throw list, C++ calls a special function unexpected(). The built-in implementation of unexpected() calls terminate().
• Never use throw lists because they are now deprecated, except for noexcept. Instead, document the possible exceptions a function can throw in its code documentation.
• If you write a class whose objects will be thrown as exceptions, you must make those objects copyable. This means that if you have dynamically allocated memory, you must write a destructor, copy constructor, and assignment operator.
• Catch exception objects by reference to avoid unnecessary copying.
• It could happen that during handling of a first exception, a second exceptional situation is triggered which requires a second exception to be thrown. Unfortunately, when you throw the second exception, all information about the first exception that you are currently trying to handle will be lost. The solution provided by C++ for this problem is called nested exceptions, which allow you to nest a caught exception in the context of a new exception. You use std::throw_with_nested() to throw an exception with another exception nested inside it. A catch handler for the second exception can use a dynamic_cast to get access to the nested_exception representing the first exception.
• With smart pointers, you never have to remember to free the underlying resource: the smart pointer destructor does it for you, whether you leave the function via an exception or leave the function normally.
• C++ guarantees that it will run the destructor for any fully constructed “sub-objects”. Therefore, any constructor that completes without an exception will cause the corresponding destructor to be run.

Warnings

• Catch and handle all possible exceptions thrown in your program.
• When you catch exceptions polymorphically, make sure to catch them by reference. If you catch exceptions by value, you can encounter slicing, in which case you lose information from the object.
• Objects thrown as exceptions are always copied by value at least once.
• Careless exception handling can lead to memory and resource leaks (because of stack unwinding).
• Remember, if and exception leaves a constructor, the destructor for that object will never be called!
• Be careful to catch in a destructor any exceptions that can be thrown by calls you make from the destructor. Never allow an exception to leave a destructor.

Chapter 14 - Overloading C++ Operators

Notes

• The operator[] can be used to both set and get elements because it returns a reference to the element. This reference can be used to assign to that element. When operator[] is used on the left-hand side of an assignment statement, the assignment actually changes the value at the given location.
• Although it’s sometimes convenient for operator[] to return an element that can serve as an lvalue, you don’t always want that behavior. It would be nice to be able to provide read-only access to the elements of the array as well, by returning a const value or const reference. C++ provides a way to do this: if you mark the second operator[] with the attribute const, then the compiler can distinguish between the two. If you call operator[] on a const object, it will use the const operator[], and, if you call it on a non-const object, it will use the non-const operator[].
• You cannot overload the subscripting operator to take more than one parameter. If you want to provide subscripting on more than one index, you can use the function call operator.
• You can overload the dereferencing operators for your classes in order to make objects of the classes behave like pointers. The main use of this capability is for implementing smart pointers. It is also useful for iterators, which the STL uses.
• Many programmers prefer operator void*() instead of operator bool().
• C++ gives you the ability to redefine the way memory allocation and deallocation work in your programs. You can provide this customization both on the global level and the class level. This capability is most useful when you are worried about memory fragmentation, which can occur if you allocate and deallocate a lot of small objects. For example, instead of going to the default C++ memory allocation each time you need memory, you could write a memory pool allocator that reuses fixed-size chunks of memory.
• You can overload operator new and operator delete to control memory allocation and deallocation, but you cannot overload the new-expression or the delete-expression. Thus, you can customize the actual memory allocation and deallocation, but not the calls to the constructor and destructor.

Warnings

• You should rarely, if ever, write an implementation of just one of operator* and operator->. You should almost always write both operators together. It would confuse the users of your class if you failed to provide both.
• Unless you know a lot about memory allocation strategies, attempts to overload the memory allocation routines are rarely worth the trouble. Don’t overload them just because it sounds like a neat idea. Only do so if you have a genuine requirement and the necessary knowledge.
• If you fail to heed my advice and decide to replace the global operator new, keep in mind that you cannot put any code in the operator that makes a call to new because this will cause an infinite loop. For example, you cannot write a message to the console with cout. A more useful technique is to overload operator new and operator delete for specific classes. These overloaded operators will be called only when you allocate and deallocate objects of that particular class.
• Whenever you overload operator new, overload the corresponding form of operator delete. Otherwise, memory will be allocated as you specify but freed according to the built-in semantics, which may not be compatible.
• Overload all forms of operator new, or explicitly delete forms that you don’t want to get used.
• If your class declares two identical versions of operator delete except that one takes the size parameter and the other doesn’t, the version without the size parameter will always get called. If you want the version with the size parameter to be used, write only that version.

Chapter 15 - Overview of the C++ Standard Library

Notes

• Technically, the C++ string is a typedef name for a char instantiation of the basic_string template. However, you need not worry about these details; you can use string as if it were a bona fide non-template class.
• The C++ STL containers are homogenous: they allow elements of only one type in each container.
• A vector in C++ is a synonym for a dynamic array: an array that grows and shrinks automatically in response to the number of elements it stores.
• Use a vector instead of a C-style array whenever possible.
• The vector, list, forward_list, deque, and array containers are called sequential containers because they store a sequence of elements.
• Technically, the queue, priority_queue, and stack containers are container adapters. They are simple interfaces built on top of one of the standard sequential containers vector, list, or deque.
• Use a set instead of a vector or list if you need order and want equal performance for insertion, deletion, and lookup.
• The set and map containers are called associative containers becuase they associate keys and values. This term is confusing when applied to sets, because in sets the keys are themselves the valuse. Both containers sort their elements, so they are called sorted or ordered associative containers.
• Note that string is technically a container as well.
• Note that strings are technically containers as well. They can be thought of as vectors of characters. Thus, some of the standard algorithms also work on strings.
• vector should be your default container. In practice, insertion and deletion in a vector is often faster than in a list or forward_list. This is because of how memory and caches work on modern CPUs, and because of the fact that for a list or forward_list you first need to iterate to the position where you want to insert or delete an element. Memory for a list or forward_list might be fragmented, so iteration is slower than for a vector.
• Although the algorithms and containers are theoretically independent, some containers provide certain algorithms in the form of class methods because the generic algorithms do not perform well on those particular containers. For example, sets provide their own find() algorithm that is faster than the generic find() algorithm. You should use the container-specific method form of the algorithm, if provided, because it is generally more efficient or appropriate for the container at hand.
• Iterators mediate between algorithms and containers. They provide a standard interface to traverse the elements of a container in sequence, so that any algorithm can work on any container.
• When examining the list of algorithms, remember that the STL is designed with generality in mind, so it adds generality that might never be used, but which, if required, would be essential. You may not need every algorithm, or need to worry about the more obscure parameters that are there for anticipated generality. It is important only to be aware of what’s available in case you ever find it useful.

Chapter 16 - Understanding Containers and Iterators

Notes

• If you want to store pointers in containers use unique_ptr if the container becomes owner of the pointed-to object, or shared_ptr if the container shares ownership with other owners. Do not use the old deprecated auto_ptr class in containers because it does not implement copying correctly (as far as the STL is concerned).
• The STL containers call the copy constructor and assignment operator for elements often, so make those operations efficient. You can also increase performance by implementing move semantics for your elements.
• Iterators might not be implemented internally as pointers, so it is better to use the term “refers to” instead of “points to” when discussing the elements accessible via an iterator.
• Only the sequential containers, associative containers, and unordered associative containers provide iterators. The container adapters and bitset class do not support iteration over their elements.
• const_iterator and const_reverse_iterator provide read-only access to elements of the container.
• The half-open range concept of iterators also applies to iterator ranges that are passed to container methods such as insert() and erase().
• All vector element accesses run with constant complexity.
• The operator[] on a vector normally returns a reference to the element, which can be used on the left-hand side of assignment statements. If operator[] is called on a const vector object, it returns a reference to a const element, which cannot be used as the target of an assignment.
• Comparing two vectors with operator== or operator!= requires the individual elements to be comparable with operator==. Comparing two vectors with operator<, operator>, operator<=, or operator>= requires the individual elements to be comparable with operator<. If you intend to store objects of a custom class in a vector, make sure to write those operators.
• Use pre-increment instead of post-increment when possible because pre-increment is at least as efficient, and usually more efficient. iter++ must return a new iterator object, while ++iter can simply return a reference to iter.
• If you do not need to modify the elements of a vector, you should use a const_iterator. This rule will make it easier to guarantee correctness of your code and allows compilers to perform certain optimizations.
• There are versions of push_back() and insert() that take an lvalue or an rvalue as parameter. The lvalue versions allocate memory as needed to store the new elements, and store copies of the element arguments. The rvalue versions use move semantics to move ownership of the object to a vector instead of copying the object.
• All STL containers implement move semantics by including a move constructor and move assignment operator. These use rvalue references. A big benefit of this is that you can easily return an STL container from a function by value without performance degradation.
• C++ supports emplace operations on most STL containers, including vector. Emplace means “to put into place.” An example is emplace_back() on a vector object, which does not copy or move anything. Instead, it makes space in the container and constructs the object in place.
• You can think of the vector<bool> specialization as a bit-field instead of a vector. The bitset container provides a more full-featured bit-field implementation than does vector<bool>. However, the benefit of vector<bool> is that it can change size dynamically.
• In practice, the little amount of space saved by packing bools hardly seems worth the extra effort. Even worse, accessing and modifying elements in a vector<bool> is much slower than, for example, in a vector<int>. Many C++ experts recommend avoiding vector<bool> in favor of the bitset, or vector<int> if you need a dynamically sized bit field.
• C++ provides synchronization classes to allow thread-safe access to shared objects. Without explicit synchronization, no STL class can be used safely from multiple threads.
• The head element of the priority_queue is the one with the “highest” priority, by default, determined according to operator< such that elements that are “less” than other elements have lower priority.
• map and the other associative containers do provide a version of insert() that takes an iterator position. However, that position is only a “hint” to the container as to the correct position. The container is not required to insert the element at that position.
• multimaps allow you to insert identical key/value pairs. If you want to avoid this redundacy, you must check explicitly before inserting a new element.
• The lower_bound(), upper_bound(), and equal_range() methods of multimap exist for maps as well, but their usefulness is limited because a map cannot have multiple elements with the same key.
• unordered_multimaps allow you to insert identical key/value pairs. If you want to avoid this redundancy, you must check explicitly before inserting a new element.

Warnings

• Like “real” array indexing, the operator[] on a vector does not provide bounds checking.
• pop_back() does not return the element that it removed. If you want the element you must first retrieve it with back().
• Methods such as insert() and erase() that take a vector range as arguments assume that the beginning and ending iterators refer to elements in the same container, and that the end iterator refers to an element at or past the begin iterator. The methods will not work correctly if these preconditions are not met!
• Reserving space for elements changes the capacity, but not the size. That is, it doesn’t actually create elements. Don’t access elements past a vector’s size.
• The fact that references returned from vector<bool> are really proxies means that you can’t take their addresses to obtain pointers to the actual elements in the container.
• Lists list class on <list> header do not provide random access to elements.
• Splicing is destructive to the list passed as an argument: It removes the spliced elements from one list in order to insert them into the other.
• When you have a choice, use the list specific methods rather than the generic STL algorithms because the former are more efficient. Sometimes you don’t have a choice and you must use the list specific methods; for example, std::sort() requires RandomAccessIterators, which a list does not provide.
• Using plain old pointer types in pairs is risky because the pair copy constructor and assignment operator perform only shallow copies and assignments of pointer types. However, you can safely store smart pointers like shared_ptr in a pair.
• You can modify element valus through non-const iterators, but the compiler will generate an error if you try to modify the key of an element, even through a non-const iterator, because it would destroy the sorted order of the elements in the map.
• Functions such as std::begin() and std::end() only work on stack-based C-style arrays, not on heap-based C-style arrays.

Chapter 17 - Mastering STL Algorithms

Notes

• It is recommended to use lambda expressions, if possible, instead of function objects because lambdas are easier to use and easier to understand.
• It’s recommended to always use the transparent operator functors.
• If you want to compare the elements of two containers of the same type, you can use operator== or operator< instead of equal() or lexicographical_compare(). The algorithms are useful primarly for comparing sequences of elements from different container types.
• transform() and the other modifying algorithms often return an iterator referring to the past-the-end value of the destination range.
• The copy() algorithm allows you to copy elements from one range to another, starting with the first element and proceeding to the last element in the range. The source and destination ranges must be different, but they can overlap. Note that copy() doesn’t insert elements into the destination range. It just overwrites whatever elements were there already. Thus, you can’t use copy() directly to insert elements into a container, only to overwrite elements that were previously in a container.
• The remove() family of functions are stable in that they maintain the order of elements remaining in the container even while moving the retained elements toward the beginning.
• Sometimes you might encounter non-standard macros to find the minimum and maximum. For example, the GNU C Library (glibc) has macros MIN() and MAX(), while the Windows.h header file defines min() and max() macros. Because these are macros, they potentially evaluate one of their arguments twice; whereas std::min() and std::max() evaluate each argument exactly once. Make sure you always use the C++ versions, std::min() and std::max().

Warnings

• If find() fails to find an element, it returns an iterator equal to the end iterator specified in the function call, not the end iterator of the underlying container.
• If a container provides a method with the same functionality as a generic algorithm, you should use the method instead, because it’s faster. For example, the generic find() algorithm runs in linear time, even on a map, while the find() method on a map runs in logarithmic time.
• It is not recommended to capture all variables from the enclosed scope with [=], or [&], or with a capture default, even though it is possible. Instead, you should selectively capture only what’s needed in the lambda capture block.
• The arithmetic function objects are just wrappers around the arithmetic operators. If you use the function objects as callbacks in algorithms, make sure that the objects in your container implement the appropriate operation, such as operator* or operator+.
• Before C++11 there was bind2nd() and bind1st(). Both have been deprecated by C++11. Use lambda expressions or bind() instead.
• The algorithms are allowed to make multiple copies of function object predicates and call different ones for different elements. The function call operator needs to be const; thus, you cannot write functors such that they count on any internal state to the object being consistent between calls.
• Ranges from maps and multimaps cannot be used as destinations of modifying algorithms. These algorithms overwrite entire elements, which in a map consist of key/value pairs. However, maps and multimaps mark the key const, so it cannot be assigned to. The same holds for set and multiset. Your alternative is to use an insert iterator.
• Make sure that your result range is large enough to hold the result of the set operations. For set_union() and set_symmetric_difference(), the result is at most the sum of the sizes of the two input ranges. For set_intersection(), the result is at most the minimum size of the two input ranges, and for set_difference() it’s at most the size of the first range.
• With the set algorithms you can’t use iterator ranges from associative containers, including sets, to store the results because they don’t allow changes to their keys.

Chapter 18 - String Localization and Regular Expressions

Warnings

• Never use regex_search() in a loop to find all occurrences of a pattern in a source string. Instead, use a regex_iterator or regex_token_iterator.
• Never try to create a regex_iterator or regex_token_iterator with a temporary regex object.

Chapter 19 - Additional Library Utilities

Notes

• std::function, defined in the <functional> header file, can be used to create a type that can point to a function, a function object, or a lambda expression; basically anything that is callable. It is called a polymorphic function wrapper. It can be used as a function pointer or as a parameter for a function to implement callbacks. The template parameters for the std::function template look a bit different than most template parameters. Its syntax is as follows: std::function<R(ArgTypes...)>; R is the return value type of the function and ArgTypes is a comma-separated list of argument types for the function.
• Software-based random number generators can never generate truly random numbers and are therefore called pseudo-random number generators because they rely on mathematical formulas to give the impression of randomness.

Warnings

• You need to make sure that you use a good quality seed for your software-based random number generator. If you initialize the random number generator with the same seed every time, you will create the same sequence of random numbers every time. This is why the seed is usually the current system time.

Part IV - Mastering Advanced Features of C++

Chapter 20 - Customizing and Extending the STL

Chapter 21 - Advanced Templates

Notes

• If you want to take a template as a template parameter, you must use a special kind of parameter called a template template parameter. Specifying a template template parameter is sort of like specifying a function pointer parameter in a normal function. Function pointer types include the return type and parameter types of a function. Similarly, when you specify a template template parameter, the full specification of the template template parameter includes the parameters to that template.
• Between all overloaded versions, function template specializations, and specific function template instantiations, the compiler always chooses the “most specific” one to call. If a non-template version is equally specific as a function template instantiation, then the compiler prefers the non-template version.
• In template<typename... Types> the three dots behind typename are not an error. This is the syntax to define a parameter pack for variadic templates. A parameter pack is something than can accept a variable number of arguments. You are allowed to put spaces before and after the three dots.
• It is better to use the syntax template<typename T1, typename... Types> for variadic templates. With this definition, trying to instantiate the template with zero template arguments results in a compiler error.
• Relying on SFINAE (Substitution Failure Is Not An Error) is tricky and complicated. If your use of SFINAE and enable_if selectively disables the wrong overloads in your overload set, you will get cryptic compiler errors, which will be hard to track down.

Warnings

• Non-type parameters (for templates) cannot be objects, or even doubles or floats. There are restricted to integral types, enums, pointers, and reference.

Chapter 22 - Memory Management

Notes

• Some compilers allow variable-sized arrays on the stack. This is not a standard feature of C++.
• There are data structures, such as STL containers, that do dynamically adjust their size and that do know their actual size. You should use these STL containers instead of standard arrays because they are much safer to use.
• You may be wondering whether the first subscript in a two-dimensional array is the x-coordinate or the y-coordinate. The truth is that it doesn’t really matter, as long as you are consistent. A four-by-seven grid could be declared as char board[4][7] or char board[7][4]. For most applications, it is easiest to think of the first subscript as the x-axis and the second as the y-axis.
• The compiler will refuse to perform a static_cast on pointers to different data types If the two pointers you are casting are actually pointing to objects that are related through inheritance, the compiler will permit a static_cast. However, a dynamic_cast is a safer way to accomplish a cast within an inheritance hierarchy.
• Arrays declared using array syntax can be accessed through a pointer. When an array is passed to a function, it is always passed as a pointer.
• The C++ compiler uses the declared types of pointers to allow you to perform pointer arithmetic. If you declare a pointer to an int and increase it by 1, the pointer moves ahead in memory by the size of an int, not by a single byte. This type of operation is most useful with arrays, since they contain homogeneous data that is sequential in memory. Another useful application of pointer arithmetic involves subtraction. Subtracting one pointer from another of the same type gives you the number of elements of the pointed-to type between the two pointers, not the absolute number of bytes between them.
• Pointers to methods and data members usually won’t come up in your programs. However, it’s important to keep in mind that you can’t dereference a pointer to a non-static method or data member without an object. Every so often, you’ll find yourself wanting to try something like passing a pointer to a non-static method to a function such as qsort() that requires a function pointer, which simply won’t work.
• If your program uses smart pointers by copying them, assigning them, or passing them by value as argumetns to functions, the shared_ptr is the perfect solution.
• If you disregard the recommendation for using smart pointers and instead still use dumb pointers, at least set your pointers to nullptr after deallocating their memory. This prevents you from accidentally deleting the same pointer twice or to use an invalid pointer. It’s worth noting that you are allowed to call delete on a nullptr pointer; it simply will not do anything.

Warnings

• In modern C++ you should avoid low-level memory operations as much as possible in favor of modern constructs such as containers and smart pointers.
• As a rule of thumb, every line of code that allocates memory with new and that uses a naked pointer instead of storing the pointer in a smart pointer, should correspond to another line of code that releases the same memory with delete.
• You should never use malloc() and free() in C++. Use only new and delete.
• Do not use realloc() in C++. It is not your friend.
• Always use delete on anything allocated with new, and always use delete[] on anything allocated with new[].
• In modern C++ you should avoid using naked C-style pointers. Thus, instead of storing plain-old dumb pointers in plain-old dumb arrays, you should store smart pointers in modern containers. These smart pointers will automatically deallocate memory associated with them.
• Now that you know all the details to work with arrays, it is recommended to avoid these old C-style arrays as much as possible because they do not provide any memory safety. They are explained here because you will encounter them in legacy code. In new code, you should use the C++ STL containers such as std::array, std::vector, std::list, and so on. For example, use vector<T> for a one-dimensional dynamic array. Use vector<vector<T>> for a two-dimensional dynamic array and so on.
• Arrays are automatically referenced as pointers, but not all pointers are arrays.
• Do not use the old auto_ptr smart pointer anymore. Instead use unique_ptr or shared_ptr.
• Never assign the result of a memory allocation to a dumb pointer. Whatever memory allocation method you use, always immediately give the memory pointer to a smart pointer, unique_ptr or shared_ptr.
• Always use make_unique() to create a unique_ptr, if your compiler supports it.
• Always use make_shared() to create a shared_ptr.
• Never use a shared_ptr to manage a pointer to a C-style array. Use unique_ptr to manage the C-style array, or better yet, use STL containers instead of C-style arrays.

Chapter 23 - Multithreaded Programming with C++

Notes

• By default, accessing cout from different threads is thread-safe and without any data races, unless you have called cout.sync_with_stdio(false) before the first output or input operation. However, even though there are no data races, output from different threads can still be interleaved!
• Thread function arguments are always copied into some internal storage for the thread. Use std::ref() from the <functional> header to pass them by reference.
• Function objects are always copied into some internal storage for the thread. If you want to execute operator() on a specific instance of your function object instead of copying it, you should use std::ref() from the <functional> header to pass your instance by reference.
• You should try to minimize the amount of synchronization, either atomics or explicit synchronization, because it lowers performance.
• It is recommended to limit the time a lock is held as much as possible, otherwise you are blocking other threads for too long.
• A future returned by a call to async() blocks in its destructor until the result is available.

Warnings

• To prevent multithreading problems, try to design your programs so that multiple threads need not read and write to shared memory. Or, use a synchronization method as described in the “Mutual Exclusion” section, or atomic operations described in the “Atomic Operations Library” section.
• In real-world applications, you should avoid using join(), because it causes the thread calling join() to block. Often there are better ways. For example, in a GUI application, a thread that finishes can post a message to the UI thread. The UI thread itself has a message loop processing messages like mouse moves, button clicks, and so on. This message loop can also receive messages from threads, and you can react to them however you want, all without blocking the UI thread with a join() call.
• Do not manually call one of the lock and unlock methods on any of the mutex classes. Mutex locks are resources, and, as all resources, they almost exclusively should be acquired using the RAII (Resource Acquisition Is Initialization) paradigm. The standard defines a number of RAII lock classes. Using them is critical to avoid deadlocks. They automatically unlock a mutex when a lock object goes out of scope, so you don’t need to manually call unlock() at the right time.
• The double-checked locking pattern is explained here because you might encounter it in existing code. Double-checked locking is sensitive to race conditions, cache coherency, and so on; It is hard to get right. It’s recommended to avoid this pattern as much as possible in new code. Instead, use other mechanisms such as simple locks, atomic variables, and call_once() without any double checking.

Part V - C++ Software Engineering

Chapter 24 - Maximizing Software Engineering Methods

Notes

• Is software too new, or is it really a different type of discipline with inherent qualities contributing to the occurrence of bugs, unusable results, and doomed projects?
• The upfront specification of all requirements makes the Waterfall Model unusable for many organizations because it is not dynamic enough.

Chapter 25 - Writing Efficient C++

Notes

• An efficient, or high-performance, program runs as fast as is possible for the particular tasks.
• Language-level efficiency involves using the language as efficiently as possible, for example, passing objects by reference instead of by value. However, this will only get you so far. Much more important is design-level efficiency, which includes choosing efficient algorithms, avoiding unnecessary steps and computations, and selecting appropriate design optimizations. Optimizing existing code, more often than not, involves replacing a bad algorithm or data structure with a better, more efficient one.
• If a function must modify an object, you can pass the object by reference. If the function should not modify the object, you can pass it by const reference.
• Avoid using pass-by-pointer, which is a relatively obsolete method for pass-by-reference, and is a throwback to the C language, rarely suitable for C++ (unless passing nullptr has meaning in your design).
• Since C++11, the language has support for move semantics, which allows you to efficiently return objects by value, instead of using reference semantics. You should implement a move constructor and move assignment operator for your objects, which allow the C++ compiler to use move semantics. With move semantics for your objects, returning them by value from a function will be efficient without incurring large copying costs.
• You should generally attempt to avoid cases in which the compiler is forced to construct temporary objects. Although it is impossible to avoid in some situations, you should at least be aware of the existence of this “feature” so you aren’t surprised by performance and profiling results. Move semantics are also used by the compiler to make working with temporary objects more efficient. That’s another reason to add move semantics to your classes.
• Always keep in mind that maintaining caches takes code, memory, and processing time. On top of that, caches can be a source of subtle bugs. You should only add caching to a particular area when a profiler clearly shows that that area is a performance bottleneck. First write clean and correct code, then profile it, and only then optimize parts of it.

Warnings

• Apply language-level optimizations judiciously. I recommend to make a clean, well-structured design and implementation first. Then use a profiler, and only invest time optimizing those parts that are flagged by a profiler as being a performance bottleneck.
• Objects should rarely be passed by value to a function or method.

Chapter 26 - Conquering Debugging

Notes

• Be careful with logging to much detail. You don’t want to leak intellectual property through your log files.
• The behavior of the standard assert macro depends on the NDEBUG pre-processor symbol: If the symbol is not defined, the assertion takes place, otherwise it is ignored. Compilers often define this symbol when compiling “release” builds. If you want to leave assertions in release builds, you may have to change your compiler settings, or write your own version of assert that isn’t affected by the value of NDEBUG.
• Make sure your program creates crash dumps, also called memory dumps, core dumps, and so on. How you create such dumps is platform dependent, so you should consult the documentation of your platform. A crash dump is often worth more than a thousand bug reports.

Warnings

• The Fundamental Law of Debugging: Avoid bugs when you’re coding, but plan for bugs in your code.
• Macros in C++ should be avoided as much as possible because they can be hard to debug. However, for logging purposes, using a simple macro is acceptable and it makes using the logging code much easier.
• Normally, you should avoid any library functions or macros that can terminate your program. The assert macro is an exception. If an assertion triggers, it means that some assumption is wrong or that something is catastrophically, unrecoverable wrong, and the only sane thing to do is to terminate the application at that very moment, instead of continuing.
• Be careful not to put any code that must be executed for correct program functioning inside assertions. For example, a line like this is probably asking for trouble: assert(myFunctionCall() != nullptr). If a release build of your code strips assertions, then the call to myFunctionCall() is stripped as well.

Appendix A - C++ Interviews

Appendix B - Annotated Bibliography

Appendix C - Standard Library Header Files

References

A reference in C++ is an alias for another variable. All modifications to the reference change the value of the variable to which it refers. You can think of references as implicit pointers that save you the trouble of taking the address of variables and de-referencing the pointer. Alternatively, you can think of references as just another name for the original variable. You can create stand-alone reference variables, use reference data members in classes, accept references as parameters to functions and methods, and return references from functions and methods.

Reference Variables

Reference variables must be initialized as soon as they are created, like this:

int x = 3;
int& xRef = x;
int& emptyRef; // Does Not Compile!

Modifying References

A reference always refer to the same variable to which it is initialized; references cannot be changed once they are created.

int x = 3, y = 4;
int& xRef = x;
xRef = y; // Changes value of x to 4. Doesn't make xRef refer to y.

int x = 3, z = 5;
int& xRef = x;
int& zRef = z;
zRef = xRef; // Assigns values, not references (set the value of z to 3, doesn't change zRef)

References to Pointers and Pointers to References

You can create references to any type, including pointer types. You cannot declare a reference to a reference, or a pointer to a reference.

int* intP;            // intP is a pointer to int
int*& ptrRef = intP;  // ptrRef is a reference to intP
ptrRef = new int;
*ptrRef = 5;

Reference Data Members

Data members of classes can be references. A reference cannot exist without referring to some other variable. Thus, you must initialize reference data members in the constructor initializer, not in the body of the constructor.

class MyClass {
public:
  MyClass(int& ref) : mRef(ref) {}

private:
  int& mRef;
};

Reference Parameters

C++ programmers do not often use stand-alone reference variables or reference data members. The most common use of references is for parameters to functions and methods. Recall that the default parameter-passing semantics are pass-by-value: Functions receive copies of their arguments. When those parameters are modified, the original arguments remain unchanged. References allow you to specify pass-by-reference semantics for arguments passed to the function. When you use reference parameters, the function receives references to the function arguments. If those references are modified, the changes are reflected in the original argument variables.

void swap(int& first, int& second) {
  int temp = first;
  first = second;
  second = temp;
}

int x = 5, y = 6;
int *xp = &x, *yp = &y;

swap(x, y);    // x and y are actually changed through references in swap
swap(*xp, *yp) // x and y are actually changed through references in swap
swap(3, 4);    // Does not Compile!

Reference Return Values

You can also return a reference from a function or method. The main reason to do so is efficiency. Instead of returning a whole object, return a reference to the object to avoid copying it unnecessarily. Of course, you can only use this technique if the object in question will continue to exist following the function termination.

If the type you want to return from your function supports move semantics, discussed later in this chapter, then returning it by value is almost as efficient as returning a reference.

A second reason to return a reference is if you want to be able to assign to the return value directly as an lvalue (the left-hand side of an assignment statement). Several overloaded operators commonly return references.

Rvalue References

In C++, an lvalue is something of which you can take an address; a named variable, for example. The name comes from the fact that they normally appear on the left-hand side of an assignment. An rvalue on the other hand is anything that is not an lvalue such as a constant value, or a temporary object or value. Typically an rvalue is on the right-hand side of an assignment operator.

An rvalue reference is a reference to an rvalue. In particular, it is a concept that is applied when the rvalue is a temporary object. The purpose of an rvalue reference is to make it possible for a particular function to be chosen when a temporary object is involved. The consequence of this is that certain operations that normally involve copying large values can be implemented by copying pointers to those values, knowing the temporary object will be destroyed.

A function can specify an rvalue reference parameter by using && as part of the parameter specification; e.g., type&& name. Normally, a temporary object will be seen as a const type&, but when there is a function overload that uses an rvalue reference, a temporary object can be resolved to that overload.

The const keyword

The keyword const is short for “constant” and specifies that something remains unchanged. The compiler will enforce this requirement by marking any attempt to change it as an error. Furthermore, when optimizations are enabled, the compiler can take advantage of this knowledge to produce better code. The keyword has two related roles. It can mark variables or parameters, and it can mark methods.

const Variables and Parameters

You can use const to “protect” variables by specifying that they cannot be modified. You can mark any variable const, including global variables and class data members. Defining a constant with const is just like defining a variable, except that the compiler guarantees that code cannot change the value.

const double PI = 3.141592653589793238462;
const std::string productName = "Super Hyper Net Modulator";

You can also use const to specify that parameters to functions or methods should remain unchanged.

void mysteryFunction(const std::string* someString) {
  *someString = "Test"; // Will not compile
}

const Pointers

const int* ip; // Same as int const* ip;
ip = new int[10];
ip[4] = 5; // DOES NOT COMPILE! (Cannot change the value to wich ip points)

int* const ip = nullptr; // mark ip itself const (not the values to which it points)
ip = new int[10];        // DOES NOT COMPILE!
ip[4] = 5;               // Error: dereferencing a null pointer

int* const ip = new int[10]; // OK
ip[4] = 5;                   // OK
ip = new int[20];            // DOES NOT COMPILE!

const int* const ip = nullptr; // both the pointer and the values to which it points are const

const References

const applied to references is usually simpler than const applied to pointers for two reasons. First, references are const by default, in that you can’t change to what they refer. So, there is no need to mark them const explicitly. Second, you can’t create a reference to a reference, so there is usually only one level of indirection with references. The only way to get multiple levels of indirection is to create a reference to a pointer.

int z;
int const& zRef = z; // Same as: const int& zRef = z;
zRef = 4; // DOES NOT COMPILE!

By passing a const reference you ensure that no copy is made but the original variable cannot be changed.

void printString(const std::string& someString) {
  std::cout << someString << std::endl;
}

const Methods

You can mark a class method const, which prevents the method from modifying any non-mutable data members of the class.

The constexpr Keyword

Constant expressions are evaluated at compile time.

const int getArraySize() { return 32; }
int main() {
  int myArray[getArraySize()]; // Invalid in C++
  return 0;
}

constexpr int getArraySize() { return 32; }
int main() {
  int myArray[getArraySize()]; // OK
  int mySecondArray[getArraySize() + 5]; // OK
  return 0;
}

Declaring a function as constexpr imposes quite a lot of restrictions on what the function can do because the compiler has to be able to evaluate the function at compile time, and the function is not allowed to have any side effects. Here are a couple of restrictions:

• The function body shall be a single return statement that does not contain a goto statement or a try catch block, and does not throw any exceptions. It is allowed to call other constexpr functions.
• The return type of the function shall be a literal type. It cannot be void.
• If the constexpr function is a member of a class, the function cannot be virtual.
• All the function arguments shall be literal types.
• A constexpr function cannot be called until it’s defined in the translation unit because the compiler needs to know the complete definition.
• dynamic_cast is not allowed.
• new and delete are not allowed.

By defining a constexpr constructor you can create constant expression variables of user-defined types. A constexpr constructor should satisfy the following requirements:

• All the constructor arguments should be literal types.
• The constructor body cannot be a function-try-block.
• The constructor body should satisfy the same requirements as the body of a constexpr function.
• All data members should be initialized with constant expressions.

class Rect {
public:
  constexpr Rect(int width, int height) : mWidth(width), mHeight(height) {}
  constexpr int getArea() const { return mWidth * mHeight; }
private:
  int mWidth, mHeight;
};

int main() {
  constexpr Rect r(8, 2);
  int myArray[r.getArea()]; // OK
  return 0;
}

The static keyword

There are several uses of the keyword static in C++, all seemingly unrelated. Part of the motivation for “overloading” the keyword was attempting to avoid having to introduce new keywords into the language.

static Data Members and Methods

You can declare static data members and methods of classes. static data members, unlike non-static data members, are not part of each object. Instead, there is only one copy of the data member, which exists outside any objects of that class.

static methods are similarly at the class level instead of the object level. A static method does not execute in the context of a specific object.

static Linkage

C++ source files are each compiled independently, and the resulting object files are linked together. Each name in a C++ source file, including functions and global variables, has a linkage that is either internal or external. External linkage means that the name is available from other source files. Internal linkage (also called static linkage) means that it is not. By default, functions and global variables have external linkage. However, you can specify internal (or static) linkage by prefixing the declaration with the keyword static.

An alternative to using static for internal linkage is to employ anonymous namespaces. Instead of marking a variable or function static, wrap it in an unnamed namespace. Entities in an anonymous namespace can be accessed anywhere following their declaration in the same source file, but cannot be accessed from other source files. These semantics are the same as those obtained with the static keyword.

The extern Keyword

A related keyword, extern, seems like it should be the opposite of static, specifying external linkage for the names it precedes. It can be used that way in certain cases. For example, consts and typedefs have internal linkage by default. You can use extern to give them external linkage. However, extern has some complications. When you specify a name as extern, the compiler treats it as a declaration, not a definition. For variables, this means the compiler doesn’t allocate space for the variable. You must provide a separate definition line for the variable without the extern keyword.

static Variables in Functions

The final use of the static keyword in C++ is to create local variables that retain their values between exits and entrances to their scope. A static variable inside a function is like a global variable that is only accessible from that function. One common use of static variables is to “remember” whether a particular initialization has been performed for a certain function.

Types

typedef

A typedef provides a new name for an existing type declaration. You can think of a typedef as syntax for introducing a synonym for an existing type declaration without creating a new type.

typedef int* IntPtr;
int* p1;   // p1 is a pointer to int
IntPtr p2; // p2 is also a pointer to int
p1 = p2;   // they are the same type (compatible)
p2 = p1;   // they are the same type (compatible)

typedef std::vector<std::string> StringVector;
void processVector(const StringVector& vec) { /* omitted */ }
int main() {
  StringVector myVector;
  processVector(myVector);
  return 0;
}

The STL uses typedefs extensively to provide shorter names for types. For example, string is actually a typedef that looks like this: typedef basic_string<char, char_traits<char>, allocator<char>> string;

Type Aliases

Type aliases are easier to understand than typedefs in certain situations.

typedef int MyInt;
using MyInt = int; // same as above

typedef int (*FuncType)(char, double);
using FuncType = int (*)(char, double); // same as above

Alias Templates

You can use a typedef to give another name to a templatized class. However, C++ requires you to specify concrete arguments for each template parameter. Use alias template to be able to specify some of the types only.

template<typename T1, typename T2>
class MyTemplateClass {/* ... */};

typedef MyTemplateClass<int, double> OtherName; // Works as expected

template<typenamt T1>
typedef MyTemplateClass<T1, double> OtherName; // Error

template<typename T1>
using OtherName = MyTemplateClass<T1, double>; // Using alias template works!

Casts

const_cast

You can use const_cast to cast away const-ness of a variable.

extern void ThirdPartyLibraryMethod(char* str);
void f(const char* str) {
  ThirdPartyLibraryMethod(const_cast<char*>(str));
}

static_cast

You can use the static_cast to perform explicit conversions that are supported directly by the language.

int i = 3, j = 4;
double result = static_cast<double>(i) / j;

You can also use static_cast to perform explicit conversions that are allowed because of user-defined constructors or conversions routines. For example, if class A has a constructor that takes an object of class B, you can convert a B object to an A object with a static_cast. In most situations where you want this behavior, however, the compiler will perform the conversion automatically.

Another use for static_cast is to perform downcasts in an inheritance hierarchy. This casts work with both pointers and references, they do not work with objects themselves. Note that these casts with static_cast do not perform run-time type checking. They allow you to convert any Base pointer to a Derived pointer or Base reference to a Derived reference, even if the Base really isn’t a Derived at run time.

class Base {
public:
  Base() {}
  virtual ~Base() {}
};

class Derived : public Base {
public:
  Derived() {}
  virtual ~Derived() {}
};

Base* b;
Derived* d = new Derived();
b = d;                        // Don't need a cast to go up the inheritance hierarchy
d = static_cast<Derived*>(b); // Need a cast to go down the hierarchy

Base base;
Derived derived;
Base& br = derived;
Derived& dr = static_cast<Derived&>(br);

static_casts are not all-powerful. You can’t static_cast pointers of one type to pointers of another unrelated type. You can’t static_cast directly objects of one type to objects of another type. You can’t static_cast a const type to a non-const type. You can’t static_cast pointers to ints. Basically, you can’t do anything that doesn’t make sense according to the type rules of C++.

reinterpret_cast

The reinterpret_cast is a bit more powerful and less safe than the static_cast. You can use it to perform some casts that are not technically allowed by C++ type rules, but which might make sense to the programmer in some circumstances. For example, you can cast a reference to one type to a reference to another type, even if the types are unrelated. Similarly, you can cast a pointer type to any other pointer type, even if they are unrelated by an inheritance hierarchy. This is commonly used to cast a pointer to a void* and back. A void* pointer is just a pointer to some location in memory. No type information is associated with a void* pointer. You should be very careful with reinterpret_cast because it allows you to do conversions without performing any type checking.

class X {};
class Y {};

X x;
Y y;
X* xp = &x;
Y* yp = &y;
// Need reinterpret cast for pointer conversion from unrelated classes
// static_cast doesn't work
xp = reinterpret_cast<X*>(yp);
// No cast required for conversion from pointer to void*
void* p = xp;
// Need reinterpret cast for pointer conversion from void*
xp = reinterpret_cast<X*>(p);
// Need reinterpret cast for reference conversion from unrelated classes
// static_cast doesn't work
X& xr = x;
Y& yr = reinterpret_cast<Y&>(x);

dynamic_cast

The dynamic_cast provides a run-time check on casts within an inheritance hierarchy. You can use it to cast pointers or references. dynamic_cast checks the run-time type information of the underlying object at run time. If the cast doesn’t make sense, dynamic_cast returns a null pointer (for the pointer version) or throws an std::bad_cast exception (for the reference version). Note that the run-time type information is stored in the vtable of the object. Therefore, in order to use dynamic_cast, your classes must have at least one virtual method. If your classes don’t have a vtable, trying to use dynamic_cast will result in a compiler error.

class Base {
public:
  Base() {}
  virtual ~Base() {}
};

class Derived : public Base {
public:
  Derived() {}
  virtual ~Derived() {}
};

// correct use of dynamic_cast
Base* b;
Derived* d = new Derived();
b = d;
d = dynamic_cast<Derived*>(b);

// dynamic cast on references casue an exception to be thrown
Base base;
Derived derived;
Base& br = base;
try {
  Derived& dr = dynamic_cast<Derived&>(br);
} catch (const std::bad_cast&) {
  cout << "Bad cast!\n";
}

Note that you can perform the same casts down the inheritance hierarchy with a static_cast or reinterpret_cast. The difference with dynamic_cast is that it performs run-time (dynamic) type checking, while static_cast and reinterpret_cast will perform the casting even if they are erroneous.

Casting Up and Down

An object can be cast or assigned to its parent class. If the cast or assignment is performed on a plain old object, this results in slicing. However, slicing does not occur if a derived class is assigned to a pointer or reference to its base class.

Super mySuper = mySub;  // Slice!
Super& mySuper = mySub; // No Slice!

Casting from a base class to one of its derived classes, also called downcasting, is often frowned upon by professional C++ programmers because there is no guarantee that the object really belongs to that derived class, and because downcasting is a sign of bad design.

void presumptuous(Super* inSuper) {
  Sub* mySub = static_cast<Sub*>(inSuper); // BAD!!!
  // Proceed to access Sub methods on mySub.
}

void lessPresumptuous(Super* inSuper) {
  Sub* mySub = dynamic_cast<Sub*>(inSuper);
  if (mySub != nullptr) {
    // Proceed to access Sub methods on mySub.
  }
}

Summary of Casts

Situation	Cast
Remove const-ness	const_cast
Explicit cast supported by language (e.g., int to double, int to bool)	static_cast
Explicit cast supported by user-defined constructors or conversions	static_cast
Object of one class to object of another (unrelated) class	Can’t be done
Pointer-to-object of one class to pointer-to-object of another class	dynamic_cast recommended, or
in the same inheritance hierarchy	static_cast
Reference-to-object of one class to reference-to-object of another	dynamic_cast recommended, or
class in the same inheritance hierarchy	static_cast
Pointer-to-type to unrelated pointer-to-type	reinterpret_cast
Reference-to-type to unrelated reference-to-type	reinterpret_cast
Pointer-to-function to pointer-to-function	reinterpret_cast

Type Inference

Type inference allows the compiler to automatically deduce the type of an expression. There are two keywords for type inference: auto and decltype and C++14 add decltype(auto).

The auto keyword

The auto keyword has four completely different meanings:

1. The first meaning is to tell the compiler to automatically deduce the type of a variable at compile time.
2. The second use of the auto keyword is for the alternative function syntax.
3. The third use of the auto keyword is for function return type deduction
4. The fourth use of auto is for generic lambda expressions.

The decltype keyword

The decltype keyword takes an expression as argument, and computes the type of that expression. For example:

int x = 123;
decltype(x) y = 456; // The compiler deduces the type of y to be int because that's the type of x

decltype(auto)

Using auto to deduce the type of an expression strips away reference qualifiers and const qualifiers. decltype does not strip those, but might cause code duplication. C++14 solves this by introducing decltype(auto).

const string message = "Test";
const string& foo() { return message; }

auto f1 = foo();            // f1 is of type string and thus a copy is made.
const auto& f1 = foo();     // explicitely make it a reference and mark it const.
decltype(foo()) f1 = foo(); // f1 is of type const string& but the syntax is ugly.
decltype(auto) f1 = foo();  // f1 is of type const string&.

Smart Pointers

To avoid common memory problems, you should use smart pointers instead of normal “naked” C-style pointers. Smart pointers automatically deallocate memory when the smart pointer object goes out of scope, for example when the function has finished executing.

The difference between shared_ptr and unique_ptr is that shared_ptr is a reference-counted smart pointer, while unique_ptr is not reference counted. This means that you can have several shared_ptr instances pointing to the same dynamically allocated memory and the memory will only be deallocated when the last shared_ptr goes out of scope. shared_ptr is also thread-safe.

unique_ptr on the other hand means ownership. When the single unique_ptr goes out of scope, the underlying memory is freed. Your default smart pointer should be unique_ptr. Use only shared_ptr when you need to share the resource.

std::unique_ptr

The unique_ptr is analogous to an ordinary pointer, except that it will automatically free the memory or resource when the unique_ptr goes out of scope or is deleted. A unique_ptr has sole ownership of the object pointed to.

unique_ptr does not support the normal copy assignment operator and copy constructor, but it does support the move assignment operator and move constructor, which explains why you can return a unique_ptr from a function.

Employee *emp = new Employee;               // normal "naked" pointer
auto emp = std::make_unique<Employee>();    // std::unique_ptr smart pointer (C++14)
std::unique_ptr<Employee> emp(new Employee) // std::unique_ptr smart pointer (C++11)

auto p1 = std::make_unique<int>(42);
std::unique_ptr<int> p2 = p1;              // Error: does not compile. No copy constructor.
std::unique_ptr<int> p3 = std::move(p1);   // OK. Ownership has been moved from p1 to p3.

std::shared_ptr

shared_ptr allows for distributed “ownership” of data. Each time a shared_ptr is assigned, a reference count is incremented indicating there is one more “owner” of the data. When a shared_ptr goes out of scope, the reference count is decremented. When the reference count goes to zero it means there is no longer any owner of the data, and the object referenced by the pointer is freed. You can’t store an array in a shared_ptr.

const_pointer_cast(), dynamic_pointer_cast(), and static_pointer_cast() are functions available to cast shared_ptrs.

auto emp = std::make_shared<Employee>();    // std::shared_ptr smart pointer (C++14)
std::shared_ptr<Employee> emp(new Employee) // std::shared_ptr smart pointer (C++11)

std::shared_ptr<Base> myBasePtr(new Derived);
std::shared_ptr<Derived> myDerivedPtr = std::dynamic_pointer_cast<Derived>(myBasePtr);

std::weak_ptr

You can use a weak_ptr to observe a shared_ptr without incrementing or decrementing the reference count of the linked shared_ptr.

A weak_ptr can contain a reference to memory managed by a shared_ptr. The weak_ptr does not own the memory, so the shared_ptr is not prevented from deallocating the memory. A weak_ptr does not destroy the pointed to memory when it goes out of scope; however, it can be used to determine if the memory has been deallocated by the associated shared_ptr or not. The constructor of a weak_ptr requires a shared_ptr or another weak_ptr as argument. To get access to the pointer stored in a weak_ptr you need to convert it to a shared_ptr. There are two ways to do this:

• Use the lock() method on a weak_ptr instance, which returns a shared_ptr.
• Create a new shared_ptr instance and give a weak_ptr as argument to the shared_ptr constructor.

In both cases, this new shared_ptr will be nullptr if the shared_ptr associated with the weak_ptr has been deallocated in the meantime.

Access Specifiers

Specifier	Meaning	When to Use
public	Any code can call public member function	Behaviors (methods) that you want clients to use.
	or access a public data member of an object.	Access methods for private and protected data
		members.
protected	Any member function of the class can call	“Helper” methods that you don not want clients
	protected member functions and access	to use.
	protected data members. Member functions of
	derived class can access protected members
	of a base class.
private	Only members functions of the class can call	Everything should be private by default,
	private member functions and access private	especially data members. You can provide protected
	data members. Member functions in derived	getters and setters if you only want to allow
	classes cannot access private members from	derived classes access them, and provide public
	a base class.	getters and setters if you want clients to access
		them.

Constructors and Destructors

Summary of Compiler-Generated Constructors

The compiler automatically generates a 0-argument and copy constructor for every class. However, the constructors you define yourself replace these according to the following rules:

If you define…	…then the compiler generates…	…and you can create an object…
[no constructors]	A 0-argument constructor	With no arguments:
	A copy constructor	SpreadsheetCell cell;
		As a copy of another object:
		SpreadsheetCell myCell(cell);
A 0-argument	A copy constructor	With no arguments:
constructor only		SpreadsheetCell cell;
		As a copy of another object:
		SpreadsheetCell myCell(cell);
A copy constructor	No constructors	Theoretically, as a copy of another object.
only		Practically, you can’t create any objects.
A single-argument or	A copy constructor	With arguments:
multi-argument non-		SpreadsheetCell cell(6);
copy constructor only		As a copy of another object:
		SpreadsheetCell myCell(cell);
A 0-argument constructor	A copy constructor	With no arguments:
as well as a single-		SpreadsheetCell cell;
argument or multi-		With arguments:
argument non-copy		SpreadsheetCell myCell(5);
constructor		As a copy of another object:
		SpreadsheetCell anotherCell(cell);

Note the lack of symmetry between the default constructor and the copy constructor. As long as you don’t define a copy constructor explicitly, the compiler creates one for you. On the other hand, as soon as you define any constructor, the compiler stops generating a default constructor. As mentioned before in this chapter, the automatic generation of a default constructor and a default copy constructor can be influenced by defining them as explicitly defaulted or explicitly deleted.

Constructor Order

Objects don’t spring to live all at once; they must be constructed along with their parents and any objects that are contained within them. C++ defines the creation order as follows:

1. If the class has a base class, the default constructor of the base class is executed, unless there is a call to a base class constructor in the ctor-initializer in which case that constructor is called instead of the default constructor.
2. Non-static data members of the class are constructed in the order in which they are declared.
3. The body of the class’s constructor is executed.

These rules can apply recursively. If the class has a grandparent, the grandparent is initialized before the parent, and so on.

Destructor Order

Because destructors cannot take arguments, the language can always automatically call the destructor for parent classes. The order of destruction is conveniently the reverse of the order of construction:

1. The body of the class’s destructor is called.
2. Any data members of the class are destroyed in the reverse order of their construction.
3. The parent class, if any, is destructed.

Again, these rules apply recursively. The lowest member of the chain is always destructed first.

Rule of Six

• Default Constructor
• Copy Constructor
• Move Constructor (C++11 or higher)
• Copy Assignment Operator
• Move Assignment Operator (C++11 or higher)
• Destructor (Should be virtual)

Spreadsheet();                             // ctor
Spreadsheet(const Spreadsheet& src);       // copy ctor
Spreadsheet(Spreadsheet&& src) noexcept;   // move ctor
virtual ~Spreadsheet();                    // destructor

Spreadsheet& operator=(const Spreadsheet& rhs);      // assignment operator
Spreadsheet& operator=(Spreadsheet&& rhs) noexcept;  // move assignment operator

C++ has six methods (four in C++03) with a default behavior. The code for those can be generated by the compiler - saving us from boring routine work and thus preventing oversights. Regarding the six operations, implement as little as possible and declare as much as possible. Any operation not implemented shall be declared as default or delete.

Move semantics for objects requires a move constructor and a move assignment operator. These will be used by the compiler on places where the source object is a temporary object that will be destroyed after the copy or assignment. Both the move constructor and the move assignment operator copy/move the member variables from the source object to the new object and then reset the variables of the source object to null values. By doing this, they are actually moving ownership of the memory from one object to another object. They basically do a shallow copy of the member variables and switch ownership of allocated memory to prevent dangling pointers or memory leaks.

Move semantics is implemented by using rvalue references. To add move semantics to a class, a move constructor and a move assignment operator need to be implemented. Move constructors and move assignment operators should be marked with the noexcept qualifier to tell the compiler that they don’t throw any exceptions. This is particularly important for compatibility with the standard library, as fully compliant implementations of the standard library will only move stored objects if, having move semantics implemented, they also guarantee not to throw.

Obviously, move semantics is useful only when you know that the source object will be destroyed.

Inheritance

Copy Constructor and assignment operator on derived classes

Providing a copy constructor and assignment operator is considered a good programming practice when you have dynamically allocated memory in the class. When defining a derived class, you need to be careful about copy constructors and operator=. If your derived class does not have any special data (pointers, usually) that require a non-default copy constructor or operator=, you don’t need to have one, regardless of whether or not the base class has one. If your derived class omits the copy constructor or operator=, a default copy constructor or operator= will be provided for the data members specified in the derived class and the base class copy constructor or operator= will be used for the data members specified in the base class. On the other hand, if you do specify a copy constructor in the derived class, you need to explicitly chain to the parent copy constructor. If you do not do this, the default constructor (not the copy constructor!) will be used for the parent portion of the object. Similarly, if the derived class overrides operator=, it is almost always necessary to call the parent’s version of operator= as well.

class Super {
public:
  Super();
  Super(const Super& inSuper);
  Super& operator=(const Super& inSuper);
};

class Sub : public Super {
public:
  Sub();
  Sub(const Sub& inSub);
  Sub& operator=(const Sub& inSub);
};

Sub::Sub(const Sub& inSub) : Super(inSub) {}
Sub& Sub::operator=(const Sub& inSub) {
  if (&inSub == this) { return *this; }
  Super::operator=(inSub); // calls parent's operator=
  // Do necessary assignment for derived class
  return *this;
}

Multiple Inheritance

class Baz : public Foo, public Bar {};

By listing multiple parents, the Baz object will have the following characteristics:

• A Baz object will support the public methods and contain the data members of both Foo and Bar.
• The methods of the Baz class will have access to protected data and methods in both Foo and Bar.
• A Baz object can be upcast to either a Foo or a Bar.
• Creating a new Baz object will automatically call the Foo and Bar default constructors, in the order that the classes are listed in the class definition.
• Deleting a Bas object will automatically call the destructors for the Foo and Bar classes, in the reverse order that the classes are listed in the class definition.

Using Interface and Implementation Classes (PIMPL Idiom)

Even with the preceding measures and the best design principles, the C++ language is fundamentally unfriendly to the principle of abstraction. The syntax requires you to combine your public interfaces and private (or protected) data members and methods together in one class definition, thereby exposing some of the internal implementation details of the class to its clients. The downside of this is that if you have to add new non-public methods or data members to your class, all the clients of the class have to be recompiled. This can become a burden in bigger projects.

The good news is that you can make your interfaces a lot cleaner and hide all implementation details, resulting in stable interfaces. The bad news is that it takes a bit of hacking. The basic principle is to define two classes for every class you want to write: the interface class and the implementation class. The implementation class is identical to the class you would have written if you were not taking this approach. The interface class presents public methods identical to those of the implementation class, but it only has one data member: a pointer to an implementation class object. This is called the pimpl idiom, or private implementation idiom. The interface class method implementations simply call the equivalent methods on the implementation class object. The result of this is that no matter how the implementation changes, it has no impact on the public interface class. This reduces the need for recompilation. None of the clients that use the interface class need to be recompiled if the implementation (and only the implementation) changes. Note that this idiom only works if the single data member is a pointer to the implementation class. If it would be a by-value data member, the clients would have to be recompiled when the definition of the implementation class changes.

Generic Code with Templates

Inheritance versus Specialization

Some programmers find the distinction between template inheritance and template specialization confusing. The following table summarizes the differences:

	Inheritance	Specialization
Recuse Code?	Yes: Derived classes contain all	No: You must rewrite all required code in the
	base class data members and methods.	specialization.
Reuse name?	No: The derived class name must be	Yes: The specialization must have the same name as
	different from the base class name.	the original.
Supports	Yes: Objects of the derived class can	No: Each instantiation of a template for a type is
polymorphism?	stand in for objects of the base	a different type.
	class.

IO Streams

All streams can be viewed as data chutes. Streams vary in their direction and their associated source or destination. For example, the cout stream is an output stream, so its direction is “out.” It writes data to the console so its associated destination is “console.” There is another standard stream called cin that accepts input from the user. Its direction is “in,” and its associated source is “console.” Both cout and cin are predefined instances of streams that are defined within the std namespace in C++. The following table gives a brief description of all predefined streams.

Stream	Description
cin	An input stream, reads data from the “input console.”
cout	A buffered output stream, writes data to the “output console.”
cerr	An un-buffered output stream, writes data to the “error console,” which is often the
	same as the “output console.”
clog	A buffered version of cerr.

Output Manipulators

One of the unusual features of streams is that you can throw more than just data down the chute. C++ streams also recognize manipulators, objects that make a change to the behavior of the stream instead of, or in addition to, providing data for the stream to work with. All the manipulators stay in effect for subsequent output to the stream until they are reset, except setw which is only active for the next single output.

boolalpha and noboolalpha

Tells the stream to output bool values as true and false (boolalpha) or 1 and 0 (noboolalpha). The default is noboolalpha.

hex, oct and dec

Outputs numbers in hexadecimal, octal and base 10, respectively.

setprecision

Sets the number of decimal places that are output for fractional numbers. This is a parameterized manipulator (meaning that it takes an argument).

setw

Sets the field width for outputting numerical data. This is a parameterized manipulator.

setfill

Specifies the character that is used to pad numbers that are smaller than the specified width. This is a parameterized manipulator.

showpoint and noshowpoint

Forces the stream to always or never show the decimal point for floating point numbers with no fractional part.

put_money

Writes a formatted money amount to a stream.

put_time

Writes a formatted time to a stream.

quoted

A parameterized manipulator that encloses a given string with quotes and escapes embedded quotes.

Input Manipulators

The built-in input manipulators, described in the list that follows, can be sent to an input stream to customize the way that data is read.

boolalpha and noboolalpha

If boolalpha is used, the string false will be interpreted as a Boolean value false; anything else will be treated as the Boolean value true. If noboolalpha is set, 0 will be interpreted as false, anything else as true. The default is noboolalpha.

hex, oct, and dec

Reads numbers in hexadecimal, octal, and base 10, respectively.

skipws and noskipws

Tells the stream to either skip white space when tokenizing or to read in white space as its own token.

ws

A handy manipulator that simply skips over the current series of white space at the current position in the stream.

get_money

Reads a money amount from a stream.

get_time

Reads a formatted time from a stream.

quoted

A parameterized manipulator that reads a string enclosed with quotes and in which embedded quotes are escaped.

Exceptions

An exception is an unexpected situation. Exceptions come with some new terminology. When a piece of code detects an exceptional situation, it throws an exception. Another piece of code catches the exception and takes appropriate action. Exceptions can get tricky in C++. To use exceptions properly, you need to understand what happens to the stack variables when an exception is thrown, and you have to be careful to properly catch and handle the necessary exceptions. Unlike the Java language, the C++ compiler doesn’t force you to catch every exception that might occur. If your code never catches any exceptions but an exception is thrown, it will be caught by the program itself, which will be terminated.

Memory Allocation Errors

The default behaviors of new and new[] are to throw an exception of type bad_alloc, defined in the <new> header file, if they cannot allocate memory. Your code could catch these exceptions and handle them appropriately. It’s not realistic to wrap all your calls to new and new[] with a try/catch, but at least you should do so when you are trying to allocate a big block of memory.

One consideration is that logging an error might try to allocate memory. If new fails, there might not be enough memory left even to log the error message.

If you don’t like exceptions, you can revert to the old C model in which memory allocation routines return a null pointer if they cannot allocate memory. C++ provides nothrow versions of new and new[], which return nullptr instead of throwing an exception if they fail to allocate memory. This is done by using the syntax new(nothrow) instead of new.

Errors in Constructors

You can throw an exception from a constructor, even though you can’t return a value. With exceptions you can easily tell clients whether or not construction of the object succeeded. However, there is one major problem: if an exception leaves a constructor, the destructor for that object will never be called. Thus, you must be careful to clean up any resources and free any allocated memory in constructors before allowing exceptions to leave the constructor. This problem is the same as in any other function, but it is subtler in constructors because you’re accustomed to letting the destructors take care of the memory deallocation and resource freeing.

Errors in Destructors

You should handle all error conditions that arise in destructors in the destructors themselves. You should not let any exceptions be thrown from destructors, for three reasons:

1. Destructors can run while there is another pending exception, in the process of stack unwinding. If you throw an exception from the destructor in the middle of stack unwinding, the C++ runtime will call std::terminate() to terminate the application. For the brave and curious, C++ does provide the ability to determine, in a destructor, whether you are executing as a result of a normal function exit or delete call, or because of stack unwinding. The function uncaught_exception(), declared in the <exception> header file, returns true if there is an uncaught exception and you are in the middle of stack unwinding. Otherwise, it returns false. However, this approach is messy and should be avoided.
2. What action would clients take? Clients don’t call destructors explicitly: they call delete, which calls the destructor. If you throw an exception from the destructor, what is a client supposed to do? It can’t call delete on the object again, and it shouldn’t call the destructor explicitly. There is no reasonable action the client can take, so there is no reason to burden that code with exception handling.
3. The destructor is your one chance to free memory and resources used in the object. If you waste your chance by exiting the function early due to an exception, you will never be able to go back and free the memory or resources.

Operator Overloading

Limitations to Operator Overloading

• You cannot add new operator symbols. You can only redefine the meanings of operators already in the language.
• There are a few operators that you cannot overload, such as . (member access in an object), :: (scope resolution operator, sizeof, ?: (the conditional operator), and a few others. The table below lists all the operators that you can overload. The operators that you can’t overload are usually not those you would care to overload anyway, so you shouldn’t find this restriction limiting.
• The arity describes the number of arguments, or operands, associated with the operator. You can only change the arity for the function call, new and delete operators. For all other operators you cannot change the arity. Unary operators, such as ++, work on only one operand. Binary operators, such as /, work on two operands. There is only one ternary operator: ?:. The main place where this limitation might bother you is when overloading [] (array brackets).
• You cannot change the precedence or associativity of the operator. These rules determine in which order operators are evaluated in a statement. Again, this constraint shouldn’t be cause for concern in most programs because there are rarely benefits to changing the order of evaluation.
• You cannot redefine operators for built-in types. The operator must be a method in a class, or at least one of the arguments to a global overloaded operator function must be a user-defined type (e.g., a class). This means that you can’t do something ridiculous, such as redefine + for ints to mean subtraction (though you could do so for your classes). The one exception to this rule is the memory allocation and deallocation routines; you can replace the global routines for all memory allocations in your program.

Summary of Overloadable Operators

The following table lists the operators that you can overload, specifies whether they should be methods of the class or global friend functions, summarizes when you should (or should not) overload them, and provides sample prototypes showing the proper return values.

In this table, T is the name of the class for which the overloaded operator is written, and E is a different type. Note that the sample prototypes given are not exhaustive; often there are other combinations of T and E possible for a given operator.

Operator	Name or Category	Friend Function	When to Overload	Sample Prototype
operator+	Binary	Global friend	Whenever you want	friend T operator+(const T&,
operator-	arithmetic	function	to provide these	const T&);
operator*		recommended	operations for	friend T operator+(const T&,
operator/			your class	const E&);
operator%
operator-	Unary arithmetic	Method	Whenever you want	T operator-() const;
operator+	and bitwise	recommended	to provide these
operator~	operators		operations for
			your class
operator++	Pre-increment and	Method	Whenever you	T& operator++();
operator–	pre-decrement	recommended	overload operator+=
			and operator-=
operator++	Post-increment and	Method	Whenever you	T operator++(int);
operator–	post-decrement	recommended	overload operator+=
			and operator-=
operator=	Assignment	Method	Whenever your class	T& operator=(const T&);
	operator	required	has dynamically
			allocated memory or
			resources, or members
			that are references
operator+=	Shorthand	Method	Whenever you overload	T& operator+=(const T&);
operator-=	arithmetic	recommended	the binary arithmetic	T& operator+=(const E&);
operator*=	operator		operators and your
operator/=	assignments		class is not designed
operator%=			to be immutable
operator<<	Binary bitwise	Global friend	Whenever you want to	friend T operator<<(const T&,
operator>>	operators	function	provide these	const T&);
operator&		recommended	operations	friend T operator<<(const T&,
operator					const E&);
operator^
operator<<=	Shorthand bitwise	Method	Whenever you overload	T& operator<<=(const T&);
operator>>=	operator	recommended	the binary bitwise	T& operator<<=(const E&);
operator&=	assignments		operators and your
operator	=			class is not designed
operator^=			to be immutable
operator<	Binary comparison	Global friend	Whenever you want to	friend bool operator<(const T&,
operator>	operators	function	provide these	const T&);
operator<=		recommended	operations	friend bool operator<(const T&,
operator>=				const E&);
operator==
operator!=
operator<<	I/O stream	Global friend	Whenever you want to	friend ostream& operator<<(
operator>>	operators	function	provide these	ostream&, const T&);
	(insertion and	required	operations	friend istream& operator>>(
	extraction)			istream&, T&);
operator!	Boolean negation	Member function	Rarely; use bool or	bool operator!() const;
	operator	recommended	void* conversion
			instead
operator&&	Binary Boolean	Global friend	Rarely	friend bool operator&&(
operator			operators	function		const T& lhs, const T& rhs);
		recommended
operator[]	Subscripting	Method	When you want to	E& operator[](int);
	(array index)	required	support	const E& operator[](int) const;
	operator		subscripting
operator()	Function call	Method	When you want objects	Return type and arguments
	operator	required	to behave like	can vary;
			function pointers
operator	Conversion, or	Method	When you want to	operator type() const;
type()	cast, operators	required	provide conversions
	(separate operator		from your class
	for each type)		to other types
operator	Memory allocation	Method	When you want to	void* operator new(size_t size);
new	routines	recommended	control memory	void* operator new[](
operator			allocation for your	size_t size);
new[]			classes (rarely)
operator	Memory	Method	Whenever you overload	void operator delete(void* ptr)
delete	deallocation	recommended	the memory allocation	noexcept;
operator	routines		routines	void operator delete[](
delete[]				void * ptr) noexcept;
operator*	Dereferencing	Method	Useful for smart	E& operator*() const;
operator->	operators	recommended for	pointers	E* operator->() const;
		operator*
		Method required
		for operator->
operator&	Address-of	N/A	Never	N/A
	operator
operator->*	Dereference	N/A	Never	N/A
	pointer-to-member
operator,	Comma operator	N/A	Never	N/A

The preceding table does not include sample prototypes with rvalue reference semantics. However, for most operators it can make sense to write both a version using normal lvalue references and a version using rvalue references. Whether it makes sense depends on implementation details of your class. The operator= is one example. Another example is operator+ to prevent unnecessary memory allocations.

The logical operators are trickier. It’s not recommended to overload && and ||. These operators don’t really apply to individual types: they aggregate results of Boolean expressions. Additionally, you lose the short-circuit evaluation, because both the left-hand side and the right-hand side have to be evaluated before they can be bound to the parameters of your overloaded operator && and ||. Thus, it rarely makes sense to overload them for specific types.

Big-O Notation

Big-O notation specifies algorithm run time as a function of its input size, also known as the complexity of the algorithm. For example, an algorithm with a performance that is linear as a function of its input size takes twice as long to process twice as many elements. Thus, if it takes 2 seconds to process 500 elements, it will take 4 seconds to process 1000 elements. That is, you could graph the performance versus input size as a straight line. Big-O notation summarizes the algorithm performance like this: O(n). The O just means that you’re using big-O notation, while the n represents the input size. O(n) specifies that the algorithm speed is a direct linear function of the input size.

Algorithm Complexity	Big-O Notation	Explanation	Example Algorithms
Constant	O(1)	Running time is independent of	Accessing a single element in an
		input size.	array.
Logarithmic	O(log n)	The running time is a function	Finding an element in a sorted
		of the logarithm base 2 of the	list using binary search.
		input size.
Linear	O(n)	The running time is directly	Finding an element in an unsorted
		proportional to the input size.	list.
Linear Logarithmic	O(n log n)	The running time is a function of	Merge sort
		the linear times the logarithmic
		function of the input size.
Quadratic	O(n^2)	The running time is a function of	A slower sorting algorithm like
		the square of the input size.	selection sort.
Exponential	O(2^n)	The running time is an	Optimized traveling salesman
		exponential function of the input	problem.
		size.

Big-O notation is sometimes insufficient or even misleading. Consider the following issues whenever you think about big-O performance specifications:

• If an algorithm takes twice as long to work on twice as much data, it doesn’t say anything about how long it took in the first place! If the algorithm is written badly but scales well, it’s still not something you want to use. For example, suppose the algorithm makes unnecessary disk accesses. That probably wouldn’t affect the big-O time but would be very bad for overall performance.
• Along those lines, it’s difficult to compare two algorithms with the same big-O running time. For example, if two different sorting algorithms both claim to be O(n log n), it’s hard to tell which is really faster without running your own tests.
• The big-O notation describes the time complexity of an algorithm asymptotically, as the input size grows to infinity. For small inputs, big-O time can be very misleading. An O(n^2) algorithm might actually perform better than an O(log n) algorithm on small input sizes. Consider your likely input sizes before making a decision.

The Standard Library

Introduction

C++ comes with a standard library, which contains a lot of useful classes that can easily be used in your code. The benefit of using classes from the standard library is that you don’t need to reinvent certain classes and you don’t need to waste time on implementing things that have already been implemented for you. Another benefit is that the classes available in the standard library are heavily tested and verified for correctness by thousands of users. The standard library classes are also tuned for high performance, so using them will most likely result in better performance compared to making your own implementation.

When working with collections take great care of what you store in them. For example, if you return a reference to an object in a collection from some method, it is recommended to not directly store objects in the collection, but pointers or better yet smart pointers to objects, to avoid bizarre aliasing problems, which can be hard to track down. For example, suppose a client stores a reference received by a call to a method that return references from collections. If the collection directly stores objects, this returned reference can become invalid when the collection needs to reallocate memory. Storing pointers or smart pointers in the collection avoids this reference-invalidation problem

STL containers use value semantics on elements. That is, they store a copy of elements that they are given, assign to elements with the assignment operator, and destroy elements with the destructor. Thus, when you write classes that you intend to use with the STL, make sure they are copyable. When requesting an element from the container, a reference to the stored copy is returned. If you prefer reference semantics, you must implement them yourself by storing pointers to elements instead of the elements themselves. When the containers copy a pointer, the result still refers to the same element. For move semantics to work properly with STL containers, the move contructor and the move assignment operator must be marked as noexcept.

Templates are used to allow generic programming. They make it possible to write code that can work with all kinds of objects, even objects unknown to the programmer when writing the code. The obligation of the programmer writing the template code is to specify the requirements of the classes that define these objects; for example, that they have an operator for comparison, or a copy constructor, or whatever is deemed appropriate, and then making sure the code that is written uses only those required capabilities. The obligation of the programmer creating the objects is to supply those operators and methods that the template writer requires.

All the containers in the STL are templates, so you can use them to store any type, from built-in types such as int and double to your own classes. Each container instance stores objects of only one type; that is, they are homogeneous collections. If you need non fixed-sized heterogeneous collections, you could create a class that has multiple derived classes, and each derived class could wrap an object of your required type.

One of the template type parameters for STL containers is a so-called allocator. The container can use this allocator to allocate and deallocate memory for elements. Some containers, such as a map; also accept a comparator as one of the template type parameters. This comparator is used to order elements. Both of these template parameters have default values.

Overview

High level functionality of the STL is shown on the following table:

Functionality	Header Files	Description
Strings	<string>	Build-int string class. Technically a typedef for a char
	<locale>	instantiation of the basic_string template.
Regular expressions	<regex>	Regex make it easy to perform so-called pattern-matching
		often used in text processing.
I/O Streams	<fstream>	C++ introduces a new model for input and output using streams.
	<iomanip>	The C++ library provides routines for reading and writing
	<ios>	built-in types from and to files, console/keyboard, and strings.
	<iosfwd>	C++ also provides the facilities for coding your own routines
	<iostream>	for reading and writing your own objects.
	<istream>
	<ostream>
	<sstream>
	<streambuf>
	<strstream>
Smart Pointers	<memory>	Smart pointers implementation: unique_ptr, shared_ptr, and
		weak_ptr. shared_ptr and weak_ptr are thread-safe.
Exceptions	<exception>	The C++ language supports exceptions, which allow functions or
	<stdexcept>	methods to pass errors of various types up the calling
	<system_error>	functions or methods. The C++ standard library provides a class
		hierarchy of exceptions that you can use in your program as is,
		or that you can derive from to create your own exceptions types.
Mathematical	<complex>	complex number class which provides an abstraction for working
Utilities	<ratio>	with numbers that contain both real and imaginary components.
	<valarray>	ratio class template that can exactly represent any finite
	<limits>	rational number defined by a numerator and denominator.
		valarray class which is similar to vector but more optimized
		for high performance numerical applications.
		numeric_limits class template which provides a standard way to
		obtain information about numeric limits.
Time Utilities	<chrono>	The Chrono library makes it easy to work with time; for example,
		to time certain durations or to perform actions based on timing.
Random Numbers	<random>	Since C++11, a random number library has been added to the
		standard. The new library comes with “random number engines”,
		“random number engine adaptors”, and “random number
		distributions”.
Initializer Lists	<initializer_list>	Initializer lists make it easy to write functions that can
		accept a variable number of arguments.
Pair and Tuple	<utility>	The pair template can store two elements with two different
	<tuple>	types. typle is a generalization of pair.
Function Objects	<functional>	A class that implements a function call operator is called a
		“function object”. Function objects can, for example, be uses as
		predicates for certain STL algorithms.
Multithreading	<thread>	The standard library provides a couple of basic building blocks
	<atomic>	for writing multithreaded code. Individual threads can be
	<condition_variable>	created using the thread class from the <thread> header.
	<mutex>	In multithreaded code you need to take care that several threads
	<future>	are not reading and writing to the same piece of data at the
		same time. To prevent this, you can use atomics defined in
		<atomic>, which give you thread-safe atomic access to a piece
		of data. Other thread synchronization mechanisms are provided by
		<condition_variable> and <mutex>. If you just need to
		calculate something and get the result back with proper exception
		handling, it’s easier to use async and future defined in the
		<future> header that it is to directly use the thread class.
Type Traits	<type_traits>	Type traits provide information about types at compile time. They
		are useful when writing advanced templates.

STL requirements on elements

The specific requirements on elements in containers using the default allocator and comparator are shown in the following table:

Method	Description	Notes
Copy	Creates a new element that is “equal” to the	Uses every time you insert an element,
Constructor	old one, but that can safely be destructed	except when using an emplace method.
	without affecting the old one.
Move	Creates a new element by moving all content	Used when the source element is an rvalue,
Constructor	from a source element to the new element.	and will be destroyed after the
		construction of the new element; also used
		when a vector grows in size, for example.
Assignment	Replaces the contents of an element with a	Used every time you modify an element.
Operator	copy of the source element.
Move	Replaces the contents of an element by	Used when the source element is an rvalue,
Assignment	moving all content from a source element.	and will be destroyed after the assignment
Operator		operation.
Destructor	Cleans up an element.	Used every time you remove an element, or,
		for example, when a vector grows in size
		and the elements are not movable.
Default	Constructs an element without any arguments.	Required only for certain operations, such
Constructor		as the vector::resize() method with one
		argument, and the map::operator[] access.
operator==	Compares two elements for equality.	Required for keys in unordered containers,
		and for certain operations, such as
		operator== on two containers.
operator<	Determines if one element is less than	Required for keys in associative
	another.	containers and for certain operations,
		such as operator< on two containers.

Iterators

The STL uses the iterator pattern to provide a generic abstraction for accessing the elements of the containers. Each container provides a container-specific iterator, which is a glorified smart pointer that knows how to iterate over the elements of that specific container. You can think of an iterator as a pointer to a specific element of the container. Like pointers to elements in an array, iterators can move to the next element with operator++. Similarly, you can usually use operator* and operator-> on the iterator to access the actual element or field of the element. Some iterators allow comparison with operator== and operator!=, and support operator-- for moving to previous elements.

All iterators must be copy constructible, copy assignable, and destructible. Lvalues of iterators must be swappable. The standard defines five categories of iterators:

Iteraotr Category	Operations Required	Comments
Read (Input Iterator)	operator++	Provides read-only access, forward only (no operator--
	operator*	to move backward).
	operator->	Iterators can be assigned, copied, and compared for
	copy constructor	equality.
	operator=
	operator==
	operator!=
Write (Output Iterator)	operator++	Provides write-only access, forward only.
	operator*	Iterators can be assigned, but cannot be compared
	copy constructor	for equality.
	operator=	Note the absence of operator->.
Forward Iterator	Capabilities of	Provides read/write access, forward only.
	input iterators,	Iterators can be assigned, copied, and compared for
	plus: default	equality.
	constructor
Bidirectional Iterator	Capabilities of	Provides everything forward iterators provide.
	forward interators,	Iterators can also move backward to previous element.
	plus: operator–
Random Access Iterator	Bidirectional	Equivalent to dumb pointers: Iterators support pointer
	capability,	arithmetic, array index syntax, and all forms of
	plus:	comparison.
	operator+
	operator-
	operator+=
	operator-=
	operator<
	operator>
	operator<=
	operator>=
	operator[]

There is no formal class hierarchy of these iterators, because the implementations for each container are not part of the standard hierarchy. However, one can deduce a hierarchy based on the functionality they are required to provide. Specifically, every random access iteraotr is also bidirectional, every bidirectional iterator is also forward, and every forward iterator is also input and output.

Additionally, you can use std::distance() to compute the distance between two iterators of a container.

Every container class in the STL that supports iterators provide public typedefs for its iterator types called iterator and const_iterator. For example, a const iterator for a vector of ints has as type std::vector<int>::const_iterator. Containers that allow you to iterate over its elements in reverse order also provide public typedefs called reverse_iterator and const_reverse_iterator.

The containers also provide a method begin() that returns an iterator referring to the first element in the containers. The end() method returns an iterator to the “past-the-end” value of the sequence of elements. That is, end() returns an iterator that is equal to the result of applying operator++ to an iterator referring to the last element in the sequence. Together begin() and end() provide a half-open range that includes the first element but not the last: [begin,end).

Iterator Methods:

• begin() and end() methods that return non-const iterators.
• cbegin() and cend() methods that return const iterators.
• rbegin() and rend() methods that return non-const reverse iterators.
• crbegin() and crend() methods that return const reverse iterators.

Iterator global non-member functions (Recommended):

• std::begin() and std::end() (since c++11)
• std::cbegin() and std::cend() (since c++14)
• std::rbegin() and std::rend() (since c++14)
• std::crbegin() and std::crend() (since c++14)

Iterator Adapters

The Standard Library provides four iterator adapters: special iterators built on top of other iterators. All four iterator adapters are defined in the <iterator> header.

Reverse Iterators

The STL provides a reverse_iterator class that iterates through a bidirectional or random-access iterator in a reverse direction. Every reversible container in the STL, which happens to be every container that’s part of the standard except forward_list and the unordered associative containers, supplies a typedef reverse_iterator and methods called rbegin() and rend(). The method rbegin() returns a reverse_iterator pointing to the last element of the container, and rend() returns a reverse_iterator pointing to the element before the first element of the container. Applying operator++ to a reverse_iterator calls operator-- on the underlying container iterator, and vice versa.

The reverse_iterator is useful mostly with algorithms in the STL that have no equivalents that work in reverse order. For example, the basic find() algorithm searches for the first element in a sequence. If you want to find the last element in the sequence, you can use a reverse_iterator instead. Note that when you call an algorithm such as find() with a reverse_iterator, it returns a reverse_iterator as well. You can always obtain the underlying iterator from a reverse_iterator by calling the base() method on the reverse_iterator. However, due to the implementation details of reverse_iterator, the iterator returned from base() always refers to one element past the element referred to by the reverse_iterator on which it’s called.

Stream Iterators

The STL provides adapters that allow you to treat input and output streams as input and output iterators. Using these iterators, you can adapt input and output streams so that they can serve as sources and destinations, respectively, in the various STL algorithms. The ostream_iterator class is an output stream iterator. It is a template class that takes the element type as a type parameter. Its constructor takes an output stream and a string to write to the stream following each element. The ostream_iterator class writes elements using operator<<.

Similarly, you can use the input stream iterator, istream_iterator, to read values from an input stream using the iterator abstraction. Elements are read using operator>>. An istream_iterator can be used as sources in the algorithms and container methods.

Insert Iterators

Algorithms like copy() don’t insert elements into a container; they simply replace old elements in a range with new ones. In order to make algorithms like copy() more useful, the STL provides three insert iterator adapters that actually insert elements into a container. They are templatized on a container type, and take the actual container reference in their constructor. By supplying the necessary iterator interfaces, these adapters can be used as the destination iterators of algorithms like copy(). However, instead of replacing elements in the container, they make calls on their container to actually insert new elements.

The basic insert_iterator calls insert(position, element) on the container, the back_insert_iterator calls push_back(element), and the front_insert_iterator calls push_front(element).

One huge benefit of insert_iterator is that it allows you to use associative containers as destinations of the modifying algorithms. Chapter 17 explains that the problem with associative containers is that you are not allowed to modify the elements over which you iterate. By using an insert_iterator, you can instead insert elements, allowing the container to sort them properly internally. Associative containers actually support a form of insert() that takes an iterator position, and are supposed to use the position as a “hint,” which they can ignore. When you use an insert_iterator on an associative container, you can pass the begin() or end() iterator of the container to use as the hint.

Move Iterators

Move semantics can be used to prevent unnecessary copying in cases where you know that the source object will be destroyed after an assignment or copy construction. There is an iterator adapter called move_iterator (which can be created calling the function make_move_iterator()). The dereferencing operator for a move_iterator automatically converts the value to an rvalue reference, which means that the value can be moved to a new destination without the overhead of copying. Before you can use move semantics, you need to make sure your objects are supporting it.

STL Containers Overview

Sequential Containers

vector

The STL vector container is similar to a standard C-style array: the elements are stored in contiguous memory, each in its own “slot.” You can index into a vector, as well as add new elements to the back or insert them anywhere else. Inserting and deleting elements into and from a vector generally takes linear time, though these operations actually run in amortized constant time at the end of a vector. Random access of individual elements has a constant complexity.

The vector iterator is random access, which means that you can move it backward or forward, or jump around.

A vector stores copies of the objects, and its destructor calls the destructor for each of the objects. The copy constructor and assignment operator of the vector class perform deep copies of all the elements in the vector. Thus, for efficiency, you should pass vectors by reference or const reference to functions and methods. In addition to normal copying and assignment, vectors provide an assign() method that removes all the current elements and adds any number of new elements. This method is useful if you want to reuse a vector.

You can remove elements from any point in a vector with erase() and you can remove all elements with clear(). There are two forms of erase(): one accepting a single iterator to remove a single element, and one accepting two iterators specifying a range of elements to remove. If you want to remove a number of elements that satisfy a certain condition, one solution would be to write a loop iterating over all the elements and erasing every element that matches the condition. However, this solution has quadratic complexity, which is very bad for performance. In this case, the quadratic complexity can be avoided by using the remove-erase-idiom, which has a linear complexity.

Inserting or erasing elements in a vector causes all subsequent elements to shift up or down to make room for, or fill in the holes left by, the affected elements. Thus, these operations take linear complexity. Furthermore, all iterators referring to the insertion or removal point or subsequent positions are invalid following the action. The iterators are not “magically” moved to keep up with the elements that are shifted up or down in the vector — that’s up to you.

Also keep in mind that an internal vector reallocation can cause invalidation of all iterators referring to elements in the vector, not just those referring to elements past the point of insertion or deletion.

vector provides two methods for obtaining information about its size: size() and capacity(). The size() method returns the number of elements in a vector, while capacity() returns the number of elements that it can hold without a reallocation. Thus, the number of elements that you can insert without causing a reallocation is capacity() – size(). You can query whether a vector is empty with the empty() method. A vector can be empty but have nonzero capacity.

One way to preallocate space is to call reserve(), which allocates enough memory to hold the specified number of elements. Another way to preallocate space is to specify, in the constructor or with the resize() method, how many elements you want a vector to store. This method actually creates a vector of that size (and probably of that capacity).

deque

deque (abbreviation for double-ended queue) is almost identical to vector, but is used far less frequently. It is defined in the <deque> header file. The principle differences are as follows:

• Elements are not stored contiguously in memory.
• A deque supports true constant-time insertion and removal of elements at both the front and the back (a vector supports amortized constant time at just the back).
• A deque provides push_front(), pop_front(), and emplace_front(), which the vector omits.
• A deque does not expose its memory management scheme via reserve() or capacity().

list

The STL list class, defined in the <list> header file, is a standard doubly linked list. It supports constant-time insertion and deletion of elements at any point in the list, but provides slow (linear) time access to individual elements. In fact, the list does not even provide random-access operations like operator[]. Only through iterators can you access individual elements.

A list iterator is bidirectional, not random access like a vector iterator. That means that you cannot add and subtract list iterators from each other, or perform other pointer arithmetic on them. For example, if p is a list iterator, you can traverse through the elements of the list by doing ++p or --p, but you cannot use the addition or subtraction operator; p+n or p-n does not work.

A list supports the same add element and remove element methods as a vector, including push_back(), pop_back(), emplace(), emplace_back(), the five forms of insert(), the two forms of erase(), and clear(). Like a deque, it also provides push_front(), emplace_front(), and pop_front(). The amazing thing about a list is that all these methods (except for clear()) run in constant time, once you’ve found the correct position. Thus, a list is appropriate for applications that perform many insertions and deletions from the data structure, but do not need quick index-based element access.

Like deques, and unlike vectors, lists do not expose their underlying memory model. Consequently, they support size(), empty() and resize(), but not reserve() or capacity(). Note that the size() method on a list has constant complexity, which is not the case for the size() method on a forward_list.

The linked-list characteristics of a list allow it to splice, or insert, an entire list at any position in another list in constant time.

forward_list

A forward_list, defined in the <forward_list> header file, is similar to a list except that it is a singly linked list while a list is a doubly linked list. This means that forward_list supports only forward iteration and, because of this, ranges need to be specified differently compared to a list. If you want to modify any list, you need access to the element before the first element of interest. Since a forward_list does not have an iterator that supports going backward, there is no easy way to get to the preceding element. For this reason, ranges that will be modified; for example, ranges supplied to erase() and splice(), must be open at the beginning. The begin() function seen earlier returns an iterator to the first element and thus can be used only to construct a range that is closed at the beginning. The forward_list class therefore defines a before_begin() method, which returns an iterator that points to an imaginary element before the beginning of the list. You cannot dereference this iterator as it points to invalid data. However, incrementing this iterator by one will make it the same as the iterator returned by begin(); so it can be used to make a range that is open at the beginning.

array

An array, defined in the <array> header file, is similar to a vector except that it is of a fixed size; it cannot grow or shrink in size. The purpose of this is to allow an array to be allocated on the stack, rather than always demanding heap access as vector does. Just like vectors, arrays support random-access iterators, and elements are stored in contiguous memory.

It has support for front(), back(), at(), and operator[]. It also supports a fill() method to fill the array with a specific element. Because it is fixed in size, it does not support push_back(), pop_back(), insert(), erase(), clear(), resize(), reserve(), and capacity(). A disadvantage compared to a vector is that the swap() method of an array runs in linear time while it has constant complexity for a vector. arrays can also not be moved in constant time, while vectors can. An array has a size() method, which is a clear advantage over C-style arrays. Note that the array declaration requires two template parameters; the first specifies the type of the elements, and the second specifies the fixed number of elements in the array.

Container Adapters

queue

The queue container adapter, defined in the header file <queue>, provides standard “first-in, first-out” (FIFO) semantics. As usual, it’s written as a class template, which looks like this:

template <class T, class Container = deque<T>> class queue;

The T template parameter specifies the type that you intend to store in the queue. The second template parameter allows you to stipulate the underlying container that the queue adapts. However, the queue requires the sequential container to support both push_back() and pop_front(), so you have only two built-in choices: deque and list. For most purposes, you can just stick with the default deque.

The queue interface is extremely simple: there are only eight methods plus the constructor and the normal comparison operators. The push() and emplace() methods add a new element to the tail of the queue, and pop() removes the element at the head of the queue. You can retrieve references to, without removing, the first and last elements with front() and back(), respectively. As usual, when called on const objects, front() and back() return const references; and when called on non-const objects they return non-const (read/write) references. The queue also supports size(), empty(), and swap().

priority_queue

A priority queue is a queue that keeps its elements in sorted order. Instead of a strict FIFO ordering, the element at the head of the queue at any given time is the one with the highest priority. This element could be the oldest on the queue or the most recent. If two elements have equal priority, their relative order in the queue is undefined.

The priority_queue container adapter is also defined in <queue>. Its template definition looks something like this (slightly simplified):

template <class T, class Container = vector<T>, class Compare = less<T>>;

The priority_queue provides even fewer operations than does the queue. The push() and emplace() methods allow you insert elements, pop() allowrs you to remove elements, and top() returns a const reference to the head element. Like the queue, the priority_queue supports size(), empty() and swap(). However, it does not provide any comparison operators.

top() returns a const reference even when called on a non-const object, because modifying the element might change its order, which is not allowed. The priority_queue provides no mechanism to obtain the tail element.

stack

A stack is almost identical to a queue, except that it provides first-in, last-out (FILO) semantics, also known as last-in, first-out (LIFO), instead of FIFO. It is defined in the <stack> header file. The template definition looks like this:

template <class T, class Container = deque<T>> class stack;

You can use vector, list, or deque as the underlying container for the stack.

Like the queue, the stack provides push(), emplace(), and pop(). The difference is that push() adds a new element to the top of the stack , “pushing down” all elements inserted earlier, and pop() removes the element from the top of the stack, which is the most recently inserted element. The top() method returns a const reference to the top element if called on a const object and a non-const reference if called on a non-const object. The stack also supports empty(), size(), swap(), and the standard comparison operators.

Associative Containers

map

A map, defined in the <map> header file, stores key/value pairs instead of just single values. Insertion, lookup, and deletion are all based on the key; the value is just “along for the ride.” The term “map” comes from the conceptual understanding that the container “maps” keys to values.

A map keeps elements in sorted order, based on the keys, so that insertion, deletion, and lookup all take logarithmic time. Because of the order, when you enumerate the elements, they come out in the ordering imposed by the type’s operator< or a user-defined comparator. It is usually implemented as some form of balanced tree, such as a red-black tree. However, the tree structure is not exposed to the client.

You should use a map whenever you need to store and retrieve elements based on a “key” and you would like to have them in a certain order.

The map template takes four types: the key type, the value type, the comparison type, and the allocator type. The comparison type is similar to the comparison type for priority_queue. It allows you to specify a different comparison class than the default. When using the default, make sure that your keys all respond to operator< appropriately.

multimap

A multimap is a map that allows multiple elements with the same key. Like maps, multimaps support uniform initialization. The interface is almost identical to the map interface, with the following changes:

• multimaps do not provide operator[]. The semantics of this operator do not make sense if there can be multiple elements with a single key.
• Inserts on multimaps always succeed. Thus, the multimap insert() method that adds a single element returns only an iterator.

The trickiest aspect of multimaps is looking up elements. You can’t use operator[], because it is not provided. find() isn’t very useful because it returns an iterator referring to any one of the elements with a given key (not necessarily the first element with that key).

However, multimaps store all elements with the same key together and provide methods to obtain iterators for this sub-range of elements with the same key in the container. The lower_bound() and upper_bound() methods each return a single iterator referring to the first and one-past-the-last elements matching a given key. If there are no elements matching that key, the iterators returned by lower_bound() and upper_bound() will be equal to each other.

If you need to obtain both iterators bounding the elements with a given key, it’s more efficient to use equal_range() instead of calling lower_bound() followed by calling upper_bound(). equal_range() returns a pair of the two iterators that would be returned by lower_bound() and upper_bound().

set

A set, defined in <set>, is very similar to a map. The difference is that instead of storing key/value pairs, in sets the value itself is the key. sets are useful for storing information in which there is no explicit key, but which you want to have in sorted order without any duplicates, with quick insertion, lookup, and deletion.

The interface supplied by set is almost identical to that of map. The main difference is that set doesn’t provide operator[].

You cannot change the key/value of elements in a set because modifying elements of a set while they are in the container would destroy the order.

multiset

A multiset is to a set what a multimap is to a map. A multiset supports all the operations of a set, but it allows multiple elements that are equal to each other to be stored in the container simultaneously.

Unordered associative containers or hash tables

unordered_map

unordered_map is defined in <unordered_map> as a class template:

template <class Key,
          class T,
          class Hash = hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T>>>
class unordered_map;

As with a normal map, all keys in an unordered_map should be unique. The method load_factor() returns the average number of elements per bucket to give you an indication on the number of collisions. The bucket_count() method returns the number of buckets in the container. It also provides a local_iterator and const_local_iterator allowing you to iterate over the elements in a single bucket; but, these may not be used to iterate across buckets. The bucket(key) method returns the index of the bucket that contains the given key; begin(n) returns a local_iterator referring to the first element in the bucket with index n, and end(n) returns a local_iterator referring to one-past-the-last element in the bucket with index n.

unordered_multimap

An unordered_multimap is an unordered_map that allows multiple elements with the same key. Their interfaces are almost identical, with the following changes:

• unordered_multimaps do not provide operator[]. The semantics of this operator do not make sense if there can be multiple elements with a single key.
• Inserts on unordered_multimaps always succeed. Thus, the unordered_multimap::insert() method that adds a single element returns only an iterator.

As discussed earlier with multimaps, looking up elements in unordered_multimaps cannot be done using operator[] because it is not provided. You can use find() but it returns an iterator referring to any one of the elements with a given key (not necessarily the first element with that key). Instead, it’s best to use the equal_range() method, which returns a pair of iterators: one referring to the first element matching a given key and one referring to one-past-the-last element matching a given key. The use of equal_range() is exactly the same as discussed for multimaps

unordered_set

The <unordered_set> header file defines unordered_set and unordered_multiset, which are very similar to set and multiset, respectively; except that they do not sort their keys and that they use a hash function. The differences between unordered_set and unordered_map are similar to the differences between set and map.

unordered_multiset

The <unordered_set> header file defines unordered_set and unordered_multiset, which are very similar to set and multiset, respectively; except that they do not sort their keys and that they use a hash function. The differences between unordered_set and unordered_map are similar to the differences between set and map.

Other Containers

Standard C-Style Arrays

Recall that “dumb” pointers are bona fide iterators because they support the required operators. This point is more than just a piece of trivia. It means that you can treat standard C-style arrays as STL containers by using pointers to their elements as iterators. Standard C-style arrays, of course, don’t provide methods like size(), empty(), insert(), and erase(), so they aren’t true STL containers. Nevertheless, because they do support iterators through pointers, you can use them in any algorithms or methods that supports iterators. Remember that the name of an array alone is interpreted as the address of the first element, the iterator referring to the end must be one-past-the-last element, so it’s the address of the first element plus the array size.

Strings

You can think of a string as a sequential container of characters. Thus, it shouldn’t be surprising to learn that a C++ string is a full-fledged sequential container. It contains begin() and end() methods that return iterators into the string, insert(), push_back() and erase() methods, size(), empty(), and all the rest of the sequential container basics. It resembles a vector quite closely, even providing methods reserve() and capacity().

In addition to the STL sequential container methods, strings provide a whole host of useful methods and friend functions. The string interface is actually quite a good example of a cluttered interface.

Streams

Input and output streams are not containers in the traditional sense: they do not store elements. However, they can be considered sequences of elements, and as such share some characteristics with STL containers. C++ streams do not provide any STL-related methods directly, but the STL supplies special iterators called istream_iterator and ostream_iterator that allow you to “iterate” through input and output streams.

bitset

A bitset is a fixed-length abstraction of a sequence of bits. A bit can represent only two values, 1 and 0, which can be referred to as on/off, true/false, etc. A bitset also uses the terminology set and unset. You can toggle or flip a bit from one value to the other.

A bitset is not a true STL container: it’s of fixed size, it’s not templatized on an element type, and it doesn’t support iteration. However, it’s a useful utility, which is often lumped with the containers.

A bitset, defined in <bitset>, is templatized on the number of bits it stores. The default constructor initializes all fields of a bitset to 0. An alternative constructor creates a bitset from a string of 0 and 1 characters.

You can adjust the values of individual bits with the set(), reset(), and flip() methods, and you can access and set individual fields with an overloaded operator[]. Note that operator[] on a non-const object returns a proxy object to which you can assign a Boolean value, call flip(), or complement with . You can also access individual fields with the ~test() method. Additionally, you can stream bitsets with the normal insertion and extraction operators. A bitset is streamed as a string of 0 and 1 characters.

In addition to the basic bit manipulation routines, a bitset provides implementations of all the bitwise operators: & , | , ^ , ~ , << , >> , &= , |= , ^= , <<= , and >>=. They behave just as they would on a “real” sequence of bits.

STL Containers Reference

vector

Stores a sequence of elements and provides random access to these elements. You can think of a vector as an array of elements that grows dynamically as you insert elements, and provides some bounds checking. Like an array, the elements of a vector are stored in contiguous memory.

Header: <vector> Container class name: vector Container type: Sequential Insertion Performance: Amortized O(1) at end; O(N-p) for an insert at position p Deletion Performance: O(1) at end; O(N-p) for a delete at position p Lookup Performance: O(1) When to Use: Need quick lookup. Don’t mind slower insertion/deletion. Whenever you would use a standard C-style array that should dynamically grow/shrink in size

list

Double linked list structure. Like an array or vector, it stores a sequence of elements. However, unlike an array or vector, the elements of a list are not necessarily in contiguous memory. Instead, each element in the list specifies where to find the next and previous elements in the list (usually via pointers).

Header: <list> Container class name: list Container type: Sequential Insertion Performance: O(1) once you are at the position where to insert the element Deletion Performance: O(1) once you are at the position where to delete the element Lookup Performance: O(N); Statistically O(N/2) When to Use: Need quick insertion/deletion. Don’t mind slower lookup

forward_list

Singly linked list.

Header: <forward_list> Container class name: forward_list Container type: Sequential Insertion Performance: O(1) once you are at the position where to insert the element Deletion Performance: O(1) once you are at the position where to delete the element Lookup Performance: O(N); Statistically O(N/2) When to Use: When you need the benefits of a list but require only forward iteration

deque

Double-ended queue although it behaves more like a vector instead of a queue.

Header: <deque> Container class name: deque Container type: Sequential Insertion Performance: Amortized O(1) at beginning or end; O(min(N-p, p)) for an insert at position p Deletion Performance: O(1) at beginning or end; O(min(N-p, p)) for a delete at position p Lookup Performance: O(1) When to Use: Not usually needed; use a vector or list instead

array

Replacement for standard C-style arrays.

Header <array> Container class name: array Container type: Sequential Insertion Performance: N/A Deletion Performance: N/A Lookup Performance: O(1) When to Use: When you need a fixed-size array to replace a standard C-style array

queue

Standard first in, first out (FIFO) container. A queue is a container in which you insert elements at one end and take them out at the other end.

Header: <queue> Container class name: queue Container type: Container Adapter Insertion Performance: Depends on the underlying container; O(1) for list, amortized O(1) for deque Deletion Performance: Depends on the underlying container; O(1) for list and deque Lookup Performance: N/A When to Use: When you want FIFO structure

priority_queue

Provides queue functionality in which each element has a priority. Elements are removed from the queue in priority order. In the case of priority ties, the order in which elements are removed is undefined.

Header: <queue> Container class name: priority_queue Container type: Container Adapter Insertion Performance: Depends on the underlying container; amortized O(log(N)) for vector and deque Deletion Performance: Depends on the underlying container; O(log(N)) for vector and deque Lookup Performance: N/A When to Use: When you want a queue with priority

stack

Provides standard first-in, last-out (FILO) semantics, also known as last-in, first-out (LIFO). Like a queue, elements are inserted and removed from the container. However, in a stack, the most recent element inserted is the first one removed.

Header: <stack> Container class name: stack Container type: Container Adapter Insertion Performance: Depends on the underlying container; O(1) for list, amortized O(1) for vector and deque Deletion Performance: Depends on the underlying container; O(1) for list, vector and deque Lookup Performance: N/A When to Use: When you want FILO/LIFO structure

set and multiset

Set of elements loosely analogous to the notion of a mathematical set: Each element is unique, and there is at most one instance of the element in the set. The elements are kept in order. Note that a set does not allow duplicate elements. That is, each element in the set must be unique. If you want duplicate elements, you must use a multiset, also defined in the <set> header file.

Header: <set> Container class name: set, multiset Container type: Sorted Associative Insertion Performance: O(log(N)) Deletion Performance: O(log(N)) Lookup Performance: O(log(N)) When to Use: When you want a sorted collection of elements with equal lookup, insertion, and deletion times

map and multimap

Stores key/value pairs. A map keeps its elements in sorted order, based on the key values, not the object values. A multimap is a map that allows duplicate keys.

Header: <map> Container class name: map, multimap Container type: Sorted Associative Insertion Performance: O(log(N)) Deletion Performance: O(log(N)) Lookup Performance: O(log(N)) When to Use: When you want a sorted collection to associate keys with values with equal lookup, insertion, and deletion times.

unordered_set and unordered_multiset

An unordered_set is similar to a standard set except that the standard set sorts its elements while the unordered_set doesn’t sort its elements.

Header: <unordered_set> Container class name: unordered_set, unordered_multiset Container type: Unordered associative / hash table Insertion Performance: Average case O(1); worst case O(N) Deletion Performance: Average case O(1); worst case O(N) Lookup Performance: Average case O(1); worst case O(N) When to Use: When you want a collection of elements with equal lookup, insertion, and deletion times and don’t require the elements to be sorted. Performance can be better than with normal set but that depends on the elements

unordered_map and unordered_multimap

An unordered_map is similar to a standard map except that the standard map sorts its elements while the unordered_map doesn’t sort its elements.

Header: <unordered_map> Container class name: unordered_map, unordered_multimap Container type: Unordered associative / hash table Insertion Performance: Average case O(1); worst case O(N) Deletion Performance: Average case O(1); worst case O(N) Lookup Performance: Average case O(1); worst case O(N) When to Use: When you want to associate keys with values with equal lookup, insertion, and deletion times and don’t require the elements to be sorted. Performance can be better than with normal map but that depends on the elements.

bitset

This is not a container in the normal sense, in that it does not implement a specific data structure in which you insert and remove elements; they have a fixed size and don’t support iterators. You can think of them as a sequence of Boolean values that you can read and write.

Header: <bitset> Container class name: bitset Container type: Special Insertion Performance: N/A Deletion Performance: N/A Lookup Performance: N/A When to Use: When you want a collection of flags

STL Algorithms

Overview

The “magic” behind the algorithms is that they work on iterator intermediaries instead of on the containers themselves. In that way, they are not tied to specific container implementations. All the STL algorithms are implemented as function templates, where the template type parameters are usually iterator types. The iterators themselves are specified as arguments to the function. Templatized functions can usually deduce the template types from the function arguments, so you can generally call the algorithms as if they were normal functions, not templates.

Algorithms pose certain requirements on iterators passed to it. For instance, copy_backward() is an example of an algorithm that requires a bidirectional iterator, and stable_sort() is an example of an algorithm requiring random access iterators. This means that such algorithms cannot work on containers that do not provide the necessary iterators. forward_list is an example of a container supporting only forward iterators, no bidirectional or random access iterators, thus copy_backward() and stable_sort() cannot work on forward_list.

Most algorithms are defined in the <algorithm> header file, while some numerical algorithms are defined in <numeric>. All of them are in the std namespace.

Just like STL containers, STL algorithms are also optimized to use move semantics at appropriate times. This can greatly speed up certain algorithms; for example, sort(). For this reason, it is highly recommended that you implement move semantics in your custom element classes that you want to store in containers. Move semantics can be added to any class by implementing a move constructor and a move assignment operator. Both should be marked as noexcept, because they should not throw exceptions.

Non-Modifying Sequence Algorithms

The non-modifying algorithms are those that look at a sequence of elements and return some information about the elements. As “non-modifying” algorithms, they cannot change the values of elements or the order of elements withing the sequence. With these algorithms, you should rarely need to write a for loop to iterate over a sequence of values.

Search Algorithms

These algorithms do not require the sequence to be sorted.

Algorithm Name	Algorithm Synopsis	Complexity
adjacent_find()	Finds the first of two consecutive elements that are equal to each	Linear
	other or are equivalent to each other as specified by a predicate.
find()	Finds the first element that matches a value or causes a predicate	Linear
find_if()	to return true.
find_first_of()	Like find, except searches for one of several elements at the same	Quadratic
	time.
find_if_not()	Finds the first element that causes a predicate to return false.	Linear
search()	Finds the first (search()) or last (find_end()) subsequence in a	Quadratic
find_end()	sequence that matches another sequence or whose elements are
	equivalent, as specified by a predicate.
search_n()	Finds the first instance of n consecutive elements that are equal	Linear
	to a given value or relate to that value according to a predicate.

Comparison Algorithms

The following comparison algorithms are provided. None of them require the source sequences to be ordered. All of them have a linear worst-case complexity.

Algorithm Name	Algorithm Synopsis
equal()	Determines if two sequences are equal by checking if parallel elements are
	equal or match a predicate.
mismatch()	Returns the first element in each sequence that does not match the element
	in the same location in the other sequence.
lexicographical_compare()	Compares two sequences to determine their “lexicographical” ordering.
	Compares each element of the first sequence with its equivalent element in
	the second. If one element is less than the other, that sequence is
	lexicographically first. If the elements are equal, compares the next
	elements in order.

Utility Algorithms

Algorithm Name	Algorithm Synopsis
all_of()	Returns true if the predicate returns true for all the elements in the sequence or if
	the sequence is empty; false otherwise.
any_of()	Returns true if the predicate returns true for at least one element in the sequence;
	false otherwise.
none_of()	Returns true if the predicate returns false for all the elements in the sequence or
	if the sequence is empty; false otherwise.
count()	Counts the number of elements matching a value or that cause a predicate to return
count_if()	true.

Modifying Sequence Algorithms

The modifying algorithms modify some or all of the elements in a sequence. Some of them modify elements in place, so that the original sequence changes. Others copy the results to a different sequence so that the original sequence is unchanged. All of them have a linear worst-case complexity.

General

Algorithm Name	Algorithm Synopsis
copy()	Copies elements from one sequence to another.
copy_backward()
copy_if()	Copies elements for which a predicate returns true from one sequence to another.
copy_n()	Copies n elements from one sequence to another.
fill()	Sets all elements in the sequence to a new value.
fill_n()	Sets the first n elements in the sequence to a new value.
generate()	Calls a specified function to generate a new value for each element in the sequence.
generate_n()	Calls a specified function to generate a new value for the first n elements in the
	sequence.
move()	Moves elements from one sequence to another. This uses efficient move semantics.
move_backward()
remove()	Removes elements that match a given value or that cause a predicate to return true,
remove_if()	either in place or by copying the results to a different sequence.
remove_copy()
remove_copy_if()
replace()	Replaces all elements matching a value or that cause a predicate to return true with
replace_if()	a new element, either in place or by copying the results to a different sequence.
replace_copy()
replace_copy_if()
reverse()	Reverses the order of the elements in the sequence, either in place or by copying
reverse_copy()	the results to a different sequence.
rotate()	Swaps the first and second “halves” of the sequence, either in place or by copying
rotate_copy()	the results to a different sequence. The two subsequences to be swapped need not be
	equal in size.
shuffle()	Shuffles the sequence by randomly reordering the elements. It is possible to
random_shuffle()	specify the properties of the random number generator used for shuffling.
	random_shuffle() is deprecated since C++14.
transform()	Calls a unary function on each element of a sequence or a binary function on
	parallel elements of two sequences.
unique()	Removes consecutive duplicates from the sequence, either in place or by copying
unique_copy()	results to a different sequence.

Operational Algorithms

Algorithm Name	Algorithm Synopsis
for_each()	Executes a function on each element in the sequence. This algorithm has a linear
	complexity and does not require the source sequence to be ordered.

Swap Algorithms

Algorithm Name	Algorithm Synopsis
iter_swap()	Swaps two elements or sequences of elements.
swap_ranges()
swap()	Swaps two values, defined in the <utility> header.

Partition Algorithms

Algorithm Name	Algorithm Synopsis	Complexity
is_partitioned()	Returns true if all elements for which a predicate returns true	Linear
	are before all elements for which it returns false.
partition()	Sorts the sequence such that all elements for which a predicate	Linear
	returns true are before all elements for which it returns false,
	without preserving the original order of the elements within
	each partition.
stable_partition()	Sorts the sequence such that all elements for which a predicate	Linear
	returns true are before all elements for which it returns false,	Logarithmic
	while preserving the original order of the elements within each
	partition.
partition_copy()	Copies elements from one sequence to two different sequences. The	Linear
	target sequence is selected based on the result of a predicate,
	either true or false.
partition_point()	Returns an iterator such that all elements before this iterator	Logarithmic
	return true for a predicate and all elements after this iterator
	return false for that predicate.

Sorting Algorithms

The STL provides several variations of sorting algorithms. A “sorting algorithm” reorders the contents of a container such that an ordering is maintained between sequential elements of the collection. Thus, it applies only to sequential collections. Sorting is not relevant to associative containers because they already maintain elements in a sorted order. Sorting is not relevant to the unordered associative containers either because they have no concept of ordering. Some containers, such as list and forward_list, provide their own sorting methods because these can be implemented more efficiently than a general sort mechanism. Consequently, the general sorting algorithms are most useful only for vectors, deques, and arrays.

Algorithm Name	Algorithm Synopsis	Complexity
is_sorted()	Checks if a sequence is sorted or which subsequence is sorted.	Linear
is_sorted_until()
nth_element()	Relocates the nth element of the sequence such that the element in	Linear
	the position pointed to by nth is the element that would be in that
	position if the whole range were sorted, and it rearranges all elements
	such that all elements preceding the nth element are less than the new
	nth element, and the ones following it are greater than the new nth
	element.
partial_sort()	Partially sorts the sequence: The first n elements (specified by	Linear
partial_sort_copy()	iterators) are sorted; the rest are not. They are sorted either in	Logarithmic
	place or by copying them to a new sequence.
sort()	Sorts elements in place, either preserving the order of duplicates	Linear
stable_sort()	elements or not.	Logarithmic

Binary Search Algorithms

The following binary search algorithms require the sequence to be at least partitioned on the element that is searched for. This could, for example, be achieved by applying std::partition(). A sorted sequence also meets this requirement. All these algorithms have logarithmic complexity.

Algorithm Name	Algorithm Synopsis
lower_bound()	Finds the beginning, (lower_bound()), end (upper_bound()), or both sides (equal_range())
upper_bound()	of the range including a specified element.
equal_range()
binary_search()	Finds a value in a sequence.

Set Algorithms

Set algorithms are special modifying algorithms that perform set operations on sequences. They are most appropriate on sequences from set containers, but work on sorted sequences from most containers.

The set algorithms work on any sorted iterator range. The includes() algorithm implements standard subset determination, checking if all the elements of one sorted range are included in another sorted range, in any order.

The set_union(), set_intersection(), set_difference(), and set_symmetric_difference() algorithms implement the standard semantics of those operations. In set theory, the result of union is all the elements in either set. The result of intersection is all the elements, which are in both sets. The result of difference is all the elements in the first set but not the second. The result of symmetric difference is the “exclusive or” of sets: all the elements in one, but not both, sets.

Algorithm Name	Algorithm Synopsis	Complexity
inplace_merge()	Merges two sorted sequences in place.	Linear Logarithmic
merge()	Merges two sorted sequences by copying them to a new sequence.	Linear
includes()	Determines if every element from one sequence is in another	Linear
	sequence.
set_union()	Performs the specified set operation on two sorted sequences,	Linear
set_intersection()	copying results to a third sorted sequence.
set_difference()
set_symetric_difference()

Heap Algorithms

A heap is a standard data structure in which the elements of an array or sequence are ordered in a semi-sorted fashion so that finding the “top” elements is quick. Six algorithms allow you to work with heaps.

Algorithm Name	Algorithm Synopsis	Complexity
is_heap()	Checks if a range of elements is a heap.	Linear
is_heap_until()	Finds the largest subrange in the given range of elements that is a heap.	Linear
make_heap()	Creates a heap from a range of elements.	Linear
push_heap()	Adds or removes an element from the heap.	Logarithmic
pop_heap()
sort_heap()	Converts the heap into a range of ascending sorted elements.	Linear
		Logarithmic

Minimum/Maximum Algorithms

Algorithm Name	Algorithm Synopsis
min()	Returns the minimum or maximum of two or more values.
max()
minmax()	Returns the minimum and maximum of two or more values as a pair.
min_element()	Finds the minimum or maximum element in a sequence.
max_element()
minmax_element()	Finds the minimum and maximum element in a sequence and returns the result as a pair.

Numerical Processing Algorithms

The <numeric> header provides the following numerical processing algorithms. None of them require the source sequences to be ordered. All of them have a linear complexity.

Algorithm Name	Algorithm Synopsis
accumulate()	“Accumulates” the values of all the elements in a sequence. The default behavior is
	to sum the elements, but the caller can supply a different binary function instead.
adjacent_difference()	Generates a new sequence in which each element is the difference (or other binary
	operation) of the parallel element, and its predecessor, in the source sequence.
inner_product()	Similar to accumulate(), but works on two sequences. Calls a binary function
	(multiplication by default) on parallel elements in the sequences, accumulating the
	result using another binary function (addition by default). If the sequences
	represent mathematical vectors, the algorithm calculates the dot product of the
	vectors.
iota()	Fills a sequence with successively incrementing values starting with a given value.
partial_sum()	Generates a new sequence in which each element is the sum (or other binary
	operation) of the parallel element, and all preceding elements, in the source
	sequence.

Permutation Algorithms

Algorithm Name	Algorithm Synopsis	Complexity
is_permutation()	Returns true if the elements in one range are a permutation of the	Quadratic
	elements in another range.
next_permutation()	Modifies the sequence by transforming it into its lexicographical “next”	Linear
prev_premutation()	or “previous” permutation. Successive calls to one or the other will
	permute the sequence into all possible permutations of its elements if
	you start with a properly sorted sequence. Returns false if no more
	permutations exist.

Remove Erase Idiom on Containers

Suppose you have a range of elements and you want to remove elements matching a certain condition. The first solution that you might think of is to check the documentation to see if your container has an erase() method and then iterate over all the elements and call erase() for each element that matches the condition. The vector is an example of a container that has such an erase() method. However, if applied to the vector container, this solution is very inefficient as it will cause a lot of memory operations to keep the vector contiguous in memory, resulting in a quadratic complexity. This solution is also error-prone, because you need to be careful that you keep your iterators valid after a call to erase(). The correct solution for this problem is the so-called remove-erase-idiom, which runs in linear time.

Algorithms have access only to the iterator abstraction, not to the container. Thus the remove algorithms cannot really remove them from the underlying container. Instead, the algorithms work by replacing the elements that match the given value or predicate with the next element that does not match the given value or predicate. The result is that the range becomes partitioned into two sets: the elements to be kept and elements to be removed. An iterator is returned that points to the first element in the range of elements to be removed. If you want to actually erase these elements from the container, you must use the remove() algorithm, then call erase() on the container to erase all the elements from the returned iterator up to the end of the range. This is the remove-erase-idiom. As an example removing empty strings from a vector:

void removeEmptyStrings(vector<string>& strings) {
  auto it = remove_if(begin(strings), end(strings), [](const string& str){ return str.empty(); });
  strings.erase(it, end(strings));
}

Allocators

Every STL container takes an Allocator type as a template parameter, for which the default usually suffices. For example, the vector template definition looks like this:

template <class T, class Allocator = allocator<T>> class vector;

The container constructors then allow you to specify an object of type Allocator. These extra parameters permit you to customize the way the containers allocate memory. Every memory allocation performed by a container is made with a call to the allocate() method of the Allocator object. Conversely, every deallocation is performed with a call to the deallocate() method of the Allocator object. The standard library provides a default Allocator class called allocator, which implements these methods as wrappers for operator new and operator delete.

If you want containers in your program to use a custom memory allocation and deallocation scheme, you can write your own Allocator class. There are several reasons for using custom allocators. For example, if the underlying allocator has unacceptable performance, there are alternatives that can be constructed. Or, if memory fragmentation is a problem (lots of different allocations and deallocations leaving unusable small holes in memory), a single “pool” of objects of one type can be created, called a memory pool. When OS-specific capabilities, such as shared memory segments, must be allocated, using custom allocators allows the use of STL containers in those shared memory segments. The use of custom allocators is complex, and there are many possible problems if you are not careful, so this should not be approached lightly.

Any class that provides allocate(), deallocate(), and several other required methods and typedefs can be used in place of the default allocator class. However, in my experience, this feature is rarely used.

What’s Missing from the STL

The STL is powerful, but it’s not perfect. Here is a list of omissions and unsupported functionality:

• The STL does not guarantee any thread safety for accessing containers simultaneously from multiple threads.
• The STL does not provide any generic tree or graph structures. Although maps and sets are generally implemented as balanced binary trees, the STL does not expose this implementation in the interface. If you need a tree or graph structure for something like writing a parser, you will need to implement your own or find an implementation in another library.

It is important to keep in mind that the STL is extensible. You can write your own containers or algorithms that will work with existing algorithms or containers. So, if the STL doesn’t provide exactly what you need, consider writing your desired code such that it works with the STL.

Writing your own STL Containers

The C++ standard contains a list of requirements that any container must fulfill in order to qualify as an STL container. Additionally, if you want your container to be sequential (like a vector), associative (like a map), or unordered associative (like an unordered_map), it must conform to supplementary requirements.

My suggestion when writing a new container is to write the basic container first following the general STL rules such as making it a class template, but without worrying too much about the specific details of STL conformity. After you’ve developed the basic implementation, you can add the iterator and methods so that it can work with the STL framework.

Type Alias Container Requirements

The C++ standard specifies that every STL container must provide the following public type aliases:

Type Name	Description
value_type	The element type stored in the container
reference	A reference to the element type stored in the container
const_reference	A reference to a const element type stored in the container
iterator	A type for iterating over elements of the container
const_iterator	A version of iterator for iterating over const elements of the container
size_type	A type that can represent the number of elements in the container; usually
	just size_t (from <cstddef>)
difference_type	A type that can represent the difference of two iterators for the container;
	usually just ptrdiff_t (from <cstddef>)

Method Container Requirements

In addition to the type aliases, every container must provide the following methods:

Method	Description	Worst Case
		Complexity
Default Constructor	Constructs an empty container	Constant
Copy Constructor	Performs a deep copy of the container	Linear
Move Constructor	Performs a move constructing operation	Constant
Copy Assignment Operator	Performs a deep copy of the container	Linear
Move Assignment Operator	Performs a move assignment operation	Constant
Destructor	Destroys dynamically allocated memory; calls
	destructor on all elements left in container	Linear
iterator begin();	Returns an iterator referring to the first	Constant
const_iterator begin() const;	element in the container
iterator end();	Returns an iterator referring to one-past-the-last	Constant
const_iterator end() const;	element in the container
const_iterator cbegin() const;	Returns a const iterator referring to the first	Constant
	element in the container
const_iterator cend() const;	Returns a const iterator referring to one-past-the-	Constant
	last element in the container
operator==	Comparison operators that compare two containers,	Linear
operator!=	element by element
operator<
operator>
operator<=
operator>=
void swap(Container&);	Swaps the contents of the container passed to the	Constant
	method with the object on which the method is called
size_type size() const;	Returns the number of elements in the container	Constant
size_type max_size() const;	Returns the maximum number of elements the container	Constant
	can hold
bool empty() const;	Specifies whether the container has any elements	Constant

Reversible Containers

If your container supplies a bidirectional or random access iterator, it is considered reversible. Reversible containers are supposed to supply two additional type aliases:

Type name	Description
reverse_iterator	The type for iterating over elements of the container in reverse order.
const_reverse_iterator	A version of reverse_iterator for iterating over const elements
	of the container in reverse order.

Additionally, the container should provide rbegin() and rend(), which are symmetric with begin() and end(); and should provide crbegin() and crend(), which are symmetric with cbegin() and cend().

Associative Container Type Aliases Requirements

Associative containers require three additional types:

Type Name	Description
key_type	The key type with which the container is instantiated
key_compare	The comparison class or function pointer type with which the container is instantiated
value_compare	Class for comparing two value_type elements

Associative Container Method Requirements

The standard prescribes quite a few additional method requirements for associative containers: …

Lambda Expressions

Lambda expressions allow you to write anonymous functions inline, removing the need to write a separate function or a function object. Lambda expressions can make code easier to read and understand.

Basics

// Basic lambda
auto basicLambda = [] { cout << "Hello from Lambda" << endl; };
basicLambda();

// Lambda with parameters
auto parametersLambda = [](int value) { cout << "The value is " << value << endl; };
parametersLambda(42);

// Lambda returning a value
auto returningLambda = [](int a, int b) -> int { return a + b; };
int sum = returningLambda(11, 22);

// Lambda returning a value, with return type omitted
auto returningLambda2 = [](int a, int b) { return a + b; };
sum = returningLambda2(11, 22);

// Lambda capturing a variable by value
double data = 1.23;
auto capturingVLambda = [data] { cout << "Data = " << data << endl; };
capturingVLambda();

// Lambda capturing a variable by value wich can be mutated (e.g. it is non-const)
auto capturingVLambda2 = [data]() mutable {
  data *= 2;
  cout << "Data = " << data << endl;
};
capturingVLambda2();

// Lambda capturing a variable by reference
auto capturingRLambda = [&data] { data *= 2; };
capturingRLambda();

// Generic Lambdas (C++14)
auto isGreaterThan100 = [](auto n) { return n > 100; };
auto result = isGreaterThan100(120);    // int parameter
auto result = isGreaterThan100(120.55); // double parameter

// Lambda Capture Expressions
double pi = 3.1415;
auto myLambda = [myCapture = "Pi: ", pi]{ std::cout << myCapture << pi; };

auto myPtr = std::make_unique<double>(3.1415);
auto myLambda = [p = std::move(myPtr)]{ std::cout << *p; };

auto myPtr = std::make_unique<double>(3.1415);
auto myLambda = [myPtr = std::move(myPtr)] { std::cout << *myPtr; };

Capture block examples

[&x] -> Captures only x by reference and nothing else. [x] -> Captures only x by value and nothing else. [=, &x, &y] -> Captures by value by default, except variables x and y, which are captured by reference. [&, x] -> Captures by reference by default, except variable x, which is captured by value. [&x, &x] -> Is illegal because identifiers cannot be repeated. [this] -> Captures the surrounding object. In the body of the lambda expression you can access this object, even without using this->.

Lambda Expressions as Return Type

function<int(void)> multiplyBy2Lambda(int x) {
  return [x]{ return 2*x; }; // captures x by value, reference wouldn't work here
}

// C++14 supports function return type deduction
auto multiplyBy2Lambda(int x) {
  return [x]{ return 2 * x; }; // captures x by value, reference wouldn't work here
}

// The function can be called as follows
auto fn = multiplyBy2Lambda(5);
cout << fn() << endl; // Ouput will be 10

Function Objects

Overview

You can overload the function call operator in a class such that objects of the class can be used in place of function pointers. These objects are called function objects, or just functors.

Many of the STL algorithms, such as find_if() and a version of accumulate(), require a function pointer as one of the parameters. When you use these functions, you can pass a functor instead of a lambda expression or function pointer. C++ provides several predefined functor classes, defined in the <functional> header file, that perform the most commonly used callback operations.

Functor classes often consist of simple one-line expressions. The clumsiness of having to create a function or functor class, give it a name that does not conflict with other names, and then use this name is considerable overhead for what is fundamentally a simple concept. In these cases, using anonymous (unnamed) functions represented by lambda expressions is a big convenience. Their syntax is easier and can make your code easier to understand.

C++14 adds support for transparent operator functors, which allow you to omit the template type argument. For example, you can just specify multiplies<>() instead of multiplies<int>() or greater<> instead of greater<int>. It is recommended to always use transparent operator functors.

Arithmetic Function Objects

C++ provides functor class templates for the five binary arithmetic operators: plus, minus, multiplies, divides, and modulus. Additionally, unary negate is supplied. These classes are templatized on the type of the operands and are wrappers for the actual operators. They take one or two parameters of the template type, perform the operation, and return the result.

Comparison Function Objects

In addition to the arithmetic function object classes, the C++ language provides all the standard comparisons: equal_to, not_equal_to, less, greater, less_equal, and greater_equal. You’ve already seen less in Chapter 16 as the default comparison for elements in the priority_queue and the associative containers.

Logical Function Objects

C++ provides function object classes for the three logical operations: logical_not (operator!), logical_and (operator&&), and logical_or (operator||). These logical operations deal only with values true and false. Bitwise function objects are covered in the next section.

Bitwise Function Objects

C++ has function objects for all the bitwise operations: bit_and (operator&), bit_or (operator|), and bit_xor (operator^). C++14 adds bit_not (operator)~ . These bitwise functors can, for example, be used together with the transform() algorithm to perform bitwise operations on all elements in a container.

Function Object Adapters

When you try to use the basic function objects provided by the standard, it often feels as if you’re trying to put a square peg into a round hole. For example, you can’t use the less function object with find_if() to find an element smaller than some value because find_if() passes only one argument to its callback each time instead of two. The function adapters attempt to rectify this problem and others. They provide a modicum of support for functional composition, or combining functions together to create the exact behavior you need.

Binders

Binders can be used to bind parameters of functions to certain values. For this you use std::bind(), defined in <functional>, which allows you to bind arguments of a function in a flexible way. You can bind function arguments to fixed values and you can even rearrange function arguments in a different order. Arguments that are not bound to specific values should be specified as _1 , _2 , _3, and so on. These are defined in the std::placeholders namespace.

The <functional> header defines the std::ref() and std::cref() helper functions. These can be used to bind references or const references, respectively.

Negators

The negators are functions similar to the binders but they complement the result of a predicate. The function not1() complements the result of every call to the predicate it takes as an argument. The “1” in not1() refers to the fact that its operand must be a unary function (one that takes a single argument). If its operand is a binary function (takes two arguments), you must use not2() instead.

Calling Member Functions

If you have a container of objects, you sometimes want to pass a pointer to a class method as the callback to an algorithm. For example, you might want to find the first empty string in a vector of strings by calling empty() on each string in the sequence. However, if you just pass a pointer to string::empty() to find_if(), the algorithm has no way to know that it received a pointer to a method instead of a normal function pointer or functor. The code to call a method pointer is different from that to call a normal function pointer, because the former must be called in the context of an object.

C++ provides a conversion function called mem_fn() that you can call on a method pointer before passing it to an algorithm. Note that you have to specify the method pointer as &string::empty. The &string:: part is not optional.

Writing Your Own Function Objects

You can write your own function objects to perform more specific tasks than those provided by the predefined functors and if you need to do something more complex than suitable for lambda expressions. If you want to be able to use the function adapters with these custom functors, you must supply certain typedefs. The easiest way to do that is to derive your function object classes from either unary_function or binary_function, depending on whether they take one or two arguments. These two classes, defined in <functional>, are templatized on the parameter and return types of the “function” they provide.

Ratios

The Ratio library allows you to exactly represent any finite rational number that you can use at compile time. Ratios are used in the std::chrono::duration class. Everything is defined in the <ratio> header file and is in the std namespace. The numerator and denominator of a rational number are represented as compile-time constants of type std::intmax_t, which is a signed integer type with the maximum width supported by a compiler. Because of the compile-time nature of these rational numbers, using them might look a bit complicated and different than usual. You cannot define a ratio object the same way as you define normal objects, and you cannot call methods on it. You need to use typedefs. For example, the following line defines a rational compile-time constant representing 1/60:

typedef ratio<1, 60> r1;
intmax_t num = r1::num;   // Access the numerator of r1 (compile-time constant)
intmax_t den = r1::den;   // Access the denominator of r1 (compile-time constant)

The library supports adding, subtracting, multiplying, and dividing rational numbers. Because all these operations are also happening at compile time, you cannot use the standard arithmetic operators. Instead, you need to use specific templates in combination with typedefs. The following arithmetic ratio templates are available: ratio_add, ratio_subtract, ratio_multiply, and ratio_divide. These templates calculate the result as a new ratio type. This type can be accessed with the embedded typedef called type. For example, the following code first defines two ratios, one representing 1/60 and the other representing 1/30. The ratio_add template adds those two rational numbers together to produce the result rational number, which, after normalization, is 1/20:

typedef ratio<1, 60> r1;
typedef ratio<1, 30> r2;
typedef ratio_add<r1, r2>::type result; // Which is 1/20 after normalization

The standard also defines a number of ratio comparison templates: ratio_equal, ratio_not_equal, ratio_less, ratio_less_equal, ratio_greater, and ratio_greater_equal. Just like the arithmetic ratio templates, the ratio comparison templates are all evaluated at compile time. These comparison templates create a new type, std::integral_constant, representing the result. An integral_constant is a struct template that stores a type and a compile-time constant value. For example, integral_constant<bool, true> stores a Boolean with value true, while integral_constant<int, 15> stores an integer with value 15. The result of the ratio comparison templates is either integral_constant<bool, true> or integral_constant<bool, false>. The value associated with an integral_constant can be accessed using the value data member. The following example demonstrates the use of ratio_less:

typedef ratio<1, 60> r1;
typedef ratio<1, 30> r2;
typedef ratio_less<r2, r1> res;
cout << boolalpha << res::value << endl;

The Chrono Library

The Chrono Library is a collection of classes to work with times. Everything is defined in the std::chrono namespace and requires you to include the <chrono> header file.

Duration

A duration, which represents an interval between two points in time, is specified by the templatized duration class. The duration class stores a numbers of ticks and a tick period. The tick period is the time in seconds between two ticks and is represented as a compile-time ratio constant, which means it could be a fraction of a second. The ~duration template accepts two template parameters and is defined as follows:

template <class Rep, class Period = ratio<1>> class duration {...}

The first template parameter, Rep, is the type of variable storing the number of ticks and should be an arithmetic type, for example long, double, and so on. The second template parameter, Period, is the rational constant representing the period of a tick. If you don’t specify the tick period, the default value ratio<1> is used, which represents a tick period of 1 second.

Three constructors are provided: the default constructor; one that accepts a single value, the number of ticks; and one that accepts another duration. The latter can be used to convert from one duration to another duration, for example from minutes to seconds.

duration<long> d1;                  // A duration where each tick is one second
duration<long, ratio<1>> d2;        // The same, ratio<1> is the default tick period
duration<long, ratio<60>> d3;       // A duration in minutes (tick period = 60 seconds)
duration<double, ratio<1, 60>> d4;  // A duration where each tick period is a sixtieth of a second
duration<long long, milli> d5;      // A duration where each tick period is one millisecond
duration<long> d6(30);              // 30 seconds
duration<double, ratio<60>> d7(d6); // Converts d6 into minutes, resulting in 0.5 minutes

auto t = hours(1) + minutes(23) + seconds(45);
cout << seconds(t).count() << " seconds" << endl;

auto myDuration = 42min; // C++14, 42 minutes (also "h", "min", "s", "ms", "us" and "ns")
auto myDuration = 42s;   // C++14, 42 seconds (also "h", "min", "s", "ms", "us" and "ns")

Clock

A clock is a class consisting of a time_point and a duration. Three clocks are defined by the standard. The first is called system_clock and represents the wall clock time from the system-wide realtime clock. The second is called steady_clock, a clock that guarantees its time_point will never decrease, which is not guaranteed for system_clock because the system clock can be adjusted at any time. The third is the high_resolution_clock, which has the shortest possible tick period. Depending on your compiler, it is possible for the high_resolution_clock to be a synonym for steady_clock or system_clock.

Every clock has a static now() method to get the current time as a time_point. The system_clock also defines two static helper functions for converting time_points to and from the time_t C-style time representation. The first is called to_time_t() converting a given time_point to a time_t; the second is called from_time_t(), which returns a time_point initialized with a given time_t value. The time_t type is defined in the <ctime> header file.

Time point

A point in time is represented by the time_point class and stored as a duration relative to the epoch. A time_point is always associated with a certain clock and the epoch is the origin of this associated clock. For example, the epoch for the classic Unix/Linux time is 1st of January 1970, and durations are measured in seconds. The epoch for Windows is 1st of January 1601 and durations are measured in 100 nanosecond units. Other operating systems have different epoch dates and duration units.

The time_point class contains a function called time_since_epoch(), which returns a duration representing the time between the epoch of the associated clock and the stored point in time. A time_point supports arithmetic operations that make sense for time points such as +, -, += and -=. Comparison operators are also supported to compare two time points. Two static methods are provided: min() returning the smallest possible point in time, and max() returning the largest possible point in time.

The time_point class has three constructors:

time_point()

constructs a time_point initialized with duration::zero(). The resulting time_point represents the epoch of the associated clock .

time_point(const duration& d)

constructs a time_point initialized with the given duration. The resulting time_point represents epoch + d.

template<class Duration2> time_point(const time_point<clock, Duration2>& t)

constructs a time_point initialized with t.time_since_epoch().

Each time_point is associated with a clock. To create a time_point, you specify the clock as the template parameter: time_point<steady_clock> tp1;

Each clock also knows its time_point type, so you can also write it as follows: steady_clock::time_point tp1;

Random Number Generation

The old srand() and rand() functions don’t offer much in terms of flexibility. You cannot, for example, change the distribution of the generated random numbers. C++11 has added a powerful library to generate random numbers by using different algorithms and distributions. The library is defined in the <random> header file. The library has three big components: engines, engine adapters, and distributions. A random number engine is responsible for generating the actual random numbers and storing the state for generating subsequent random numbers. The distribution determines the range of the generated random numbers and how they are mathematically distributed within that range. A random number engine adapter modifies the results of a random number engine you associate it with. It’s highly recommended to stop using srand() and rand(), and to start using the classes from <random>.

The quality of a random number generator is referred to as its entropy measure. The entropy() method of the random_device class returns 0.0 if it is using a software-based pseudo-random number generator, and returns a nonzero value if there is a hardware device attached. The nonzero value is an estimate of the entropy of the attached device.

Type Traits

Type traits allow you to make decisions based on types at compile time. For example, you can write a template that requires a type that is derived from a certain type, or a type that is convertible to a certain type, or a type that is integral, and so on. The standard defines several helper classes for this. All type traits-related functionality is defined in the <type_traits> header file.

Primary type categories

is_void, is_integral, is_floating_point, is_pointer, …

Composited type categories

is_reference, is_object, is_scalar, …

Type properties

is_const, is_literal_type, is_polymorphic, is_unsigned, is_constructible, is_copy_constructible, is_move_constructible, is_assignable, is_trivially_copyable, …

Type relations

is_same, is_base_of, is_convertible

const-volatile modifications

remove_const, add_const, …

Sign modifications

make_signed, make_unsigned

Reference modifications

remove_reference, add_lvalue_reference, add_rvalue_reference

Other transformations

enable_if, conditional, …

Multithreaded Programming

Race Conditions

Race conditions can occur when multiple threads want to read/write to a shared memory location. For example, suppose you have a shared variable and one thread increments this value while another thread decrements it. Incrementing and decrementing the value means that the current value needs to be retrieved from memory, incremented or decremented, and stored back in memory. On older architectures, such as PDP-11 and VAX, this used to be implemented with an INC processor instruction, which was atomic. On modern x86 processors, the INC instruction is not atomic anymore, meaning that other instructions could be executed in the middle of this operation, which might cause the code to retrieve a wrong value.

Deadlocks

If you opt to solve a race condition by using a synchronization method, such as mutual exclusion, you might run into another common problem with multithreaded programming: Deadlocks. Deadlocks are threads blocking indefinitely because they are waiting to acquire access to resources currently locked by other blocked threads. For example, suppose you have two threads and two resources, A and B. Both threads require a lock on both resources, but they acquire the locks in different order. You should try to avoid any possible deadlock situation altogether. If you need to acquire multiple locks, the recommended way is to use the standard std::lock() or std::try_lock() functions. These functions obtain or try to obtain a lock on several resources, doing their best to prevent deadlocks.

Tearing

Tearing means that part of your data has been written to memory, while part hasn’t been written yet. If another thread reads that data at that exact moment it sees inconsistent data.

Cache Coherency

Cache coherency is important to keep in mind. If one thread writes a piece of data, that thread immediately sees this new data, but this does not mean that all threads see this new data immediately! CPUs have caches and the cache structure on multicore processors is complicated. If one core modifies your data, it is changed immediately in its cache; but, this change is not immediately visible to cores using a different cache. So, even simple data types, such as Booleans, need to be synchronized when reading and writing to them from multiple threads.

Thread Local Storage

The standard supports the concept of thread local storage. With a keyword called thread_local, you can mark any variable as thread local, which means that each thread will have its own unique copy of the variable and it will last for the entire duration of the thread. For each thread, the variable is initialized exactly once. For example, in the following code, every thread shares one-and-only-one copy of k, while each thread has its own unique copy of n:

thread_local int n;
int k;
void doWork() {
  // perform some computation
}

Note that if the thread_local variable is declared in the scope of a function, its behavior is as if it were declared static, except that every thread has its own unique copy and is initialized exactly once per thread, no matter how many times that function is called in that thread.

Canceling Threads

The standard does not include any mechanism for canceling a running thread from inside another thread. The best way to achieve this is to provide some communication mechanism that the two threads agree upon. The simplest mechanism is to have a shared variable, which the target thread checks periodically to determine if it should terminate. Other threads can set this shared variable to indirectly instruct the thread to shut down. Care has to be taken to avoid race conditions and cache coherency problems with reading and writing to this shared variable. Atomic variables or condition variables can help avoid these problems.

Retrieving Results from Threads

In most cases you are probably interested in results produced by a given thread. For example, if your thread performs some mathematical calculations, you really would like to get the results out of the thread once the thread is finished. One way is to pass a pointer or reference to a result variable to the thread in which the thread stores the results. Another method is to store the results inside a class member variable of a function object, which you can retrieve later once the thread has finished executing.

However, there is another and easier method to obtain a result from threads: futures. They also make it easier to handle errors that occur inside your threads.

Copying and Rethrowing Exceptions

The whole exception mechanism in C++ works perfectly, as long as it stays within one single thread. Every thread can throw its own exceptions, but they need to be caught within their own thread. Exceptions thrown in one thread cannot be caught in another thread. This introduces quite a few problems when you would like to use exception handling in combination with multithreaded programming.

Without the standard threading library it’s very difficult if not impossible to gracefully handle exceptions across threads. The standard threading library solves this issue with the following exception-related functions. These functions not only work with std::exceptions, but with all kinds of exceptions, ints, strings, custom exceptions, and so on:

exception_ptr current_exception() noexcept;

This function is intended to be called from inside a catch block, and returns an exception_ptr object that refers to the exception currently being handled, or a copy of the currently handled exception, or a null exception_ptr object if no exception is being handled. This referenced exception object remains valid for as long as there is an object of type exception_ptr that is referencing it. exception_ptr is of type NullablePointer, which means it can easily be tested with a simple if statement.

[[noreturn]] void rethrow_exception(exception_ptr p);

This function rethrows the exception referenced by the exception_ptr parameter. Rethrowing the referenced exception does not have to be done in the same thread that generated the referenced exception in the first place, which makes this feature perfectly suited for handling exceptions across different threads. The [[[[noreturn]]]] attribute makes it clear that this function never returns normally.

Atomic Operations Library

Atomic types allow atomic access, which means that concurrent reading and writing without additional synchronization is allowed. Without atomic operations, incrementing a variable is not thread-safe because the compiler first loads the value from memory into a register, increments it, and then stores the result back in memory. Another thread might touch the same memory during this increment operation, which is a race condition.

You need to include the <atomic> header to use these atomic types. The standard defines named integral atomic types for all primitive types. The following table lists a few:

Named Atomic Type	Equivalent Atomic Type
atomic_bool	atomic<bool>
atomic_char	atomic<char>
atomic_uchar	atomic<unsigned char>
atomic_int	atomic<int>
atomic_uint	atomic<unsigned int>
atomic_long	atomic<long>
atomic_ulong	atomic<unsigned long>
atomic_llong	atomic<long long>
atomic_ullong	atomic<unsigned long long>
atomic_wchar_t	atomic<wchar_t>

When accessing a piece of data from multiple threads, atomics also solve other problems such as cache coherence, memory ordering, compiler optimizations, and so on. Basically, it’s virtually never safe to read and write to the same piece of data from multiple threads without using atomics or explicit synchronization mechanisms.

Mutual Exclusion

If you are writing multithreaded applications, you have to be sensitive to sequencing of operations. If your threads read and write shared data, this can be a problem. There are many ways to avoid this problem, such as never actually sharing data between threads (or atomics for simple types). However, if you can’t avoid sharing data, you must provide for synchronization so that only one thread at a time can change the data.

Scalars such as Booleans and integers can often be synchronized properly with atomic operations; but, when your data is more complex, and you need to use that data from multiple threads, you must provide explicit synchronization.

Mutex Classes

Mutex stands for mutual exclusion. The mutual exclusion classes are all defined in the <mutex> header file and are in the std namespace. The basic mechanism of using a mutex is as follows:

• A thread that wants to use (read/write) memory shared with other threads tries to lock a mutex object. If another thread is currently holding this lock, the new thread that wants to gain access blocks until the lock is released, or until a timeout interval expires.
• Once the thread has obtained the lock, it is free to use the shared memory. Of course, this assumes that all threads that want to use the shared data all correctly acquire a lock on the mutex.
• After the thread is finished with reading/writing to the shared memory, it releases the lock to give some other thread an opportunity to obtain the lock to the shared memory. If two or more threads are waiting on the lock, there are no guarantees as to which thread is granted the lock and thus allowed to proceed.

The standard provides non-timed mutex and timed mutex classes.

Non-Timed Mutex Classes

The library has two non-timed mutex classes: std::mutex and std::recursive_mutex. Each supports the following methods:

lock()

The calling thread tries to obtain the lock and blocks until the lock has been acquired. It blocks indefinitely. If there is a desire to limit the amount of time the thread blocks, you should use a timed mutex.

try_lock()

The calling thread tries to obtain the lock. If the lock is currently held by another thread, the call returns immediately. If the lock has been obtained, try_lock() returns true, otherwise it returns false.

unlock()

Releases the lock held by the calling thread, making it available for another thread.

std::mutex is a standard mutual exclusion class with exclusive ownership semantics. There can be only one thread owning the mutex. If another thread wants to obtain ownership of this mutex, it either blocks when using lock(), or fails when using try_lock(). A thread already having ownership of a std::mutex is not allowed to call lock() or try_lock() again on that mutex. This might lead to a deadlock!

std::recursive_mutex behaves almost identically to std::mutex, except that a thread already having ownership of a recursive mutex is allowed to call lock() or try_lock() again on the same recursive mutex. The calling thread should call the unlock() method as many times as it obtained a lock on the recursive mutex.

Timed Mutex Classes

The library provides three timed mutex classes: std::timed_mutex, std::recursive_timed_mutex, and std::shared_timed_mutex; all support the normal lock(), try_lock(), and unlock() methods. Additionally, they support the following:

try_lock_for(rel_time)

The calling thread tries to obtain the lock for a certain relative time. If the lock could not be obtained after the given timeout, the call fails and returns false. If the lock could be obtained within the timeout, the call succeeds and returns true.

try_lock_until(abs_time)

The calling thread tries to obtain the lock until the system time equals or exceeds the specified absolute time. If the lock could be obtained before this time, the call returns true. If the system time passes the given absolute time, the function stops trying to obtain the lock and returns false.

A thread already having ownership of a timed_mutex is not allowed to call one of the previous lock calls again on that mutex. This might lead to a deadlock!

recursive_timed_mutex behaves almost identically to timed_mutex, except that a thread already having ownership of a recursive mutex is allowed to call one of the previous lock calls again on the same mutex. The calling thread should call the unlock() method as many times as it obtained a lock on the recursive mutex.

The shared_timed_mutex class supports the concept of shared lock ownership, also known as readers-writers lock. A thread can either get exclusive ownership or shared ownership of the lock. Exclusive ownership, also known as a write lock, can be acquired only when there are no other threads having exclusive or shared ownership. Shared ownership, also known as a read lock, can be acquired if there is no other thread having exclusive ownership, but other threads are allowed to have acquired shared ownership. The shared_timed_mutex class supports lock(), try_lock(), try_lock_for(), try_lock_until(), and unlock(), all discussed earlier. These methods acquire and release exclusive locks. Additionally they have the following shared ownership-related methods:

lock_shared()

The calling thread tries to obtain the shared ownership lock and blocks until the lock has been acquired.

try_lock_shared()

The calling thread tries to obtain the shared ownership lock. If an exclusive lock is currently held by another thread, the call returns immediately. If the lock has been obtained, try_lock() returns true, otherwise it returns false.

try_lock_shared_for(rel_time)

The calling thread tries to obtain the shared ownership lock for a certain relative time. If the lock could not be obtained after the given timeout, the call fails and returns false. If the lock could be obtained within the timeout, the call succeeds and returns true.

try_lock_shared_until(abs_time)

The calling thread tries to obtain the shared ownership lock until the system time equals or exceeds the specified absolute time. If the lock could be obtained before this time, the call returns true. If the system time passes the given absolute time, the function stops trying to obtain the lock and returns false.

unlock_shared()

Releases shared ownership.

Locks

A lock class is a RAII class that makes it easier to correctly obtain and release a lock on a mutex; the destructor of the lock class automatically releases the associated mutex. The standard defines three types of locks: std::lock_guard, std::unique_lock, and std::shared_lock.

lock_guard

lock_guard is a simple lock with two constructors.

explicit lock_guard(mutex_type& m);

A constructor accepting a reference to a mutex. This one tries to obtain a lock on the mutex and blocks until the lock is obtained.

lock_guard(mutex_type& m, adopt_lock_t);

A constructor accepting a reference to a mutex and an instance of the std::adopt_lock_t struct. The lock assumes that the calling thread already has obtained a lock on the referenced mutex and will manage this lock.

unique_lock

std::unique_lock is a more sophisticated lock that allows you to defer lock acquisition until later in the execution, long after the declaration. You can use the owns_lock() method to see if the lock has been acquired. A unique_lock also has a bool conversion operator, which can be used to check if the lock has been acquired. unique_lock has several constructors:

explicit unique_lock(mutex_type& m);

A constructor accepting a reference to a mutex. This one tries to obtain a lock on the mutex and blocks until the lock is obtained.

unique_lock(mutex_type& m, defer_lock_t) noexcept;

A constructor accepting a reference to a mutex and an instance of the std::defer_lock_t struct. The unique_lock stores the reference to the mutex, but does not immediately try to obtain a lock. A lock can be obtained later.

unique_lock(mutex_type& m, try_to_lock_t);

A constructor accepting a reference to a mutex and an instance of the std::try_to_lock_t struct. The lock tries to obtain a lock to the referenced mutex, but if it failes it does not block.

unique_lock(mutex_type& m, adopt_lock_t)

A constructor accepting a reference to a mutex and an instance of the std::adopt_lock_t struct. The lock assumes that the calling thread already has obtained a lock on the referenced mutex and will manage this lock.

unique_lock(mutex_type& m, const chrono::time_point<Clock, Duration>& abs_time );

A constructor accepting a reference to a mutex and an absolute time. The constructor tries to obtain a lock until the system time passes the given absolute time.

unique_lock(mutex_type& m, const chrono::duration<Rep, Period>& rel_time);

A constructor accepting a reference to a mutex and a relative time. The constructor tries to get a lock on the mutex with the given relative timeout.

The unique_lock class also has the following methods: lock(), try_lock(), try_lock_for(), try_lock_until(), and unlock(), which behave as explained in the section on timed mutex classes.

shared_lock

The shared_lock class has the same type of constructors and the same methods as unique_lock. The difference is that the shared_lock class calls the shared ownership related methods on the underlying shared mutex. Thus, the methods of shared_lock are called lock(), try_lock(), and so on, but on the underlying shared mutex they call lock_shared(), try_lock_shared(), and so on. This is done so that shared_lock has the same interface as unique_lock, and can be used as a stand-in replacement for unique_lock but acquires a shared lock instead of an exclusive lock.

Acquiring Multiple Locks at Once

C++ has two generic lock functions that you can use to obtain locks on multiple mutex objects at once without the risk of creating deadlocks. Both are defined in the std namespace, and both are variadic template functions:

template <class L1, class L2, class… L3> void lock(L1&, L2&, L3&…);

This generic function locks all the given mutex objects in an unspecified order without the risk of deadlocks. If one of the mutex lock calls throws an exception, unlock() is called on all locks that have already been obtained.

template <class L1, class L2, class… L3> int try_lock(L1&, L2&, L3&…);

try_lock() tries to obtain a lock on all the given mutex objects by calling try_lock() on each of them in sequence. It returns -1 if all calls to try_lock() succeed. If any try_lock() fails, unlock() is called on all locks that have already been obtained, and the return value is the zero-based index of the parameter position of the mutex on which try_lock() failed.

The following example demonstrates how to use the generic lock() function. The process() function first creates two locks, one for each mutex, and gives an instance of std::defer_lock_t as a second argument to tell unique_lock not to acquire the lock during construction. The call to lock() then acquires both locks without the risk of deadlocks:

mutex mut1;
mutex mut2;
void process() {
  unique_lock<mutex> lock1(mut1, defer_lock_t());
  unique_lock<mutex> lock2(mut2, defer_lock_t());
  lock(lock1, lock2);
  // Locks acquired
}
int main() {
  process();
}

std::call_once

You can use std::call_once() in combination with std::once_flag to make sure a certain function or method is called exactly one time no matter how many threads try to call call_once(). Only one call_once() invocation actually calls the given function or method; this invocation is called the effective call_once(). This effective invocation on a specific once_flag instance finishes before all other call_once() invocations on the same once_flag instance. Other threads calling call_once() on the same once_flag instance block until the effective call is finished.

Condition Variables

Condition variables allow a thread to block until a certain condition is set by another thread or until the system time reaches a specified time. They allow for explicit inter-thread communication. There are two kinds of condition variables available, both defined in the <condition_variable> header file:

std::condition_variable

A condition variable that can wait only on a unique_lock<mutex>, which, according to the standard, allows for maximum efficiency on certain platforms.

std::condition_variable_any

A condition variable that can wait on any kind of object, including custom lock types.

The condition_variable class supports the following methods.

notify_one()

Wakes up one of the threads waiting on this condition variable.

notify_all()

Wakes up all threads waiting on this condition variable.

wait(unique_lock<mutex>& lk)

The thread calling wait() should already have acquired a lock on lk. The effect of calling wait() is that it atomically calls lk.unlock() and then blocks the thread, waiting for a notification. When the thread is unblocked by a notify_one() or notify_all() call in another thread, the function calls lk.lock() again, possibly blocking on the lock and then returning.

wait_for(unique_lock<mutex>& lk, const chrono::duration<Rep, Period>& rel_time)

Similar to the previous wait() method, except that the thread is unblocked by a notify_one() call, a notify_all() call, or when the given timeout has expired.

wait_until(unique_lock<mutex>& lk, const chrono::time_point<Clock, Duration>& abs_time)

Similar to wait(), except that the thread is unblocked by a notify_one() call, a notify_all() call, or when the system time passes the given absolute time.

The condition_variable_any class supports the same methods as the condition_variable class except that it accepts any kind of lock class instead of only a unique_lock<mutex>. Your lock class should have a lock() and unlock() method.

Threads waiting on a condition variable can wake up when another thread calls notify_one() or notify_all(), or with a relative timeout, or when the system time reaches a certain time, but can also wake up spuriously. This means that a thread can wake up even if no other thread has called any notify method. Thus, when a thread waits on a condition variable and wakes up, it needs to check whether it woke up because of a notify or not. One way to check for this is using one of the versions of wait() accepting a predicate.

Futures

Using std::thread to launch a thread that calculates a single result does not make it easy to get the computed result back once the thread has finished executing. Another problem with std::thread is handling errors like exceptions. If a thread throws an exception and this exception is not handled by the thread itself, the C++ runtime calls std::terminate, which usually terminates the whole application. You can avoid this by using std::future, which is able to transport an uncaught exception to another thread, which can then handle the exception however it wants. Of course, it’s good practice to always try to handle exceptions in the threads themselves as much as possible, preventing them from leaving the thread.

std::future and std::promise work together to make it easier to retrieve a result from a function that ran in the same thread or in another thread. Once a function, running in the same thread or in another thread, has calculated the value that it wants to return, it puts this value in a promise. This value can then be retrieved through a future. You can think of a future/promise pair as an inter-thread communication channel for a result.

If you want to give the C++ runtime more control over whether or not a thread is created to calculate something, you can use std::async(). It accepts a function to be executed and returns a future that you can use to retrieve the result. There are two ways in which async() can call your function:

• Creating a new thread to run your function asynchronously.
• Running your function at the time you call get() on the returned future.

If you call async() without additional arguments, the runtime automatically chooses one of the two methods depending on factors like the number of processors in your system and the amount of concurrency already taking place. You can force the runtime to use one or the other method by specifying a launch::async (create a new thread) or launch::deferred (use current thread) policy argument.

Thread Pools

Instead of creating and deleting threads dynamically throughout your program lifetime, you can create a pool of threads that can be used as needed. This technique is often used in programs that want to handle some kind of event in a thread. In most environments, the ideal number of threads is equal to the number of processing cores. If there are more threads than cores, threads will have to be suspended to allow other threads to run, and this will ultimately add overhead. Note that while the ideal number of threads is equal to the number of cores, this applies only in the case where the threads are compute bound and cannot block for any other reason, including I/O. When threads can block, it is often appropriate to run more threads than there are cores. Determining the optimal number of threads in such cases may involve throughput measurements.

Because not all processing is identical, it is not uncommon to have threads from a thread pool receive, as part of their input, a function object or lambda expression that represents the computation to be done.

Because threads from a thread pool are pre-existing, it is vastly more efficient for the operating system to schedule one to run than it is to create one in response to an input. Furthermore, the use of a thread pool allows you to manage the number of threads created, so depending on the platform, you may have just one thread or thousands of threads.

Threading Design and Best Practices

Before terminating the application, always use join() to wait for background threads to finish

Make sure you use join() on all background threads before terminating your application. This will make sure all those background threads have the time to do proper cleanup. Background threads for which there is no join() will terminate abruptly when the main thread is terminated.

The best synchronization is no synchronization

Multithreaded programming becomes much easier if you manage to design your different threads in such a way that all threads working on shared data read only from that shared data and never write to it, or only write to parts never read by other threads. In that case there is no need for any synchronization and you cannot have problems like race conditions or deadlocks.

Try to use the single-thread ownership pattern

This means that a block of data is owned by no more than one thread at a time. Owning the data means that no other thread is allowed to read/write to the data. When the thread is finished with the data, the data can be passed off to another thread, which now has sole and complete responsibility/ownership of the data. No synchronization is necessary in this case.

Use atomic types and operations when possible

Atomic types and atomic operations make it easier to write race-condition and deadlock-free code, because they handle synchronization automatically. If atomic types and operations are not possible in your multithreaded design, and you need shared data, you have to use a mutual exclusion mechanism to ensure proper synchronization.

Use locks to protect mutable shared data

If you need mutable shared data to which multiple threads can write, and you cannot use atomic types and operations; you have to use a locking mechanism to make sure reads and writes between different threads are synchronized.

Release locks as soon as possible

When you need to protect your shared data with a lock, make sure you release the lock as soon as possible. While a thread is holding a lock, it is blocking other threads waiting for the same lock, possibly hurting performance.

Make sure to acquire multiple locks in the same order

If multiple threads need to acquire multiple locks, they must be acquired in the same order in all threads to prevent deadlocks. You should use the generic std::lock() or std::try_lock() to minimize the chance of violating lock ordering restrictions.

Use a multithreading-aware profiler

Use a multithreading-aware profiler to find performance bottlenecks in your multithreaded applications and to find out if your multiple threads are indeed utilizing all available processing power in your system. An example of a multithreading-aware profiler is the profiler in certain editions of Microsoft Visual Studio.

Understand the multithreading support features of your debugger

Most debuggers have at least basic support for debugging multithreaded applications. You should be able to get a list of all running threads in your application, and you should be able to switch to any one of those threads to inspect their call stack. You can use this, for example, to inspect deadlocks because you can see exactly what each thread is doing.

Use thread pools instead of creating and destroying a lot of threads dynamically

Your performance decreases if you dynamically create and destroy a lot of threads. In that case it’s better to use a thread pool to reuse existing threads.

Use higher-level multithreading libraries

Where possible, use higher-level multithreading libraries such as Intel Threading Building Blocks (TBB), Microsoft Parallel Patterns Library (PPL), and so on, rather than reinventing the wheel. Multithreaded programming is hard to get right and is error prone. More often than not, your wheel may not be as round as you think.

Efficient C++

Language-Level Efficiency (Only for objects, not primitive types)

Pass Objects by Reference (pass-by-reference)

Pass-by-value incurs copying costs that are avoided with pass-by-reference. Objects passed by value must call constructors and destructors on them and all their data members.

Return Objects by Reference (retury-by-reference)

Just as you should pass objects by reference to functions, you should also return them by reference from functions in order to avoid copying the objects unnecessarily. Unfortunately, it is sometimes impossible to return objects by reference, such as when you write overloaded operator+ and other similar operators. You should never return a reference or a pointer to a local object that will be destroyed when the function exits. Since C++11, the language has support for move semantics, which allows you to efficiently return objects by value, instead of using reference semantics.

Catch Exceptions by Reference

You should catch exceptions by reference in order to avoid an extra copy. Throwing exceptions is heavy in terms of performance, so any little thing you can do to improve their efficiency will help.

Use Move Semantics

You should implement a move constructor and move assignment operator for your objects, which allow the C++ compiler to use move semantics. With move semantics for your objects, returning them by value from a function will be efficient without incurring large copying costs.

Avoid Creating Temporary Objects

The compiler creates temporary, unnamed objects in several circumstances. For example after writing a global operator+ for a class, you can add objects of that class to other types, as long as those types can be converted to objects of that class. In general, the compiler constructs a temporary object whenever your code converts a variable of one type to another type for use in a larger expression. This rule applies mostly to function calls.

You should generally attempt to avoid cases in which the compiler is forced to construct temporary objects. Although it is impossible to avoid in some situations, you should at least be aware of the existence of this “feature” so you aren’t surprised by performance and profiling results.

Move semantics are also used by the compiler to make working with temporary objects more efficient. That’s another reason to add move semantics to your classes.

Use Inline Methods and Functions

The code for an inline method or function is inserted directly into the code where it is called, avoiding the overhead of a function call. You should mark as inline all functions and methods that you think can qualify for this optimization. However, remember that inlining requests by the programmer are only a recommendation to the compiler, which is allowed to refuse them.

On the other hand, some compilers inline appropriate functions and methods during their optimization steps, even if those functions aren’t marked with the inline keyword. Thus, you should read your compiler documentation before wasting a lot of effort deciding which functions to inline.

Design-Level Efficiency

The design choices in your program affect its performance far more than do language details such as pass-by-reference. For example, if you choose an algorithm for a fundamental task in your application that runs in O(n^2) time instead of a simpler one that runs in O(n) time, you could potentially perform the square of the number of operations that you really need. To put numbers on that, a task that uses an O(n^2) algorithm and performs one million operations would perform only one thousand with an O(n) algorithm. Even if that operation is optimized beyond recognition at the language level, the simple fact that you perform one million operations when a better algorithm would use only one thousand will make your program very inefficient. Always choose your algorithms carefully.

In addition to your choice of algorithms, design-level efficiency includes specific tips and tricks. Instead of writing your own data structures and algorithms, you should use existing ones, such as the STL or the Boost libraries, as much as possible because these are written by experts. You should also think about incorporating multithreading in your design.

Here are two more design techniques for optimizing your program: caching, and object pools.

Cache

Caching means storing items for future use in order to avoid retrieving or recalculating them. You might be familiar with the principle from its use in computer hardware. Modern computer processors are built with memory caches that store recently and frequently accessed memory values in a location that is quicker to access than main memory. Most memory locations that are accessed at all are accessed more than once in a short time period, so caching at the hardware level can significantly speed up computations.

Caching in software follows the same approach. If a task or computation is particularly slow, you should make sure that you are not performing it more than necessary. Store the results in memory the first time you perform the task so that they are available for future needs. Here is a list of tasks that are usually slow:

Disk access

You should avoid opening and reading the same file more than once in your program. If memory is available, save the file contents in RAM if you need to access it frequently.

Network communication

Whenever you need to communicate over a network, your program is subject to the vagaries of the network load. Treat network accesses like file accesses, and cache as much static information as possible.

Mathematical computations

If you need the result of a very complex computation in more than one place, perform the calculation once and share the result. However, if it’s not very complex, then it’s probably faster to just calculate it instead of retrieving it from a cache. Use a profiler if you want to make sure.

Object allocation

If you need to create and use a large number of short-lived objects in your program, consider using an object pool.

Thread creation

This task can also be slow. You can “cache” threads in a thread-pool, similar to caching objects in an object-pool.

One common problem with caching is that the data you store are often only copies of the underlying information. The original data might change during the lifetime of the cache. For example, you might want to cache the values in a configuration file so that you don’t need to read it repeatedly. However, the user might be allowed to change the configuration file while your program is running, which would make your cached version of the information obsolete. In cases like this, you need a mechanism for cache invalidation: When the underlying data change, you must either stop using your cached information, or repopulate your cache.

One technique for cache invalidation is to request that the entity managing the underlying data notifies your program of the data change. It could do this through a callback that your program registers with the manager. Alternatively, your program could poll for certain events that would trigger it to repopulate the cache automatically. Regardless of your specific cache invalidation technique, make sure you think about these issues before relying on a cache in your program.

Object Pools

If your program needs a large number of short-lived objects of the same type that have an expensive constructor (for example, a constructor creating a large, pre-sized vector for storing data), and a profiler confirms that allocating and deallocating these objects is a bottleneck, then you can create a pool, or cache, of those objects. Whenever you need an object in your code, you ask the pool for one. When you are done with the object, you return it to the pool. The object pool creates the objects only once, so their constructor is called only once, not each time they are used. Thus, object pools are appropriate when the constructor performs some setup actions that apply to many uses of the object, and when you can set instance-specific parameters on the object through non-constructor method calls.