Is everything in C++11 STL user-implementable?

Question

I know that libs like <map>, <vector> and <algorithm> can be implemented by user even if they do not exist in the standard libraries.

But is some of the classes or functions in C++11 STL just "compiler-magic" that cannot be implemented manually?

---

EDIT By STL, I meant the standard template libraries, which do not requires extra linking.

Answer 1

The typeid operator which depends on the <typeinfo> header is one example.

The other case is the initializer_list, which is basically a library add-on with special core language privileges. It is for example considered in variable initialization rules.

I guess there are more things that are both add-on libraries and base language constructs, but those are the ones I can remember for now.

Answer 2

I'm assuming you mean the C++11 standard library, not the STL (which is a library of algorithms, iterators and containers from the 1990s).

The answer depends what you mean by "implemented manually". Do you mean in pure C++? i.e. no assembly code and no OS-specific features such as POSIX memory allocation functions, or even lower-level system calls to the kernel?

Because if you're prepared to write assembly and call directly into the kernel, you can implement nearly everything, but it's not very practical. Even writing your own std::malloc() or operator new is very hard without building it on top of something lower-level such as sbrk(). Without something like malloc it's hard to write std::allocator and so hard to implement std::vector!

std::system_clock also relies on facilities provided by the operating system, you either need a lower-level API such as POSIX's clock_gettime() or access to a hardware clock in the CPU. Even std::time() defined in <ctime> needs something like that.

So let's assume relying on the C library for features such as malloc is OK, but we want to avoid writing assembly and non-C++.

It is not possible to implement std::atomic efficiently in pure C++. You need some compiler magic or assembly code to provide the necessary synchronization guarantees. The libstdc++ implementation of std::atomic relies on GCC's __atomic built-ins which are "compiler magic". The libc++ implementation of std::atomic makes use of the _Atomic keyword, which is defined by C11 and supported by clang++ but is not defined in standard C++. In both cases the library implementation relies on non-standard features of the compiler to provide the platform-specific assembly necessary to provide the required behaviour.

Alternatively, you could just implement std::atomic inefficiently using a mutex, but that just shifts the requirement for "magical" synchronization properties onto the mutex type. At the very least, an implementation needs to provide std::atomic_flag which can't be done in pure C++. Without std::atomic_flag the other atomic types and std::mutex cannot be implemented in pure C++, so require either platform-specific assembly code, or require using a lower-level library such as Pthreads which provides the necessary primitives (which themselves will either be implemented in assembly or with non-portable compiler magic).

As pointed out at How does std::async "store" an arbitrary exception? there are parts of the C++ runtime such as std::typeinfo and std::exception_ptr which can be written in C++, but not portably. The runtime has to define the data structures and internal details of RTTI and exception handling, and provide entry points that the compiler will call so that e.g. throw in your C++ code calls the relevant routine from the runtime to allocate an exception object. So you could implement those things yourself, but unless you conform to the right API the compiler won't use them so they won't work!

But even if you're prepared to write assembly and call directly into the kernel, several type traits rely on compiler magic and cannot be implemented by the user, for example is_standard_layout, is_trivial, is_trivially_constructible and the other is_trivially_xxx traits. These all depend on properties of a type which cannot be tested for in code, only the compiler can do the necessary inspection and tell you if a type has the property (and the same applies to the C++14 is_final trait).

Answer 3

If you mean the part of the standard library that originated from Alexander Stepanov's Standard Template Library, then you can implement all of it without any compiler "magic" (i.e., you only need normal functionality that's required by the rest of the C++ standard).

Algorithms operate on iterators. The operations they need from the iterator are defined by the class of iterator on which they operate (see below). The algorithm simply carries out normal operations such as assigning to elements and swapping elements.

All iterators provide a few operations such as increment and dereference. Bidirectional iterators also provide decrement, and random access iterators provide addition/subtraction. None of these is particularly complex it implement using standard compiler features.

Containers are similar to algorithms in that they mostly operate on data via iterators. They also use allocator classes to allocate memory, create objects in that memory, and so on. Although writing an allocator used to be fairly complex (and the requirements poorly documented) C++11 has simplified the task considerably (and it never required anything non-standard).

If you take "STL" to mean the STandard Library in general, then yes, there are quite a few parts that require some compiler magic of various sorts.

Some of these are defined in terms of lower-level components, so (for example) iostreams are defined in terms of C's getchar/puthchar¹ to get data from/to the outside world. Other parts (e.g., type traits, std::uncaught_exception) provide an interface to data that's generated by the compiler, but isn't available to portable code by other means.

---

^{1. Note, however, that even though iostreams are defined in terms of reading and writing via C functions, they're not required to actually use those C functions, just to do the same things as if they had.}

Answer 4

Not all of them are user-implementable. Some classes can only be implemented with compiler extensions.

GCC provides the "compiler-magic" for type traits.

• https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/Type-Traits.html#Type-Traits

GCC also provides atomic builtins,

• https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/_005f_005fatomic-Builtins.html#_005f_005fatomic-Builtins

initializer_list is usually implemented on that compiler itself has access to the private function, which is in this case the constructor.