Edit  History 
  Sep 15 '23
Please feel free to contribute
This is an older version of the article. Click here to see the current one.

Writing custom C++ containers, iterators and value references

Generic containers are awesome.

  1. The effort required to write a container and access data no longer affects the design of a good system. Efficient bug free code need only be written once. A common interface allows reuse.
  2. More mistakes can be caught at compile time. Type safety is amazing. Long gone should be the days of writing inline linked list access, where each time there’s a chance to mess something up. No really, please stop.

Good code is modular. Great code strikes a balance in the boundaries of its modules — the internal implementation can be optimized (bigger is better) but every bit of code needs to work with every other bit of code within the interface boundary and that’s hard to maintain (smaller is better). Abstractions are great, but they cost and can hurt performance. Containers are an easy example where good boundaries are fairly intuitive. See High Cohesion, Loose Coupling and Single-responsibility. When discussing containers, performance and modularity I think Structure of Arrays is an important thing to bring up.

One concept I’ve recently started to respect is iterator safety over indices.

for(size_t i = 0; i < foo.size(); ++i)
{
    doSomethingWithBar(bar[i]);
}

This is a simple mistake that the compiler should be able to help with. Imagine a more complex example with many arrays and nested loops. A further issue is iterating over a structure of arrays, but perhaps zip will be a solution there.

When conforming to existing C++ convetions, some things just become easier. Consider the following:

void convertArrayFooToBar(FooInput, BarOutput);
void convertArrayBarToFoo(BarInput, FooOutput);
void convertArrayFooToBaz(FooInput, BazOutput);
void convertArrayBazToFoo(BazInput, FooOutput);
void convertArrayBazToBar(BazInput, BarOutput);
void convertArrayBarToBaz(BarInput, BazOutput);

Sure, each function can internally use a common templated conversion function but that’s still only written for this one specific example. If these array types were iterator compatible it would be far easier to write generic code for them; once, without the chance for mistakes in each one or forgetting a permutation.

// Fine-grained object conversion functions
namespace FooBarBaz {
template <class Result, class From> Result convert(const From& value);
template <> Bar convert(const Foo& value) { ... specialize }
...
}

// Single convert-anything template
template <class ArrayResult, class ArrayFrom>
void convertArray(const ArrayFrom& input, ArrayResult& output)
{
    using ResultType = typename ArrayResult::value_type;
    std::transform(std::begin(input),
                   std::end(input),
                   std::begin(output),
                   [](const auto& foo){ return FooBarBaz::convert<ResultType>(foo); });
}

Example use cases

A few ideas to demonstrate how amazing custom containers can be.

  1. std::vector uses separate heap allocations. What if you just need a small vector of items that live on the stack. This could even fall back to heap allocations, e.g. eastl::fixed_vector.
  2. One could make a circular buffer.
  3. std::span assumes contiguous data. In computer graphics it’s common to interleave values in memory. Extending it with a stride would allow more convenient views of data.
  4. Pointers don’t work between address spaces, e.g. addresses within a file on disk or within a shared memory block. Boost’s offset_ptr instead holds a relative offset from its own memory address. Containers to traverse memory-mapped files could be written around this concept.

Container

The container itself is often the simpler object to implement. It just holds the data, or references it in the case of views. The iterator is where the complexity may lie.

The main thing a container needs is a begin() and end() function. With those, you get a pile of things for free. In C++ 20 begin and end are grouped into ranges and with range adaptors existing containers “just work”™ with other library features.

class my_container {
public:
    my_iterator begin() { ... }
    my_iterator end() { ... }

private:
    ???
};

The next main thing are some common functions such as size() and types such as a value_type, a.k.a. named requirements.

Named Requirements and Concepts

C++ templates are evaluated when they’re used. There’s no formal declaration ahead of time. For example, you can write:

template<class T>
Result doThing(const T& object) {
    return object.thing();
}

Being a template, this code doesn’t get compiled until you make the call doThing(my_object);. At that point, the function doThing for my_object‘s type gets generated and compiled. If the type doesn’t have a member function thing() then compilation will fail. Named requirements are basically a convention without formal validation where you say “objects I want to call doThing() with will all have a .thing(). Thankfully, C++ 20 introduced concepts to do better formal validation of templates.

C++ named requirements: Container

At the time of writing there are no official concepts for containers, but ranges has Range concepts.

Many of these requirements can be written by reusing another single definition, e.g. using value_type = typename iterator::value_type; or implementing operator[] as return *(begin() + index);.

Here’s a boilerplate example. Fair warning, this is not well tested. Full source code is available on GitHub.

template <class T, size_t N>
class my_container {
public:
    using value_type      = T;
    using iterator        = my_iterator<value_type>;
    using const_iterator  = my_iterator<const value_type>;
    using reference       = decltype(*std::declval<iterator>());
    using const_reference = decltype(*std::declval<const_iterator>());
    using size_type       = size_t;

    my_container() : m_array{} {};
    my_container(const my_container& other) noexcept = default;
    my_container(std::initializer_list<T> init) {
        std::copy(init.begin(), init.end(), begin());
    }

    // Copy constructor that also handles const conversion
    template <class U, class = std::enable_if_t<std::is_same_v<T, U> ||
                                                std::is_convertible_v<U, T>>>
    explicit my_container(my_container<U, N>& other) {
        std::copy(other.begin(), other.end(), begin());
    }

    template <class Iterator>
    my_container(Iterator init_begin, Iterator init_end) {
        std::copy(init_begin, init_end, this->begin());
    }

#ifdef __cpp_lib_ranges
    template <std::ranges::input_range Range>
    my_container(Range&& range) {
        std::ranges::copy(range, this->begin());
    }
#endif

    reference operator[](size_type index) noexcept {
        return *(begin() + index);
    }
    const_reference operator[](size_type index) const noexcept {
        return *(begin() + index);
    }

    iterator       begin() noexcept { return iterator(m_array); }
    const_iterator begin() const noexcept { return const_iterator(m_array); }
    iterator       end() noexcept { return begin() + N; }
    const_iterator end() const noexcept { return begin() + N; }

    value_type*       data() noexcept { return m_array; }
    const value_type* data() const noexcept { m_array; }
    size_type         size() const noexcept { return N; }
    reference         front() noexcept { return *begin(); }
    const_reference   front() const noexcept { return *begin(); }
    reference         back() noexcept { return *(end() - 1); }
    const_reference   back() const noexcept { return *(end() - 1); }

private:
    value_type m_array[N];
};

While writing the container it is invaluable to already have some test cases in place. There are a lot of great compile time tests that the standard library already provides.

// Copy construction
static_assert(std::is_copy_constructible_v<my_view<int>>);
static_assert(std::is_trivially_copy_constructible_v<my_view<int>>);

// Const conversion
static_assert(std::is_constructible_v<my_view<const int>, my_view<int>>,
              "can't make const view from non-const view");
static_assert(!std::is_constructible_v<my_view<int>, my_view<const int>>,
              "can make non-const view from const view");

Iterator

Iterators can just be raw pointers and it’s way easier if they actually are. That said, std::vector and std::span probably cover most uses for pointer-only iterators so I imagine it’s uncommon to have a container that doesn’t also need a custom iterator class. In my experience, the iterator class is often where most of the complexity lies.

Here’s a boilerplate iterator example. Again, this is not well tested. While the iterator itself could be a raw pointer, i.e. template <class T> my_iterator = T*;, this class instead has a value_type* m_ptr; to demonstrate various operators, types and my_value_reference.

template <class T>
class my_iterator {
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using reference         = my_value_reference<T>; // could just be value_type&
    using const_reference   = reference;             // must be the same

    my_iterator() noexcept                                    = default;
    my_iterator(const my_iterator& other) noexcept            = default;
    my_iterator& operator=(const my_iterator& other) noexcept = default;

    // TODO: implement this
    my_iterator(value_type* ptr) noexcept : m_ptr(ptr) {}

    reference operator*() noexcept {
        // TODO: implement this
        return *m_ptr;
    }

    const_reference operator*() const noexcept {
        // TODO: implement this
        return *m_ptr;
    }

    reference operator[](difference_type index) noexcept {
        return *(*this + index);
    }

    const_reference operator[](difference_type index) const noexcept {
        return *(*this + index);
    }

    my_iterator& operator++() noexcept {
        // TODO: implement this
        ++m_ptr;
        return *this;
    }

    my_iterator operator++(int) noexcept {
        my_iterator temp = *this;
        ++(*this);
        return temp;
    }

    my_iterator& operator--() noexcept {
        // TODO: implement this
        --m_ptr;
        return *this;
    }

    my_iterator operator--(int) noexcept {
        my_iterator temp = *this;
        --(*this);
        return temp;
    }

    my_iterator& operator+=(difference_type n) noexcept {
        // TODO: implement this
        m_ptr += n;
        return *this;
    }

    my_iterator operator+(difference_type n) const noexcept {
        my_iterator result(*this);
        return result += n;
    }

    friend my_iterator operator+(difference_type    n,
                                const my_iterator& it) noexcept {
        return it + n;
    }

    my_iterator& operator-=(difference_type n) noexcept {
        return *this += (-n);
    }

    my_iterator operator-(difference_type n) const noexcept {
        return *this + (-n);
    }

    friend my_iterator operator-(difference_type    n,
                                const my_iterator& it) noexcept {
        return it - n;
    }

    difference_type operator-(const my_iterator& other) const noexcept {
        return std::distance(other.m_ptr, m_ptr);
    }

    bool operator==(const my_iterator& other) const noexcept {
        return (other - *this) == 0;
    }

    bool operator!=(const my_iterator& other) const noexcept {
        return !(*this == other);
    }

    bool operator<(const my_iterator& other) const noexcept {
        return 0 < (*this - other);
    }

    bool operator<=(const my_iterator& other) const noexcept {
        return 0 <= (*this - other);
    }

    bool operator>(const my_iterator& other) const noexcept {
        return 0 > (*this - other);
    }

    bool operator>=(const my_iterator& other) const noexcept {
        return 0 >= (*this - other);
    }

private:
    value_type* m_ptr = nullptr;
};

Again, compile-time validation with static_assert can help catch bugs way before they happen or you start trying to use the container in real code.

template <class iterator>
concept input_and_output_iterator =
    std::input_iterator<iterator> &&
    std::output_iterator<iterator, typename std::iterator_traits<iterator>::value_type>;

static_assert(std::ranges::random_access_range<my_container>);
static_assert(std::ranges::sized_range<my_container>);
static_assert(input_and_output_iterator<typename my_container::iterator>);

Value reference

Typically iterators will dereference directly to their value type. This is generally easy for const access. However sometimes it’s not possible to return a writable reference. A reference wrapper or proxy object can be used instead. For example,

  • The value is encoded differently in memory such as a bitfield. In this case, the reference wrapper provides operator value_type() const and operator=(const value_type& value) to read and write values respectively.
  • The value is cached and its reference must not go out of scope while in use. The reference wrapper could hold a reference count (TBH, this sounds rather expensive).

Here’s a boilerplate value reference example. Again, this is not well tested.

template <class T>
class my_value_reference {
public:
    using value_type = T;

    my_value_reference() = delete;
    my_value_reference& operator=(const my_value_reference& other) {
        return operator=(other.operator value_type());
    }
    my_value_reference(value_type& reference) noexcept
        : m_reference{reference} {}
    my_value_reference& operator=(const value_type& value) {
        m_reference = value;
        return *this;
    }
    const my_value_reference& operator=(const value_type& value) const {
        m_reference = value;
        return *this;
    }
    operator value_type() const { return m_reference; }

private:
    value_type& m_reference;
};

Extras

Rule of three, five and zero

Rule of Three: If you make a custom destructor, copy constructor, or copy assignment operator, make sure to define all three.

Rule of Five: Add move constructor and move assignment operator to the Rule of Three.

Rule of Zero: Ideally, have none. It might be possible to move resource management to individual members so that aggregate classes don’t need to do anything special.

See here for reference.

Const objects

Const containers, iterators and value references can be confusing especially when combined with const values. Remember that a const pointer can point to non-const (mutable) data. An iterator should be considered like a pointer. Whether you have a const iterator or not, the iterator’s value_type would be the same. In fact, iterator concepts validate that iterator::reference is the same as iterator::const_reference. However, the container’s const_iterator::reference may be a const value_type& which it would be for the case of std::vector but not std::span.

A container for type T is a different type to a container of type const T and there is no cast between them (well, reinterpret_cast would do it but that’d be undefined behaviour, e.g. if the const T type were to specialize its memory layout). One use case is when trying to make a const object immutable despite having non-const pointers, in which case there are wrappers such as propagate_const to provide a transitive/deep const view of an object.

Exceptions

Just like const, adding noexcept can allow the compiler to make some optimizations. Libraries can also check methods with the noexcept() operator.

For example, containers such as std::vector will move their elements if the elements’ move constructor is noexcept, and copy otherwise…

Note that the compiler won’t validate that called functions are also noexcept and std::terminate() is called if one actually happens to throw.

Testing

Sadly not everything can be compile-time validated. Unit testing is important, especially for generic containers that will see a lot of use and are expected to work in all cases. I wish there were some standard test suites people could easily throw at their own containers. Maybe there are and I just haven’t found them. gcc and llvm have standard library test suites, but they’re very likely not easily pluggable with custom containers.

Performance

I’m always surprised when the compiler is able to optimize crazy amounts inline functions away completely. In many cases, custom C++ iterators are just as fast to execute as writing out C structures and code by hand. That said, all intermediate operations still need to conform to C++ spec. If a copy constructor for an iterator gets called, it gets called, and the compiler needs to optimize it away. Sometimes a little mistake can lead to something significant and as always testing is needed.

Benchmark

Profile some basic loops over items in your container and compare them to bare bones hand written loops with plain old data structs. For example, the repository for above code samples includes test_benchmark.cpp.

Compiler output

If the benchmarks aren’t looking good, take the loops and throw each into godbolt. E.g. void loop_with_my_container() and void loop_with_raw_array(). Remember to compile with -O2.

Debug Performance

One major drawback to custom C++ containers is their performance in debug builds. Benchmarks show an easy 10x or more penalty. One thought is if it’s possible to switch on optimizations and disable debug code generation for custom containers (after, and separately to thoroughly testing them of course). This is possible to do with compiler specific pragma directives GCC’s #pragma GCC optimize or MSVC’s #pragma optimize(), but I have not tried this yet.