By 2006, C++ had been in widespread industrial use for 20 years. It contained parts that had survived unchanged since introduced into C in the early 1970s as well as features that were novel in the early 2000s. From 2006 to 2020, the C++ developer community grew from about 3 million to about 4.5 million. It was a period where new programming models emerged, hardware architectures evolved, new application domains gained massive importance, and quite a few well-financed and professionally marketed languages fought for dominance. How did C++ -- an older language without serious commercial backing -- manage to thrive in the face of all that? This paper focuses on the major changes to the ISO C++ standard for the 2011, 2014, 2017, and 2020 revisions. The standard library is about 3/4 of the C++20 standard, but this paper's primary focus is on language features and the programming techniques they support. The paper contains long lists of features documenting the growth of C++. Significant technical points are discussed and illustrated with short code fragments. In addition, it presents some failed proposals and the discussions that led to their failure. It offers a perspective on the bewildering flow of facts and features across the years. The emphasis is on the ideas, people, and processes that shaped the language. Themes include efforts to preserve the essence of C++ through evolutionary changes, to simplify its use, to improve support for generic programming, to better support compile-time programming, to extend support for concurrency and parallel programming, and to maintain stable support for decades' old code. The ISO C++ standard evolves through a consensus process. Inevitably, there is competition among proposals and clashes (usually polite ones) over direction, design philosophies, and principles. The committee is now larger and more active than ever, with as many as 250 people turning up to week-long meetings three times a year and many more taking part electronically. We try (not always successfully) to mitigate the effects of design by committee, bureaucratic paralysis, and excessive enthusiasm for a variety of language fashions. Specific language-technical topics include the memory model, concurrency and parallelism, compile-time computation, move-semantics, exceptions, lambda expressions, and modules. Designing a mechanism for specifying a template's requirements on its arguments that is sufficiently flexible and precise yet doesn't impose run-time costs turned out to be hard. The repeated attempts to design ``concepts'' to do that have their roots back in the 1980s and touch upon many key design issues for C++ and for generic programming. The description is based on personal participation in the key events and design decisions, backed by the thousands of papers and hundreds of meeting minutes in the ISO C++ standards committee's archives.

Object-oriented programming is often characterized as encapsulation plus polymorphism plus inheritance. The original Simula67 demonstrated that we could do without encapsulation and Kristen Nygaard insisted that some OOP could be done without inheritance. I present generic programming as providing encapsulation plus polymorphism. In C++, this view is directly supported by language facilities, such as classes, templates and (only recently) concepts. I show a range of type-and-resource-safe techniques covering a wide range of applications including containers, algebraic concepts, and numerical and non-numerical algorithms.

Pattern matching is an abstraction mechanism that can greatly simplify source code. We present functional-style pattern matching for C++ implemented as a library, called Mach71. All the patterns are user-definable, can be stored in variables, passed among functions, and allow the use of class hierarchies. As an example, we implement common patterns used in functional languages.

We describe how legacy C++ programs can be rejuvenated using C++11 features such as generalized constant expressions, perfect forwarding, and lambda expressions. In general, this work develops a correspondence between different kinds of macros and the C++ declarations to which they should be transformed. We have created a set of demacrofication tools to assist a developer in the rejuvenation of C++ programs. To evaluate the work, we have applied the rejuvenation tools to a number of C++ libraries to assess the extent to which these libraries might be improved by demacrofication. Results indicate that between 68 and 98% of potentially refactorable macros could be transformed into C++11 declarations. Additional experiments demonstrate why these numbers are not readily achieved using fully automated rejuvenation tools. We also discuss some techniques to further assist in automating rejuvenation process.

C++ programs can be rejuvenated by replacing error-prone usage of the C Preprocessor macros with type safe C++11 declarations. We have developed a classification of macros that directly maps to corresponding C++11 expressions, statements, and declarations. We have built a set of tools that replaces macros with equivalent C++ declarations and iteratively introduces the refactorings into the software build.

Selecting operations based on the run-time type of an object is key to many object-oriented and functional programming techniques. We present a technique for implementing open and efficient type switching on hierarchical extensible data types. The technique is general and copes well with C++ multiple inheritance. To simplify experimentation and gain realistic performance using production-quality compilers and tool chains, we implement a type switch construct as an ISO C++11 library, called Mach7. This library-only implementation provides concise notation and outperforms the visitor design pattern, commonly used for case analysis on types in object-oriented programming. For closed sets of types, its performance roughly equals equivalent code in functional languages, such as OCaml and Haskell. The type-switching code is easier to use and is more expressive than hand-coded visitors are. The library is non-intrusive and circumvents most of the extensibility restrictions typical of the visitor design pattern. It was motivated by applications involving large, typed, abstract syntax trees.

An increasing number of modern real-time systems and the nowadays ubiquitous multicore architectures demand the application of programming techniques for reliable and efficient concurrent synchronization. Some recently developed Compare-And-Swap (CAS) based nonblocking techniques hold the promise of delivering practical and safer concurrency. The ABA problem is a fundamental problem to many CAS-based designs. Its significance has increased with the suggested use of CAS as a core atomic primitive for the implementation of portable lock-free algorithms. The ABA problem's occurrence is due to the intricate and complex interactions of the application's concurrent operations and, if not remedied, ABA can significantly corrupt the semantics of a nonblocking algorithm. The current state of the art leaves the elimination of the ABA hazards to the ingenuity of the software designer. In this work we provide the first systematic and detailed analysis of the ABA problem in lock-free Descriptor-based designs. We study the semantics of Descriptor-based lock-free data structures and propose a classification of their operations that helps us better understand the ABA problem and subsequently derive an effective ABA prevention scheme. Our ABA prevention approach outperforms by a large factor the use of the alternative CAS-based ABA prevention schemes. It offers speeds comparable to the use of the architecture-specific CAS2 instruction used for version counting. We demonstrate our ABA prevention scheme by integrating it into an advanced nonblocking data structure, a lock-free dynamically resizable array.

Generic classes can be used to improve performance by allowing compile-time polymorphism. But the applicability of compile-time polymorphism is narrower than that of runtime polymorphism, and it might bloat the object code. We advocate a programming principle whereby a generic class should be implemented in a way that minimizes the dependencies between its members (nested types, methods) and its generic type parameters. Conforming to this principle (1) reduces the bloat and (2) gives rise to a previously unconceived manner of using the language that expands the applicability of compile-time polymorphism to a wider range of problems. Our contribution is thus a programming technique that generates faster and smaller programs. We apply our ideas to GCC's STL containers and iterators, and we demonstrate notable speedups and reduction in object code size (real application runs 1.2x to 2.1x faster and STL code is 1x to 25x smaller). We conclude that standard generic APIs (like STL) should be amended to reflect the proposed principle in the interest of efficiency and compactness. Such modifications will not break old code, simply increase flexibility. Our findings apply to languages like C++, C#, and D, which realize generic programming through multiple instantiations.

The dynamic cast operation allows flexibility in the design and use of data management facilities in object- oriented programs. Dynamic cast has an important role in the implementation of the data management services (DMS) of the mission data system project (MDS), the jet propulsion laboratory's experimental work for providing a state-based and goal-oriented unified architecture for testing and development of mission software. DMS is responsible for the storage and transport of control and scientific data in a remote autonomous spacecraft. Like similar operators in other languages, the C++ dynamic cast operator does not provide the timing guarantees needed for hard real-time embedded systems. In a recent study, Gibbs and Stroustrup (G&S) devised a dynamic cast implementation strategy that guarantees fast constant-time performance. This paper presents the definition and application of a co-simulation framework to formally verify and evaluate the G&S fast dynamic casting scheme and its applicability in the mission data system DMS application. We describe the systematic process of model-based simulation and analysis that has lead to performance improvement of the G&S algorithm's heuristics by about a factor of 2.

Multiple dispatch - the selection of a function to be invoked based on the dynamic type of two or more arguments - is a solution to several classical problems in object-oriented programming. Open multi-methods generalize multiple dispatch towards open-class extensions, which improve separation of concerns and provisions for retroactive design. We present the rationale, design, implementation, and performance of a language feature, called open multi-methods, for C++. Our open multi-methods support both repeated and virtual inheritance. Our call resolution rules generalize both virtual function dispatch and overload resolution semantics. After using all information from argument types, these rules can resolve further ambiguities by using covariant return types. Great care was taken to integrate open multi-methods with existing C++ language features and rules. We describe a model implementation and compare its performance and space requirements to existing open multi-method extensions and workaround techniques for C++. Compared to these techniques, our approach is simpler to use, catches more user mistakes, and resolves more ambiguities through link-time analysis, runs significantly faster, and requires less memory. In particular, the runtime cost of calling an open multi method is constant and less than the cost of a double dispatch (two virtual function calls). Finally, we provide a sketch of a design for open multi-methods in the presence of dynamic loading and linking of libraries.

Generic programming has emerged as an important technique for the development of highly reusable and efficient software libraries. In C++, generic programming is enabled by the flexibility of templates, the C++ type parametrization mechanism. However, the power of templates comes with a price: generic (template) libraries can be more difficult to use and develop than non-template libraries and their misuse results in notoriously confusing error messages. As currently defined in C++98, templates are unconstrained, and type-checking of templates is performed late in the compilation process, i.e., after the use of a template has been combined with its definition. To improve the support for generic programming in C++, we introduce concepts to express the syntactic and semantic behavior of types and to constrain the type parameters in a C++ template. Using concepts, type-checking of template definitions is separated from their uses, thereby making templates easier to use and easier to compile. These improvements are achieved without limiting the flexibility of templates or decreasing their performance - in fact their expressive power is increased. This paper describes the language extensions supporting concepts, their use in the expression of the C++ Standard Template Library, and their implementation in the ConceptGCC compiler. Concepts are candidates for inclusion in the upcoming revision of the ISO C++ standard, C++0x.

C++ templates are key to the design of current successful mainstream libraries and systems. They are the basis of programming techniques in diverse areas ranging from conventional general-purpose programming to software for safety-critical embedded systems. Current work on improving templates focuses on the notion of concepts (a type system for templates), which promises significantly improved error diagnostics and increased expressive power such as concept-based overloading and function template partial specialization. This paper presents C++ templates with an emphasis on problems related to separate compilation. We consider the problem of how to express concepts in a precise way that is simple enough to be usable by ordinary programmers. In doing so, we expose a few weakness of the current specification of the C++ standard library and suggest a far more precise and complete specification. We also present a systematic way of translating our proposed concept definitions, based on use-patterns rather than function signatures, into constraint sets that can serve as convenient basis for concept checking in a compiler.

Abstract We describe a scheme for implementing dynamic casts suitable for systems where the performance and predictability of performance is essential. A dynamic cast from a base class to a derived class in an object‐oriented language can be performed quickly by having the linker assign an integer type ID to each class. A simple integer arithmetic operation verifies whether the cast is legal at run time. The type ID scheme presented uses the modulo function to check that one class derives from another. A 64‐bit type ID is sufficient to handle class hierarchies of large size at least nine levels of derivation deep. We also discuss the pointer adjustments required for a C++ dynamic_cast. All examples will be drawn from the C++ language. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.

Reuse happens only when a variety of social conditions are favorable. However, social conditions, development processes, and design methods alone cannot guarantee success. In the end, working code must be produced, and at this stage programming languages and programming styles can make a critical difference. The paper focuses on C++ and its use because that's where the author's experience is, and because reuse in the abstract is a sterile exercise. To yield its obvious benefits, reuse must be practised. Reuse is a result of good design; it is not something you get from simple minded use of special language features. The paper presents examples of how designs of components for use in several contexts can be expressed directly and efficiently in C++. Concrete types, abstract classes, class hierarchies, and generic programming using templates are mentioned.

Abstract The C language is a fine tool for writing compact and efficient programs. It is relatively easy to produce good compilers for, and the number of tools available for supporting program‐ ming in C is large, especially in its ‘home environment’, the UNM system. However, C'S facilities for structuring programs were, until recently, rather limited. To remedy this situation, a data abstraction facility, called classes, was added. The class concept described here has benefitted from the experience gained through a year's use. It is now in use at close to a hundred installations. The guiding principles of the design of C classes were simplicity both in concept and in implementation. Smooth blending of the new facilities into the existing C programming environment was considered essential. Classes can be used without sacrificing the run‐time efficiency expected from C. This paper presents some of the reasons why C classes are what they are.

Abstract Two styles of operating system implementation based on the use of monitors and processes, respectively, are identified, and arguments for a basic equivalence of these systems despite large stylistic differences are presented. The ‘Lauer‐Needham Duality Hypothesis’ states that the two styles are equivalent, both in terms of ease of programming and in efficiency of the resulting systems. A domain for which the first part of this claim holds is outlined, and data affirming the essential equivalence of performance within that domain are presented. An operating system based on the Cambridge CAP system, called SIMOS, was simulated for a wide range of hardware configurations and job loads. SIMOS is written using a module concept that allows an individual module to be interpreted as a monitor in one run and as a process in another. Runs using a monitor to control access to some data can be compared with runs using a process to control access to the same data. The throughput and response time for the two styles of system were found to be identical in most cases. However, a degradation in response time occurred in a process‐based system when the job load and the low level scheduling policy were poorly matched.

Abstract This paper describes a concept called ‘long return’ for use in inter‐module communication systems. First an implementation which implies a simplification of—rather than an extension of—traditional inter‐module communication systems is outlined. This implementation allows long returns to be used as an optimization technique without violating the commonly accepted principles of system structuring. Thereafter an experiment that provides an estimate of the improvements in efficiency of a particular operating system is described. In the SIMOS operating systems (based on the Cambridge CAP operating system) about 20 per cent of all inter‐process communication operations can be avoided by using long returns, and as a consequence the amount of useful work done in the system is typically increased by about 2.0 per cent.