cpp-intrusive-list/intrusive_list.hpp

//
//  intrusive_iterator.h
//  utilities
//
//  Created by Sam Jaffe on 9/26/14.
//  Copyright (c) 2014 Sam Jaffe. All rights reserved.
//

#pragma once

#include <iterator>
#include <limits>
#include <cstddef>

template <typename T> class intrusive_node;
template <typename T> class intrusive_list;
template <typename T> class intrusive_iterator;
template <typename T> class const_intrusive_iterator;

template <typename T>
class intrusive_list {
public:
  typedef T value_type;
  typedef intrusive_node<value_type> node_type;
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef intrusive_iterator<node_type> iterator;
  typedef const_intrusive_iterator<node_type> const_iterator;
  typedef typename std::reverse_iterator<iterator> reverse_iterator;
  typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;
public:
  constexpr intrusive_list( node_type T::*node );
  intrusive_list( const intrusive_list& ) = delete;
  intrusive_list( intrusive_list&& other ) = default;
  intrusive_list( std::initializer_list<pointer> ilist, node_type T::*node );
  ~intrusive_list();
  
  intrusive_list& operator=( const intrusive_list& ) = delete;
  intrusive_list& operator=( intrusive_list&& other );
  intrusive_list& operator=( std::initializer_list<pointer> ilist );
  
  void assign( std::initializer_list<pointer> ilist );
  
  inline pointer front();
  inline const_pointer front() const;
  
  inline pointer back();
  inline const_pointer back() const;
  
  inline iterator begin() noexcept;
  inline const_iterator begin() const noexcept;
  inline const_iterator cbegin() const noexcept;
  
  inline iterator end() noexcept;
  inline const_iterator end() const noexcept;
  inline const_iterator cend() const noexcept;
  
  inline reverse_iterator rbegin();
  inline const_reverse_iterator rbegin() const noexcept;
  inline const_reverse_iterator crbegin() const noexcept;
  
  inline reverse_iterator rend() noexcept;
  inline const_reverse_iterator rend() const noexcept;
  inline const_reverse_iterator crend() const noexcept;
  
  inline bool empty() const noexcept;
  inline size_type size() const noexcept;
  inline size_type max_size() const noexcept;
  
  void clear() noexcept;
  
  iterator insert(const_iterator pos, pointer value);
  iterator transfer( const_iterator pos, pointer value );
  iterator insert(const_iterator pos, std::initializer_list<pointer> ilist);
  
  iterator erase(iterator pos);
  iterator erase(iterator first, iterator last);
  
  inline void push_back(pointer value);
  inline void pop_back();
  inline void push_front(pointer value);
  inline void pop_front();
  
  void remove( pointer value );
  template< class UnaryPredicate >
  void remove_if( UnaryPredicate pred );
private:
  void insert_impl( const_iterator pos, node_type * n );
  inline void link(node_type* lhs, node_type* rhs);
  inline void unlink(node_type* node);
  
  node_type T::*node_;
  node_type end_{ nullptr }; // secretly const
  node_type *tail_{ &end_ };
  node_type *head_{ &end_ };
  size_type size_{ 0 };
};

#include "intrusive_iterator.tpp"
#include "intrusive_node.tpp"
#include "intrusive_list.tpp"