Solution of circular buffer from C++ exam: https://github.com/CPP-KT/circular-buffer-task

circular_buffer.h

#pragma once
#include <cassert>
#include <cstdlib>
#include <iterator>
#include <utility>
#include <memory>
#include <algorithm>


template <typename T>
class circular_buffer { // Should be class according to CppCoreGuidelines
private: // I've written in some HTs why I prefer to declare members first
  T* data_ = nullptr;   // (data_ == nullptr) <=> (capacity_ == 0)

  size_t capacity_ = 0; // capacity is always a pow of to in order to make
                        // computing modular arithmetic more efficient
                        // without making development more difficult.
                        // For example, we don't now have to
                        // call `%` for every step while traversal.
                        // The only issue is that at reallocate we might need
                        // to choose a bit too big buffer, but if we want,
                        // it's very easy to switch to using `%`.
                        // The other alternative is to check that we don't overflow
                        // two capacities and use branching (that would be predicted efficiently)

  size_t head_ = 0;     // Denotes the index from `data_` where the first elements are stored
  size_t size_ = 0;     // capacity

  template<typename ItT>
  class circular_buffer_iterator {
  public:
    static constexpr bool MUTABLE = !std::is_const_v<ItT>;

  private:
    using MutableT = std::remove_const_t<ItT>;
    using SiblingT = std::conditional_t<MUTABLE, std::add_const_t<ItT>, MutableT>;
    using Sibling = circular_buffer_iterator<SiblingT>;

    using Buff = circular_buffer<MutableT>;
    using BuffRef = std::conditional_t<MUTABLE, Buff&, const Buff&>;
    using BuffPtr = std::conditional_t<MUTABLE, Buff*, const Buff*>;
    using Ref = ItT&;

    BuffPtr buffer = nullptr;
    size_t index = 0; // Index that would be given to `operator []`

    friend class circular_buffer<ItT>;
    friend class circular_buffer<SiblingT>;
    friend class circular_buffer_iterator<SiblingT>;

  private:
    circular_buffer_iterator(BuffRef buffer, size_t index) : buffer(&buffer), index(index) {}

  public:

    void swap(circular_buffer_iterator& other) {
      std::swap(buffer, other.buffer);
      std::swap(index, other.index);
    }

    /* Can always copy construct from same iterator type */
    circular_buffer_iterator(circular_buffer_iterator const &other)
        : buffer(other.buffer), index(other.index) {}

    /* Moreover, from mutable we can construct immutable (don't forget about always having 1 overload) */

    template<bool TmpMut = MUTABLE>
    /* implicit */ circular_buffer_iterator(std::enable_if_t<!TmpMut, const Sibling&> mutable_iter)
        : buffer(const_cast<BuffPtr>(mutable_iter.buffer)), index(mutable_iter.index) {}

    circular_buffer_iterator& operator=(circular_buffer_iterator const &other) {
      if (this != &other) {
        circular_buffer_iterator(other).swap(*this);
      }
      return *this;
    }

    circular_buffer_iterator() = default;


    Ref operator*() noexcept {
      return (*buffer)[index];
    }

    circular_buffer_iterator& operator++()
    {
      index++;
      return *this;
    }

    circular_buffer_iterator operator++(int)
    {
      auto old = *this;
      operator++();
      return old;
    }

    circular_buffer_iterator& operator--()
    {
      index--;
      return *this;
    }

    circular_buffer_iterator operator--(int)
    {
      auto old = *this;
      operator--();
      return old;
    }

    friend bool operator==(const circular_buffer_iterator& lhs,
                           const circular_buffer_iterator& rhs) {
      return lhs.buffer == rhs.buffer && lhs.index == rhs.index;
    }
    friend bool operator!=(const circular_buffer_iterator& lhs,
                           const circular_buffer_iterator& rhs) {
      return !(rhs == lhs);
    }
    friend bool operator<(const circular_buffer_iterator& lhs,
                          const circular_buffer_iterator& rhs) {
      return lhs.index < rhs.index;
    }
    friend bool operator>(const circular_buffer_iterator& lhs,
                          const circular_buffer_iterator& rhs) {
      return rhs < lhs;
    }
    friend bool operator<=(const circular_buffer_iterator& lhs,
                           const circular_buffer_iterator& rhs) {
      return !(rhs < lhs);
    }
    friend bool operator>=(const circular_buffer_iterator& lhs,
                           const circular_buffer_iterator& rhs) {
      return !(lhs < rhs);
    }

    circular_buffer_iterator& operator+= (size_t amount) { // Only add/subtract positive values
      index += amount;
      return *this;
    }
    circular_buffer_iterator& operator-= (size_t amount) {
      index -= amount;
      return *this;
    }
    friend circular_buffer_iterator operator+ (circular_buffer_iterator it, size_t amount) {
      return it += amount;
    }
    friend circular_buffer_iterator operator- (circular_buffer_iterator it, size_t amount) {
      return it -= amount;
    }

    friend circular_buffer_iterator operator+ (size_t amount,
                                              circular_buffer_iterator it) {
      return it += amount;
    }

    friend size_t operator- (circular_buffer_iterator left,
                            circular_buffer_iterator right) {
      return left.index - right.index;
    }

    Ref operator[](size_t shift) {
      return *((*this) + shift);
    }
  };


public:
  using iterator = circular_buffer_iterator<T>;
  using const_iterator = circular_buffer_iterator<const T>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  friend class circular_buffer_iterator<T>;
  friend class circular_buffer_iterator<const T>;


public:
  circular_buffer() noexcept = default;                  // O(1)
  circular_buffer(circular_buffer const& other)          // O(n), strong
      : data_(other.dump_buffer(other.capacity())), capacity_(other.capacity()), head_(0), size_(other.size()) {
    // If `other.dump_buffer()`, memory is freed and destructors are called
    // But `this` becomes invalid object which is an acceptable behaviour
  }
  ~circular_buffer() {                         // O(n)
    destruct_deallocate();
  }
  circular_buffer& operator=(circular_buffer const& other) {  // O(n), strong
    if (this != &other) {
      circular_buffer(other).swap(*this);
    }
    return *this;
  }

  size_t size() const noexcept { return size_; }                     // O(1)
  T& operator[](size_t index) noexcept { return const_cast<T&>(const_cast<const circular_buffer&>(*this)[index]); } // O(1)
  T const& operator[](size_t index) const noexcept { return data_[modular_index(head_ + index)]; } // O(1)

  bool empty() const noexcept { return size() == 0; } // O(1), nothrow
  void clear() noexcept { // O(n), nothrow
    destruct_all();
    size_ = 0; // head_ can be anywhere in buffer
  }

  void push_back(T const& val) { // O(1)*, strong
    put_at_new_position(true, val);
  }
  void pop_back() noexcept {      // O(1)
    back().~T();
    size_--;
  }
  T& back() noexcept { return (*this)[size() - 1]; }             // O(1)
  T const& back() const noexcept { return (*this)[size() - 1]; } // O(1)

  void push_front(T const& val) {  // O(1)*, strong
    put_at_new_position(false, val);
  }
  void pop_front() noexcept {       // O(1)
    front().~T();
    head_ = modular_index(head_ + 1);
    size_--;
  }
  T& front() noexcept { return (*this)[0]; }             // O(1)
  T const& front() const noexcept { return (*this)[0]; } // O(1)

  void reserve(size_t desired_capacity) { // O(n), strong
    if (capacity() >= desired_capacity) {
      return;
    }
    size_t new_capacity = calculate_new_capacity(desired_capacity);
    T* new_buffer = dump_buffer(new_capacity);

    destruct_deallocate();
    data_ = new_buffer;
    capacity_ = new_capacity;
    head_ = 0;
    // size_ remains unchanged
  }
  size_t capacity() const noexcept { return capacity_; }      // O(1)

  iterator begin() noexcept {             // O(1)
    return iterator (*this, 0);
  }
  const_iterator begin() const noexcept {
    return const_iterator (*this, 0);
  } // O(1)
  iterator end() noexcept {
    return iterator (*this, size());
  }               // O(1)
  const_iterator end() const noexcept {
    return const_iterator (*this, size());
  }   // O(1)

  reverse_iterator rbegin() noexcept { // O(1)
    reverse_iterator(*this, size());
  }
  const_reverse_iterator rbegin() const noexcept { // O(1)
    const_reverse_iterator(*this, size());
  }
  reverse_iterator rend() noexcept { // O(1)
    reverse_iterator(*this, size_t(-1));
  }
  const_reverse_iterator rend() const noexcept  { // O(1)
    const_reverse_iterator(*this, size_t(-1));
  }

  iterator insert(const_iterator pos, T const& val) {          // O(n), basic
      if (end() - pos < pos - begin()) {
        size_t swaps_needed = end() - pos;
        push_back(val);
        size_t new_element_index = size() - 1;
        for (; swaps_needed != 0; --swaps_needed, --new_element_index) {
          std::swap(begin()[new_element_index], begin()[new_element_index - 1]);
        }
        return begin() + new_element_index;
      } else {
        size_t swaps_needed = pos - begin();
        push_front(val);
        size_t new_element_index = 0;
        for (; swaps_needed != 0; --swaps_needed, ++new_element_index) {
          std::swap(begin()[new_element_index], begin()[new_element_index + 1]);
        }
        return begin() + new_element_index;
      }
  }
  iterator erase(const_iterator pos)  { // O(n), basic
    return erase(pos, pos + 1);
  }

  iterator erase(const_iterator first, const_iterator last) { // O(n), basic
    const_iterator beg = begin();
    size_t index_first = first - beg;
    size_t index_last = last - beg;
    size_t removed_elements = index_last - index_first;


    if (index_first > size() - index_last) {
      for (size_t i = index_last; i < size(); ++i) {
        std::swap(begin()[i], begin()[i - removed_elements]);
      }
      for (size_t i = 0; i < removed_elements; ++i) {
        pop_back();
      }
    } else {
      for (size_t i = index_first; i > 0; --i) {
        std::swap(begin()[i - 1], begin()[i + removed_elements - 1]);
      }
      for (size_t i = 0; i < removed_elements; ++i) {
        pop_front();
      }
    }


    return begin() + index_first;
  }

  void swap(circular_buffer& other) noexcept { // O(1)
    std::swap(data_, other.data_);
    std::swap(capacity_, other.capacity_);
    std::swap(size_, other.size_);
    std::swap(head_, other.head_);
  }


private:
  size_t modular_index(size_t original_index) const {
    assert(capacity() != 0); // Don't have valid indices for zero capacity

    size_t msk = capacity() - 1; // All ones at positions [0: log_2(capacity))

    return original_index & msk;
  }

  size_t prev_buffer_position(size_t position) {
    return position == 0 ? capacity() - 1 : position - 1;
  }

  size_t calculate_new_capacity(size_t at_least_cap) const { // We've already decided that we allocate
    if (at_least_cap == 0) return 0;

    size_t res = std::max(capacity(), size_t(2));
    while (res < at_least_cap) { // No more than 64 bitwise ops for ×64, anyway, it's O(log(at_least_cap))
      res *= 2;
    }
    return res;
  }

  static T* allocate(size_t new_capacity) {
    return new_capacity == 0 ? nullptr : static_cast<T*>(operator new(new_capacity * sizeof(T)));
  }

  T* dump_buffer(size_t new_capacity) const {
    auto* new_buff = allocate(new_capacity);

    size_t i = 0;
    try {
      for (; i < size(); ++i) {
        new (new_buff + i) T((*this)[i]);
      }
    } catch (...) {
      // Constructed [0: i)
      std::destroy_n(new_buff, i);
      operator delete(new_buff);
      throw;
    }

    return new_buff;
  }


  // Either to element after `back` of the one before `front`
  void put_at_new_position(bool to_end, const T& element) {
    if (size() + 1 > capacity()) {
      // Reallocation needed
      auto new_cap = calculate_new_capacity(size() + 1);
      auto buff = dump_buffer(new_cap); // If couldn't, no problems: we haven't modified `this`
      size_t target_position = to_end ? size() : new_cap - 1;
      try {
        new(buff + target_position) T(element);
      } catch(...) {
        std::destroy_n(buff, size());
        operator delete(buff);
        throw;
      }
      destruct_deallocate();

      data_ = buff;
      if (!to_end) {
        head_ = target_position;
      }
      capacity_ = new_cap;
    } else {
      size_t buffer_position = to_end ? modular_index(head_ + size()) : prev_buffer_position(head_);
      new (&data_[buffer_position]) T(element);
      if (!to_end) {
        head_--;
      }
    }
    size_++;
  }

  void destruct_range(size_t start, size_t end) {
    for (size_t i = start; i < end; ++i) {
      (*this)[i].~T();
    }
  }

  void destruct_all() { destruct_range(0, size()); }

  void destruct_deallocate() {
    destruct_all();
    operator delete (data_);
  }
};