`— layout: post title: “Understand the STL”

Understanding STL

I want to understand the Standard Template Library (STL) in excruciating detail and the best way is to implement something. I’m starting off withstd::vector as it is relatively simple algorithmically but a fundamental container.

This is not intended for production use. It is targeting C++-23. There’s no attempt to be portable or backward compatible beyond following good practices. There’s no obfuscating names with __ to avoid conflicts with other code.

No std:: code (mostly)

Ideally, no std code is used. However, some exceptions are made:

  • <functional>, <limits> and <stdexcept> are used from std because it seems like a lot of work for not much gain.
  • <new> is used for placement new
  • <initializer_list> is a compiler specific struct
  • <type_traits> for std::is_base_of
  • <iterator> as I needed to use the same iterator tag The namespace is pw and include files are pw/<name>. Most of the actual implementations are in pw/impl/<file.h>. In fact, most of the STL include files consist primarily of including various implementation files.
  • <iosfwd>, <iostream> as wanted to generate some types
  • <string>

Namespace/structure

  • The namespace pw is analogous to std
  • The files in pw/ like pw/vector implement the STL. These are the public interfaces and should be used by other code.
  • The files in pw/impl/ are the implementation and are in the namespace pw.
  • The namespace pw::internal is for private details and are in pw/internal/. These should not be used by other code.
  • The namespace pw::test is utilities for testing and is in tests/test/<file.h>.
  • The unit tests are in tests/unit/ and use the Catch2 framework. Currently release 3.9.1 as specified in tests/unit/CMakeLists.txt.

Testing

The tests are tagged with phases to provide an orderly way to develop functionality.

The declaration of pw::vector is in pw/vector_decl.h. There are two implementations:

  • pw/vector_defn.h: This is the full implementation of pw::vector and relies heavily on pw::internal::Storage in pw/internal/storage.h
  • pw/vector_defn_empty.h: This is the empty implementation that only provides enough code to make the compiler happy. Other than the body of the functions it is identical to pw/vector_defn.h.

Phase 1: Constructors and accessors

The phase1 unit tests require the all the constructors to be implemented. and a few accessors. The phase1 tests do not need make any modifications to a vector so operations like push_back(), insert(), erase(), etc. are not required. However, the tests do expect to be able to use an initializer_list and call operator==(). The phase1 tests do not require the allocators to work correctly (that’s phase2). To make things simple, the phase1 tests use int as the value_type.

In tests/test/test_testtype.h are tuples of types that are passed to Catch2’s TEMPLATE_LIST_TEST_CASE. The phase1 tests use TestTypesPhase1 which uses pw::vector<int> and std::vector<int>. Tests should pass both implementations.

Along with the constructors, these accessors must be implemented:

  • begin(), cbegin()
  • end(), cend()
  • operator[]()
  • operator<=>()
  • front()
  • back()
  • empty()
  • capacity()
  • size()
  • get_allocator()
  • operator==() (free function)
  • operator!=() (free function)

Phase 2: Allocators and constructors

The phase2 unit tests continues testing the constructors but now requires that the allocators are used in constructors. The Phase2TestTypeList uses pw::vector<int, allocator_base> and std::vector<int, allocator_base>.

The allocator_base, in allocator terminology, is a “stateful” allocator with an m_instance member data. The following types are all set to false_type:

  • propagate_on_container_copy_assignment
  • propagate_on_container_move_assignment
  • propagate_on_container_swap
  • is_always_equal

The following types set the type to true_type:

  • pw::test::allocator_copy_assignment makes propogate_on_container_copy_assignment to true_type
  • pw::test::allocator_move_assignment makes propogate_on_container_move_assignment to true_type
  • pw::test::allocator_swapable makes propogate_on_container_swap to true_type
  • pw::test::allocator_is_always_equal makes is_always_equal to true_type

Phase 3: Modifiers

The phase3 unit tests require the modifiers to be implemented and that they use allocators for memory management.

How to proceed

An iterative process of writing code to implement vector and when that requires other code from STL digress until that other code is done.

Depending on the complexity or need these digressions may not fully implement the standard.

The declaration

Here is the first step pw_vector.h:

#ifndef INCLUDED_PW_VECTOR_H
#define INCLUDED_PW_VECTOR_H

namespace pw {

template<class Type, class Allocator>
class vector
{
public:
};
}

#endif /*  INCLUDED_PW_VECTOR_H */

and the first digression: the Allocator needs a default allocator.