Understanding the Foundation of libc++ STL Source Code — SFINAE

In my opinion, when learning system programming languages (C++/Rust/C), one should not be impatient; it is essential to build a solid foundation to progress further.

Before we delve into the libc++ STL source code, we need to understand a concept called SFINAE. SFINAE stands for Substitution Failure Is Not An Error, which translates to ‘substitution failure is not an error.’

In this article, we will explain the following concepts:

• What is SFINAE
• How to use SFINAE
• Template specialization

What is SFINAE

SFINAE (Substitution Failure Is Not An Error) is a fundamental principle in C++. It applies during the substitution of template function/template specialization parameters; when a template parameter substitution fails, the compiler does not report an error but instead ignores that candidate.

For example, the following sample code is quite common in the standard library:

template<typename T>
typename T::size_type len(const T&t) {
    return t.size();
}

std::size_t len(...) {
    return 0;
}

In the above, len(…) is a fallback function, which will be chosen as a candidate when the compiler finds no corresponding candidates during the function overload resolution phase.

We will discuss the use of template specialization and SFINAE in subsequent sections. Now, let’s look at the scenarios where SFINAE will take effect.

How to use SFINAE

SFINAE does not take effect in every scenario. To apply SFINAE, it must be in an immediate context. Below are scenarios that are not in an immediate context (instances caused by template function or template specialization parameter substitution):

• The definition of a class template (i.e., its body and list of base classes)
• The definition of a function template (body and, in the case of a constructor, its constructor-initializers)
• The initializer of a variable template
• A default argument
• A default member initializer
• An exception specification
• Any implicit definition of special member functions triggered by the substitution

Any scenario that hits the above will lead to a compilation error rather than ignoring the corresponding candidates.

For example, in the following scenario:

template<typename T>
struct IterType {
    using Iter = T*;
};

template<typename T>
void f(IterType<T>::Iter);

template<typename T>
void f(T*);

f<int>(0, 0); // Directly reports an error

Template Specialization

The STL source code extensively uses SFINAE to select the specialized versions of templates while ignoring invalid template specialization versions. Therefore, we will briefly introduce this part, and we will explain it in detail during the source code analysis.

In the C++ standard, templates are divided into the following three types:

• Main template
• Fully specialized template
• Partially specialized template

The main template is a normally defined template, such as the following class template:

template<typename T> // Main template
struct HasOneType {
};

template<>
struct HasOneType<int> {
    using Type = int;
};

template<template<typename...> class Container, typename... Args>
struct HasOneType<Container<Args...>> {
    using Type = Container<Args...>;
};

A fully specialized template refers to the main template, as shown above:

template<>
struct HasOneType<int> {
    using Type = int;
};

Fully specialization must start with template<> and replace all template parameters with specific parameters.

The following code is a specialized version of the main template, which is quite common in the standard library:

template<template<typename...> class Container, typename... Args>
struct HasOneType<Container<Args...>> {
    using Type = Container<Args...>;
};

The specialized version is based on the main template, and the class template of the specialized version can have any template parameters, but only one template parameter can be included after the class template name.

When the compiler sees the following declaration:

typename HasOneType<std::vector<int>>::Type

The compiler will first check if the main template can be instantiated, and then look for the corresponding partially specialized and specialized versions. In this example, the partially specialized version is valid, so it will choose that specialized version and ignore the main specialized version.

This is the role of SFINAE in class templates.

In the following sections, we will refer to the terminology from the book C++ Template Guide 2nd Edition, SFINAE Out; when applying the SFINAE principle to ignore a function template or class template specialization version, we use the term SFINAE Out.

In the next section, we will begin the analysis of the libc++ STL source code, starting with type traits and utility.