C++ Concepts Got There the Hard Way, and the Design Scars Show Why That Matters
Source: isocpp
Bjarne Stroustrup published a teaching paper on concept-based generic programming in late 2025, presenting C++20 concepts as a coherent programming paradigm rather than a syntax feature. Reading it as a retrospective is worthwhile, because the feature it describes arrived only after a public failure that reshaped how the committee thinks about language complexity.
The paper’s core claim is that C++ generic programming has always been concept-based in intent. std::sort required a RandomAccessIterator. std::find required an InputIterator. These were real constraints with real algorithmic significance; they just existed only in documentation, not in the language. Every programmer who passed a linked list to std::sort and received a hundred lines of substitution errors learned this the hard way. Stroustrup’s position is that making concepts first-class language features was not adding something new, but finally expressing what was already there.
Two Attempts, One Standard
The first concepts proposal targeted C++11, then called C++0x. It was a comprehensive design with genuine theoretical rigor, built around concept maps: explicit declarations that told the compiler how a given type satisfied a given concept.
// C++0x design (never shipped)
concept InputIterator<typename Iter> {
typename value_type;
Iter& operator++(Iter&);
value_type operator*(Iter);
}
concept_map InputIterator<int*> {
typedef int value_type;
};This is structurally similar to Haskell’s typeclass instances or Rust’s impl Trait for Type blocks. The compiler needed explicit evidence that a type satisfied a concept; nothing was inferred structurally. The design had real advantages: it was coherent (one concept map per type per concept, compiler-enforced), it matched mathematical practice, and it allowed types to satisfy concepts they were never designed for without accidental matching.
The Frankfurt meeting in 2009 voted the entire proposal out of C++0x. The design had become too large, GCC’s experimental implementation ran to hundreds of thousands of lines, and compile times on even simple programs were unacceptable. The standard shipped as C++11, without concepts.
The redesign that became C++20 took a different philosophical position. Andrew Sutton led the work, with Stroustrup’s involvement throughout. The central change was dropping concept maps entirely. Instead of nominal satisfaction, C++20 uses structural satisfaction: a type satisfies a concept if the expressions in the concept’s requires clause compile for that type. No declarations needed.
// C++20 - structural, no declarations
template <typename T>
concept InputIterator = requires(T it) {
++it;
*it;
typename T::value_type;
};
// int* satisfies this automatically - no concept_map needed
void consume(InputIterator auto it) { /* ... */ }This aligns with C++‘s existing duck typing model. Templates have always been structural; concepts, in C++20, follow that same tradition.
What Structural Satisfaction Costs
The tradeoff is coherence. In Haskell, there is exactly one Eq instance per type, compiler-enforced. In Rust, the orphan rules ensure no two crates can define conflicting impl Trait for Type blocks. In C++20, none of this exists. A type either satisfies a concept or it does not, and there is no registration mechanism. You cannot have two different “views” of the same type satisfying the same concept through different adapters.
For most use cases, this does not matter. For the cases where it does, you use wrapper types, which is the same solution C++ programmers have always used. The C++ committee made a practical choice: get the 95% case right without the mechanism complexity, and trust programmers to handle edge cases manually.
The thing the 2009 design got right was a deeper problem: semantic requirements. Some constraints cannot be expressed syntactically. std::sort requires that its comparator define a strict weak ordering, which means it must be irreflexive, asymmetric, and transitive. No requires expression can verify this. The C++0x design had axioms for exactly this, letting you write:
concept StrictWeakOrder<typename Comp, typename T> {
axiom Irreflexivity(T a) { !comp(a, a); }
axiom Asymmetry(T a, T b) { if (comp(a, b)) !comp(b, a); }
axiom Transitivity(T a, T b, T c) {
if (comp(a, b) && comp(b, c)) comp(a, c);
}
}Axioms were dropped from C++20. They carry semantic content the compiler cannot verify, so they become documentation, which is what we had before. Stroustrup’s paper discusses this gap without resolving it; the honest position is that concept-based programming in C++ guarantees syntactic correctness but leaves semantic correctness to the programmer.
The requires Expression Fills In Where SFINAE Failed
The concrete day-to-day improvement is over enable_if. Here is what detecting a .size() member looked like before C++20:
template <typename T>
class has_size {
template <typename U>
static auto check(U* p) -> decltype(p->size(), std::true_type{});
static std::false_type check(...);
public:
static constexpr bool value = decltype(check((T*)nullptr))::value;
};
template <typename T, std::enable_if_t<has_size<T>::value, int> = 0>
void print_size(const T& container) {
std::cout << container.size() << '\n';
}With concepts:
template <typename T>
concept HasSize = requires(const T& t) {
{ t.size() } -> std::convertible_to<std::size_t>;
};
template <HasSize T>
void print_size(const T& container) {
std::cout << container.size() << '\n';
}The error messages follow the same improvement curve. SFINAE failures produce substitution chains routed through <type_traits> internals. Concept failures produce a direct statement: “T does not satisfy HasSize,” with the specific failing expression identified.
Subsumption is the other major practical benefit. When two constrained overloads both match a call, the compiler picks the more constrained one automatically. This makes the iterator dispatch pattern clean:
template <std::input_iterator It>
void advance(It& it, std::ptrdiff_t n) {
while (n--) ++it; // O(n)
}
template <std::random_access_iterator It>
void advance(It& it, std::ptrdiff_t n) {
it += n; // O(1)
}
std::list<int>::iterator lit = mylist.begin();
std::vector<int>::iterator vit = myvec.begin();
advance(lit, 5); // calls first overload
advance(vit, 5); // calls second overload, subsumedstd::random_access_iterator subsumes std::input_iterator because its definition includes every constraint from std::input_iterator plus additional ones. The compiler proves this at compile time through constraint normalization, selecting the stricter match without any manual disambiguation.
Where C++ Sits in the Language Landscape
Comparing C++20 concepts to equivalent mechanisms in other languages clarifies what the structural approach actually traded.
Rust traits are nominal. When you write fn sort<T: Ord>(slice: &mut [T]), the compiler needs an explicit impl Ord for T somewhere in scope. This gives Rust coherence guarantees and lets trait objects (dyn Ord) exist at runtime. C++ concepts have neither of these properties; they are purely compile-time predicates with no runtime component and no coherence enforcement.
Swift protocols sit between the two. They require explicit conformance declarations, support runtime dispatch through existentials (any Protocol), and allow protocol extensions to provide default implementations. The last part has no equivalent in C++20 concepts, which are predicates only; they impose no obligations on the type and provide no default implementations.
Haskell typeclasses are the most structurally different. They compile to implicit dictionary arguments, making them zero-cost in compiled code while retaining the coherence and evidence model. Higher-kinded constraints (Functor f, where f :: * -> *) have no direct equivalent in C++ concepts, which operate on concrete types.
The structural approach C++20 chose means that a type can “accidentally” satisfy a concept. A class with an operator++ and an operator* satisfies InputIterator even if the author never intended iterator semantics. Nominal systems prevent this. Whether accidental satisfaction is a problem depends on context; in generic algorithm libraries it rarely is, because the algorithms are designed to work on any type meeting the syntactic requirements regardless of the type’s intent.
The Paradigm Stroustrup Is Describing
The paper frames concept-based generic programming as distinct from both object-oriented and procedural styles. The key difference is that algorithms are written against abstract requirement sets, not concrete types, and those requirement sets form a refinement hierarchy analogous to mathematical structures.
Alexander Stepanov designed the STL around this idea long before the language supported it. InputIterator refines into ForwardIterator refines into BidirectionalIterator refines into RandomAccessIterator; each refinement adds obligations on the type and enables more efficient algorithms. The same dispatch pattern that shows up in std::advance appears throughout the standard library.
What C++20 adds is the ability to express this hierarchy in code rather than prose, to enforce it at the call site rather than at the instantiation, and to use subsumption to select optimal implementations automatically. The concepts themselves do not change the algorithms; they make the implicit structure of the algorithms explicit and machine-checkable.
Stroustrup’s paper is worth reading as a programming techniques document rather than a language reference. The cppreference entry on constraints and concepts covers the syntax; the paper covers the reasoning behind how to organize generic code around named abstractions, how to build concept hierarchies, and how to think about the relationship between a template’s interface and its implementation. It took twenty years and one failed standard to arrive at this design, and understanding why the first attempt failed makes the current design more legible.