Educational implementation of a list in the style of the C++ Standard Library (it is minimal and incomplete, but easier to read than GCC's source).

list.hpp

// -*- coding:utf-8; mode:c++; mode:auto-fill; fill-column:80; -*-

/// @file list.hpp
/// @brief A minimal list implementation copying the style of the C++
///        Standard Library --- it is meant for educational purposes.
/// @author J. Arrieta <[email protected]>
/// @copyright Copyright (c) 2016 Nabla Zero Labs. All rights reserved.
/// @license This software is released under the MIT License.
/// @warning Do not use this turd in production code, or for anything that is
///          not strictly educational. Just use std::list (actually you most
///          likely want std::vector, but you get the idea).
///
/// The MIT License (MIT)
/// Copyright (c) 2016 Nabla Zero Labs
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to
/// deal in the Software without restriction, including without limitation the
/// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
/// sell copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in
/// all copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
/// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
/// IN THE SOFTWARE.

#pragma once
#ifndef LIST_HPP_HEADER_GUARDS
#define LIST_HPP_HEADER_GUARDS

// C++ Standard Library
#include <memory>
#include <iterator>
#include <type_traits>

namespace detail {

/// @brief Base structure for an arbitrary doubly-linked list.
///
/// The @p list_node_base structure contains the minimal infrastructure
/// necessary to implement a doubly-linked list: the previous and next
/// pointers. Notice that @p list_node_base does not have any knowledge of
/// values.
struct list_node_base {

  list_node_base* m_prev { nullptr };
  list_node_base* m_next { nullptr };

  /// @brief Hook this node right before the provided position.
  /// @code
  /// +------+     +----------+
  /// |      +----->          |
  /// | this |     | position |
  /// |      <-----+          |
  /// +------+     +----------+
  /// @endcode
  void
  hook(list_node_base* const position) noexcept
  {
    m_next = position;
    m_prev = position->m_prev;

    position->m_prev->m_next = this;
    position->m_prev         = this;
  }

  /// @brief Unhooks this node from the linked list.
  /// @code
  /// +------+      +------+      +------+
  /// |      +------>      +------>      |
  /// | prev |      | this |      | next |
  /// |      <------+      <------+      |
  /// +------+      +------+      +------+
  /// @endcode
  void
  unhook() noexcept
  {
    m_prev->m_next = m_next;
    m_next->m_prev = m_prev;
  }

};

/// @brief Template class introducing the concept of value.
///
/// The @p list_node<T> template introduces the concept of value to the data
/// structure. Since it derives from @p list_node_base, it can also be included
/// into a linked list, because its parent class provides the necessary
/// machinery.
///
/// Notice that the memory location to store the value is uninitialized
/// storage. This is necessary to separate allocation from construction later
/// on, when allocators are introduced into the picture.
template<typename T>
struct list_node
    : public list_node_base {

  std::aligned_storage_t<sizeof(T), alignof(T)> m_storage;

  /// @brief Return the address of the list node.
  void*
  addr() noexcept
  { return static_cast<void*>(&m_storage); }

  /// @brief Return the address of the list node (const version).
  const void*
  addr() const noexcept
  { return static_cast<const void*>(&m_storage); }

  /// @brief Return a pointer to the value member.
  T*
  valptr() noexcept
  { return static_cast<T*>(addr()); }

  /// @brief Return a pointer to the value member (const version).
  const T*
  valptr() const noexcept
  { return static_cast<const T*>(addr()); }

};

/// @brief Base class for all list iterators.
///
/// This class provides the basic infrastructure for creating list iterators.
struct list_iterator_base {

  using size_type         = std::size_t;
  using difference_type   = std::ptrdiff_t;
  using iterator_category = std::bidirectional_iterator_tag;

  list_node_base* m_node;

  list_iterator_base()
      : m_node() { }

  explicit
  list_iterator_base(list_node_base* x) noexcept
      : m_node(x) { }

  void increment() noexcept
  { m_node = m_node->m_next; }

  void decrement() noexcept
  { m_node = m_node->m_prev; }

  bool operator==(const list_iterator_base& x) const noexcept
  { return m_node == x.m_node; }

  bool operator!=(const list_iterator_base& x) const noexcept
  { return m_node != x.m_node; }

};

/// @brief Template class for generalizing const and non-const iterators.
///
/// Implementing this class reduces code duplication when preparing the const
/// and non-const version of the iterators. I found this style in the SGI
/// implementation of std::list. I liked it better than the style used by
/// Clang's libc++ or GCC's stdlibc++.
template<typename T, typename Ref, typename Ptr>
struct list_iterator
    : public list_iterator_base {
  using iterator       = list_iterator<T, T&, T*>;
  using const_iterator = list_iterator<T, const T&, const T*>;
  using self           = list_iterator<T, Ref, Ptr>;

  using value_type = T;
  using pointer    = Ptr;
  using reference  = Ref;
  using node       = list_node<T>;

  list_iterator() noexcept
      : list_iterator_base() { }

  explicit
  list_iterator(node* x) noexcept
      : list_iterator_base(x) { }

  list_iterator(const iterator& x) noexcept
      : list_iterator_base(x.m_node) { }

  self
  m_const_cast() const noexcept
  { return *this; }

  reference
  operator*() const noexcept
  { return *static_cast<node*>(m_node)->valptr(); }

  pointer
  operator->() const noexcept
  { return static_cast<node*>(m_node)->valptr(); }

  self&
  operator++() noexcept
  {
    this->increment();
    return *this;
  }

  self
  operator++(int) noexcept
  {
    self tmp = *this;
    this->increment();
    return *tmp;
  }

  self&
  operator--() noexcept
  {
    this->decrement();
    return *this;
  }

  self
  operator--(int) noexcept
  {
    self tmp = *this;
    this->decrement();
    return *tmp;
  }

};

/// @brief Base class implementing the memory portion of the list.
///
/// This class deals with allocation, deallocation, construction, and
/// destruction. The "pimpl" derives from allocator to take advantage of the
/// empty base-class optimization.
template<typename T, typename Alloc>
struct list_base {

  using T_alloc_type      = typename std::allocator_traits<Alloc>::template rebind_alloc<T>;
  using T_alloc_traits    = std::allocator_traits<T_alloc_type>;
  using Node_alloc_type   = typename T_alloc_traits::template rebind_alloc<detail::list_node<T>>;
  using Node_alloc_traits = std::allocator_traits<Node_alloc_type>;

  struct list_impl
      : public Node_alloc_type {

    detail::list_node<std::size_t> m_node;

    list_impl() noexcept
        : Node_alloc_type(),
          m_node() { }

    list_impl(const Node_alloc_type& a) noexcept
        : Node_alloc_type(a),
          m_node() { }

    list_impl(Node_alloc_type&& a) noexcept
        : Node_alloc_type(std::move(a)),
          m_node() { }
  };

  list_impl m_impl;

  std::size_t
  get_size() const
  { return *m_impl.m_node.valptr(); }

  void
  set_size(std::size_t n)
  { *m_impl.m_node.valptr() = n; }

  void
  inc_size(std::size_t n)
  { *m_impl.m_node.valptr() += n; }

  void
  dec_size(std::size_t n) const
  { *m_impl.m_node.valptr() -= n; }

  std::size_t
  node_count() const
  { return *m_impl.m_node.valptr(); }

  // Allocation stuff
  typename Node_alloc_traits::pointer
  get_node()
  { return Node_alloc_traits::allocate(m_impl, 1); }

  void
  put_node(typename Node_alloc_traits::pointer p) noexcept
  { Node_alloc_traits::deallocate(m_impl, p, 1); }

  Node_alloc_type&
  get_node_allocator() noexcept
  { return m_impl; }

  const Node_alloc_type&
  get_node_allocator() const noexcept
  { return m_impl; }

  list_base()
      : m_impl()
  { initialize(); }

  list_base(const Node_alloc_type& a) noexcept
      : m_impl(a)
  { initialize(); }

  list_base(list_base&& x) noexcept
      : m_impl(std::move(x.get_node_allocator()))
  { move_nodes(std::move(x)); }

  list_base(list_base&& x, Node_alloc_type&& a) noexcept
      : m_impl(std::move(a))
  {
    if (x.get_node_allocator() == get_node_allocator()) {
      move_nodes(std::move(x));
    } else {
      initialize();
    }
  }

  ~list_base() noexcept
  { clear(); }

  void
  move_nodes(list_base&& x)
  {
    auto* const x_node = std::addressof(x.m_impl.m_node);
    if (x_node->m_next == x_node) {
      initialize();
    } else {
      auto* const node = std::addressof(m_impl.m_node);
      node->m_next = x_node->m_next;
      node->m_prev = x_node->m_prev;
      node->m_next->m_prev = node->m_prev->m_next = node;
      set_size(x.get_size());
      x.initialize();
    }
  }

  void
  initialize() noexcept
  {
    this->m_impl.m_node.m_next = &this->m_impl.m_node;
    this->m_impl.m_node.m_prev = &this->m_impl.m_node;
    this->set_size(0);
  }

  void
  clear() noexcept
  {
    using node = detail::list_node<T>;
    detail::list_node_base* current = m_impl.m_node.m_next;
    while (current != &m_impl.m_node) {
      node* tmp = static_cast<node*>(current);
      current = tmp->m_next;
      T* val = tmp->valptr();
      Node_alloc_traits::destroy(get_node_allocator(), val);
      put_node(tmp);
    }
  }
};

} // namespace detail

namespace nzl {

/// @brief A very limited and incomplete copy of std::list.
///
// This is the full interface. You will notice it does not implement the full
// std::list interface, but my point was to get the code working. I implemented
// it because I wanted to understand the spaghetti code implementing the C++
// Standard Library, and I found it very polluted by macros implementing
// different interfaces to support backward and forward compatibility: I wanted
// a minimal example with "all the parts".
//
// By far, the most confusing aspect to me are the allocators. I still have not
// fully figured them out. To make matters worse, the interface to
// std::allocator and the allocator concept itself will be updated for C++17,
// and I did not get up to speed before finishing this code.
template<typename T, typename Allocator = std::allocator<T> >
class list
    : protected detail::list_base<T, Allocator> {

 private:

  using Base              = detail::list_base<T, Allocator>;
  using T_alloc_type      = typename Base::T_alloc_type;
  using T_alloc_traits    = typename Base::T_alloc_traits;
  using Node_alloc_type   = typename Base::Node_alloc_type;
  using Node_alloc_traits = typename Base::Node_alloc_traits;

 public:

  using value_type             = T;
  using pointer                = typename T_alloc_traits::pointer;
  using const_pointer          = typename T_alloc_traits::const_pointer;
  using reference              = typename T_alloc_traits::value_type;
  using const_reference        = const reference;
  using iterator               = detail::list_iterator<T, T&, T*>;
  using const_iterator         = detail::list_iterator<T, const T&, const T*>;
  using reverse_iterator       = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  using size_type              = std::size_t;
  using difference_type        = std::ptrdiff_t;
  using allocator_type         = Allocator;

 protected:

  using Node = detail::list_node<T>;
  using Base::m_impl;
  using Base::put_node;
  using Base::get_node;
  using Base::get_node_allocator;

  template<typename... Args>
  Node*
  create_node(Args&&... args)
  {
    auto p      = this->get_node();
    auto& alloc = this->get_node_allocator();
    try {
      Node_alloc_traits::construct(alloc, p->valptr(), std::forward<Args>(args)...);
    } catch(const std::exception& e) {
      this->put_node(p);
      throw e;
    }
    return p;
  }

 public:

  list() noexcept(std::is_nothrow_default_constructible<Node_alloc_type>::value)
      : Base() { }

  list(const allocator_type& a) noexcept
      : Base(Node_alloc_type(a)) { }

  ~list() = default;

  iterator
  begin() noexcept
  { return iterator(static_cast<Node*>(this->m_impl.m_node.m_next)); }

  iterator
  end() noexcept
  { return iterator(reinterpret_cast<Node*>(&this->m_impl.m_node)); }

  const_iterator
  begin() const noexcept
  { return const_iterator(static_cast<Node*>(this->m_impl.m_node.m_next)); }

  const_iterator
  end() const noexcept
  { return const_iterator(
      reinterpret_cast<Node*>(
          const_cast< detail::list_node<std::size_t>* >(&this->m_impl.m_node))); }

  const_iterator
  cbegin() const noexcept
  { return begin(); }

  const_iterator
  cend() const noexcept
  { return end(); }

  reverse_iterator
  rbegin() noexcept
  { return reverse_iterator(end()); }

  reverse_iterator
  rend() noexcept
  { return reverse_iterator(begin()); }

  const_reverse_iterator
  crbegin() const noexcept
  { return const_reverse_iterator(end()); }

  const_reverse_iterator
  crend() const noexcept
  { return const_reverse_iterator(begin()); }

  bool
  empty() const noexcept
  { return this->m_impl.m_node.m_next == this->m_impl.m_node; }

  size_type
  size() const noexcept
  { return this->node_count(); }

  void
  push_front(const value_type& x)
  { this->insert(begin(), x); }

  void
  push_back(const value_type& x)
  { this->insert(end(), x); }

  iterator
  insert(const iterator position, const value_type& x)
  {
    Node* tmp = create_node(x);
    tmp->hook(position.m_node);
    this->inc_size(1);
    return iterator(tmp);
  }

  iterator
  insert(const iterator position, value_type&& x)
  {
    return emplace(position, std::move(x));
  }

  template<typename... Args>
  iterator
  emplace(const iterator position, Args&&... args)
  {
    Node* tmp = create_node(std::forward<Args>(args)...);
    tmp->hook(position.m_const_cast().m_node);
    this->inc_size(1);
    return iterator(tmp);
  }

  template<typename... Args>
  iterator
  emplace_front(Args&&... args)
  { return emplace(begin(), std::forward<Args>(args)...); }

  template<typename... Args>
  iterator
  emplace_back(Args&&... args)
  { return emplace(end(), std::forward<Args>(args)...); }

};

}      // namespace nzl
#endif // LIST_HPP_HEADER_GUARDS

test-list.cpp

// -*- coding:utf-8; mode:c++; mode:auto-fill; fill-column:80; -*-

/// @file list.hpp
/// @brief A minimal test of nzl::list --- it is meant for educational purposes.
/// @author J. Arrieta <[email protected]>
/// @copyright Copyright (c) 2016 Nabla Zero Labs. All rights reserved.
/// @license This software is released under the MIT License.
///
/// The MIT License (MIT)
/// Copyright (c) 2016 Nabla Zero Labs
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to
/// deal in the Software without restriction, including without limitation the
/// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
/// sell copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in
/// all copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
/// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
/// IN THE SOFTWARE.

// C++ Standard Library
#include <iostream>

// nzl library
#include "list.hpp"

template<typename Container>
void
show(const Container& c)
{ for (auto && item : c) std::cout << (item) << "\n"; }

int
main()
{
  nzl::list<double> l;

  l.emplace_front(10);
  l.emplace_front(20);
  l.emplace_front(30);
  l.emplace_back(99);
  l.emplace_back(0);
  l.emplace_front(789);

  std::cout << "---------- the list ----------\n";
  show(l);

  std::cout << "---------- end list  ----------\n"
            << "---------- the reversed list ----------\n";

  for (auto it = l.crbegin(); it != l.crend(); ++it) {
    std::cout << *it << std::endl;
  }

  std::cout << "---------- end reversed list  ----------\n"
            << "size using method... " << l.size() << "\n"
            << "size using algos.... " << std::distance(l.begin(), l.end()) << "\n";
}

Compile and run the example:

$ g++ test-list.cpp -std=c++14 -Wall -Wextra
$ ./a.out 
---------- the list ----------
789
30
20
10
99
0
---------- end list  ----------
---------- the reversed list ----------
0
99
10
20
30
789
---------- end reversed list  ----------
size using method... 6
size using algos.... 6