7
\$\begingroup\$

I attempt to write a STL-like vector, mostly to figure out how it works. I wonder which parts look weird or what I made stupid. Any kind of comment is appreciated:

alloc.hpp

#pragma once

#include <limits>
#include <memory>

namespace p1v0t {
template <class T>
class allocator {
public:
  using value_type = T;

  template <class U>
  struct rebind {
    typedef allocator<U> other;
  };

  allocator() noexcept = default;

  template <class U>
  allocator(allocator<U> const &) noexcept {}

  // Use pointer if pointer is not a value_type*
  [[nodiscard]] value_type *allocate(std::size_t n) {
    return static_cast<value_type *>(::operator new(n * sizeof(value_type)));
  }

  // Use pointer if pointer is not a value_type*
  void deallocate(value_type *p, std::size_t) noexcept { ::operator delete(p); }

  using propagate_on_container_copy_assignment = std::false_type;
  using propagate_on_container_move_assignment = std::false_type;
  using propagate_on_container_swap = std::false_type;
  using is_always_equal = std::is_empty<allocator>;
};

template <class T, class U>
bool operator==(allocator<T> const &, allocator<U> const &) noexcept {
  return true;
}

template <class T, class U>
bool operator!=(allocator<T> const &x, allocator<U> const &y) noexcept {
  return !(x == y);
}
} // namespace p1v0t

vector.hpp

#pragma once

#include "alloc.hpp"
#include <algorithm>
#include <initializer_list>
#include <limits>

namespace p1v0t {
template <typename T, class Allocator = allocator<T>>
class vector {

public:
  using allocator_type = Allocator;
  using value_type = T;

  using reference = value_type &;
  using const_reference = const value_type &;

  using pointer = typename std::allocator_traits<Allocator>::pointer;
  using const_pointer =
      typename std::allocator_traits<Allocator>::const_pointer;

  using iterator = value_type *;
  using const_iterator = const value_type *;

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

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

  allocator_type m_allocator;
  T *m_data = nullptr;

  size_type m_capacity = 0;
  size_type m_size = 0;

  constexpr vector() noexcept(noexcept(Allocator()));
  explicit vector(size_type n_);
  constexpr vector(std::initializer_list<T> il_);
  constexpr vector(size_t elm_, const value_type &val_);

  template <class InputIt>
  constexpr vector(InputIt first, InputIt last);

  constexpr vector(const vector<T, Allocator> &other_);
  constexpr vector &operator=(const vector &other_);
  constexpr vector &operator=(std::initializer_list<value_type> il_);

  constexpr vector(vector &&other_) noexcept(
      std::is_nothrow_move_constructible<allocator_type>::value);
  constexpr vector &operator=(vector &&other_) noexcept(
      allocator_type::propagate_on_container_move_assignment::value ||
      allocator_type::is_always_equal::value);

  virtual ~vector() noexcept;

  constexpr void assign(size_type, const T &);
  template <class InputIt>
  constexpr void assign(InputIt, InputIt);
  constexpr void assign(std::initializer_list<T>);

  constexpr allocator_type get_allocator() const noexcept;

  constexpr reference at(size_type);
  constexpr const_reference at(size_type) const;

  constexpr reference operator[](size_type);
  constexpr const_reference operator[](size_type) const;

  constexpr reference front();
  constexpr const_reference front() const;

  constexpr reference back();
  constexpr const_reference back() const;

  constexpr pointer data() noexcept;
  constexpr const_pointer data() const noexcept;

  constexpr iterator begin() noexcept;
  constexpr const_iterator begin() const noexcept;
  constexpr const_iterator cbegin() const noexcept;
  constexpr reverse_iterator rbegin() noexcept;
  constexpr const_reverse_iterator rbegin() const noexcept;
  constexpr const_reverse_iterator crbegin() const noexcept;

  constexpr iterator end() noexcept;
  constexpr const_iterator end() const noexcept;
  constexpr const_iterator cend() const noexcept;
  constexpr reverse_iterator rend() noexcept;
  constexpr const_reverse_iterator rend() const noexcept;
  constexpr const_reverse_iterator crend() const noexcept;

  [[nodiscard]] constexpr bool empty() const noexcept;
  constexpr difference_type max_size() const noexcept;
  constexpr size_type capacity() const noexcept;
  constexpr size_type size() const noexcept;
  constexpr void reserve(size_type new_cap_);
  constexpr void shrink_to_fit();
  constexpr void clear() noexcept;

  constexpr iterator insert(const_iterator, const T &);
  constexpr iterator insert(const_iterator, T &&);
  constexpr iterator insert(const_iterator, size_type, const T &);
  template <class InputIt>
  constexpr iterator insert(const_iterator, InputIt, InputIt);
  constexpr iterator insert(const_iterator, std::initializer_list<T>);

  constexpr void push_back(const T &);
  constexpr void push_back(T &&);

  template <class... Args>
  constexpr reference emplace_back(Args &&...);

  template <class... Args>
  constexpr iterator emplace(const_iterator pos_, Args &&...);

  constexpr iterator erase(const_iterator pos_);
  constexpr iterator erase(const_iterator first_, const_iterator last_);
  constexpr void pop_back();
  constexpr void resize(size_type count_);
  constexpr void resize(size_type count_, const value_type &value_);
  constexpr void swap(vector &other_) noexcept;

private:
  const uint8_t m_growing_rate = 2;
}; // end class vector

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector() noexcept(noexcept(Allocator())) {
  m_size = 0;
  reserve(1);
}

template <typename T, class Allocator>
vector<T, Allocator>::vector(size_type n_) {
  reserve(n_ * m_growing_rate);
  m_size = n_;
}

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector(size_t n_, const value_type &val_) {
  m_size = m_capacity = n_;
  m_data = m_allocator.allocate(m_capacity);

  std::fill(begin(), end(), val_);
}

template <typename T, class Allocator>
template <class InputIt>
constexpr vector<T, Allocator>::vector(InputIt first_, InputIt last_) {
  assign(first_, last_);
}

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector(std::initializer_list<T> lst_) {
  reserve(lst_.size() * m_growing_rate);

  std::move(lst_.begin(), lst_.end(), this->begin());
  m_size = lst_.size();
}

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector(const vector<T, Allocator> &other_) {
  reserve(other_.size() * m_growing_rate);
  std::move(other_.begin(), other_.end(), this->begin());
  m_size = other_.size();
}

template <typename T, class Allocator>
constexpr vector<T, Allocator> &vector<T, Allocator>::
operator=(const vector &other_) {
  assign(other_.begin(), other_.end());

  return *this;
}

template <typename T, class Allocator>
constexpr vector<T, Allocator> &vector<T, Allocator>::
operator=(std::initializer_list<value_type> il_) {
  m_size = il_.size();

  m_capacity = m_size * m_growing_rate;
  m_data = m_allocator.allocate(m_capacity);

  std::move(il_.begin(), il_.end(), this->begin());

  return *this;
}

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector(vector &&other_) noexcept(
    std::is_nothrow_move_constructible<allocator_type>::value) {
  m_data = std::move(other_.m_data);
  m_size = other_.m_size;
  m_capacity = other_.m_capacity;

  other_.m_data = nullptr;
  other_.m_capacity = 0;
  other_.m_size = 0;
}

template <typename T, class Allocator>
constexpr vector<T, Allocator> &vector<T, Allocator>::
operator=(vector &&other_) noexcept(
    allocator_type::propagate_on_container_move_assignment::value ||
    allocator_type::is_always_equal::value) {

  m_data = std::move(other_.m_data);
  m_size = other_.m_size;
  m_capacity = other_.m_capacity;

  other_.m_data = nullptr;
  other_.m_capacity = 0;
  other_.m_size = 0;

  return *this;
}

template <typename T, class Allocator>
vector<T, Allocator>::~vector() noexcept {
  m_allocator.deallocate(m_data, m_capacity);
  m_size = 0;
  m_capacity = 0;
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::assign(size_type count_, const T &value_) {

  reserve(count_ * m_growing_rate);
  m_size = count_;
  std::fill(begin(), end(), value_);
}

template <typename T, class Allocator>
template <class InputIt>
constexpr void vector<T, Allocator>::assign(InputIt first_, InputIt last_) {

  size_type length_of_interval =
      static_cast<size_type>(std::distance(first_, last_));

  reserve((size() + length_of_interval) * m_growing_rate);

  std::move(first_, last_, begin());
  m_size += static_cast<size_type>(std::distance(first_, last_) * 2);
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::assign(std::initializer_list<T> il_) {
  reserve(il_.size() * m_growing_rate);
  std::move(il_.begin(), il_.end(), begin());
  m_size = il_.size();
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::allocator_type
vector<T, Allocator>::get_allocator() const noexcept {
  return m_allocator;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reference
vector<T, Allocator>::at(size_type index_) {
  if (index_ >= size()) {
    throw std::out_of_range("Billions of Bilious Blue Blistering Barnacles! "
                            "You attempted to access out of range");
  }
  return m_data[index_];
}

template <typename T, class Allocator>
typename vector<T, Allocator>::const_reference constexpr vector<
    T, Allocator>::at(size_type index_) const {
  if (index_ >= size()) {
    throw std::out_of_range("Billions of Bilious Blue Blistering Barnacles! "
                            "Attemp to access out of range");
  }
  return m_data[index_];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reference vector<T, Allocator>::
operator[](size_type pos_) {
  return m_data[pos_];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reference vector<T, Allocator>::
operator[](size_type pos_) const {
  return m_data[pos_];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reference
vector<T, Allocator>::front() {
  return m_data[0];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reference
vector<T, Allocator>::front() const {
  return m_data[0];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reference
vector<T, Allocator>::back() {
  return m_data[m_size - 1];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reference
vector<T, Allocator>::back() const {
  return m_data[m_size - 1];
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::pointer
vector<T, Allocator>::data() noexcept {
  return m_data;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_pointer
vector<T, Allocator>::data() const noexcept {
  return m_data;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::begin() noexcept {
  return (m_data + 0);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_iterator
vector<T, Allocator>::begin() const noexcept {
  return (m_data + 0);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_iterator
vector<T, Allocator>::cbegin() const noexcept {
  return (m_data + 0);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reverse_iterator
vector<T, Allocator>::rbegin() noexcept {
  return reverse_iterator(end());
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reverse_iterator
vector<T, Allocator>::rbegin() const noexcept {
  return const_reverse_iterator(end());
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reverse_iterator
vector<T, Allocator>::crbegin() const noexcept {
  return static_cast<const_reverse_iterator>(end());
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::end() noexcept {
  return (m_data + m_size);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_iterator
vector<T, Allocator>::end() const noexcept {
  return (m_data + m_size);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_iterator
vector<T, Allocator>::cend() const noexcept {
  return (m_data + m_size);
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::reverse_iterator
vector<T, Allocator>::rend() noexcept {
  return reverse_iterator(begin());
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reverse_iterator
vector<T, Allocator>::rend() const noexcept {
  return const_reverse_iterator(begin());
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::const_reverse_iterator
vector<T, Allocator>::crend() const noexcept {
  return const_reverse_iterator(cbegin());
}

template <typename T, class Allocator>
[[nodiscard]] constexpr bool vector<T, Allocator>::empty() const noexcept {
  return size() == 0;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::difference_type
vector<T, Allocator>::max_size() const noexcept {
  return std::numeric_limits<difference_type>::max();
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::size_type
vector<T, Allocator>::capacity() const noexcept {
  return m_capacity;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::size_type
vector<T, Allocator>::size() const noexcept {
  return m_size;
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::shrink_to_fit() {
  m_capacity = m_size;
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::reserve(size_type new_cap_) {
  if (new_cap_ > m_capacity) {
    if (new_cap_ > max_size())
      throw std::length_error("Megacycle Pyromaniac! Length ERROR!!!");

    if (empty()) {
      m_data = m_allocator.allocate(new_cap_);
      m_capacity = new_cap_;
    } else {
      T *tmp = m_allocator.allocate(new_cap_);
      std::move(begin(), end(), tmp);
      m_allocator.deallocate(m_data, m_capacity);

      m_data = std::move(tmp);
      m_capacity = new_cap_;
    }
  }
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::clear() noexcept {
  m_size = 0;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::insert(const_iterator pos_, const T &val_) {
  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = val_;

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  if (empty()) {
    *begin() = val_;
    ++m_size;

    return begin();
  }

  return ret;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::insert(const_iterator pos_, T &&val_) {
  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = std::move(val_);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  if (empty()) {
    *begin() = std::move(val_);
    ++m_size;

    return begin();
  }

  return ret;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::insert(const_iterator pos_, size_type count_,
                             const T &val_) {

  iterator ret = const_cast<iterator>(pos_);

  if (empty() && capacity() < count_) {
    reserve(count_ * m_growing_rate);
    m_size = count_;

    std::fill(begin(), end(), val_);
    return begin();
  } else {
    m_size += count_;

    std::move_backward(ret, end() - count_, end());
    std::fill(ret, ret + count_, val_);

    if (size() * 2 >= capacity())
      reserve(capacity() * m_growing_rate);

    return ret;
  }
}

template <typename T, class Allocator>
template <class InputIt>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::insert(const_iterator pos_, InputIt first_,
                             InputIt last_) {

  iterator ret = const_cast<iterator>(pos_);

  size_type diff = static_cast<size_type>(std::distance(first_, last_));

  m_size += diff;

  std::move_backward(ret, end() - diff, end());
  std::move(first_, last_, ret);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::insert(const_iterator pos_,
                             std::initializer_list<T> lst_) {

  iterator ret = const_cast<iterator>(pos_);

  m_size += lst_.size();

  std::move_backward(ret, end() - lst_.size(), end());
  std::move(lst_.begin(), lst_.end(), ret);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::push_back(const T &val_) {

  m_data[m_size++] = val_;

  if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::push_back(T &&val_) {
  m_data[m_size++] = std::move(val_);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);
}

template <typename T, class Allocator>
template <class... Args>
constexpr typename vector<T, Allocator>::reference
vector<T, Allocator>::emplace_back(Args &&... args_) {
  ++m_size;

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  *(end() - 1) = std::move(T(std::forward<Args>(args_)...));

  return *(end() - 1);
}

template <typename T, class Allocator>
template <class... Args>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::emplace(const_iterator pos_, Args &&... args_) {

  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = std::move(std::forward<Args>(args_)...);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::erase(const_iterator pos_) {
  if (pos_ == begin()) {
    --m_size;
    return ++m_data;
  }

  iterator ret = const_cast<iterator>(pos_);
  std::move(ret + 1, end(), ret);
  --m_size;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);

  return ret;
}
template <typename T, class Allocator>
constexpr typename vector<T, Allocator>::iterator
vector<T, Allocator>::erase(const_iterator first_, const_iterator last_) {

  difference_type diff = last_ - first_;
  iterator ret = const_cast<iterator>(first_);

  std::move(last_, cend(), ret);

  m_size -= static_cast<size_type>(diff);

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);

  return ret;
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::pop_back() {
  if (!empty()) {
    --m_size;
  }
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::resize(size_type count_) {
  m_size = count_;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::resize(size_type count_,
                                            const value_type &value_) {
  size_type old_size = m_size;
  m_size = count_;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);

  if (old_size > count_) {
    fill(begin() + count_, begin() + old_size, value_);
  } else {
    fill(begin() + old_size, begin() + count_, value_);
  }
}

template <typename T, class Allocator>
constexpr void vector<T, Allocator>::swap(vector &other_) noexcept {
  size_type tmp_size = other_.size();
  size_type tmp_capacity = other_.capacity();
  auto tmp_data = other_.data();

  other_.m_size = m_size;
  other_.m_capacity = m_capacity;
  other_.m_data = m_data;

  m_size = tmp_size;
  m_capacity = tmp_capacity;
  m_data = tmp_data;
}

template <typename T, class Allocator>
constexpr bool operator==(const p1v0t::vector<T, Allocator> &lhs_,
                          const p1v0t::vector<T, Allocator> &rhs_) {
  return (lhs_.size() == rhs_.size() and
          std::equal(lhs_.begin(), lhs_.end(), rhs_.begin()));
}

template <typename T, class Allocator>
constexpr bool operator!=(const p1v0t::vector<T, Allocator> &lhs_,
                          const p1v0t::vector<T, Allocator> &rhs_) {
  return !(lhs_ == rhs_);
}

template <typename T, class Allocator>
constexpr bool operator<(const p1v0t::vector<T, Allocator> &lhs_,
                         const p1v0t::vector<T, Allocator> &rhs_) {
  return std::lexicographical_compare(lhs_.begin(), lhs_.end(), rhs_.begin(),
                                      rhs_.end());
}

template <typename T, class Allocator>
constexpr bool operator>=(const p1v0t::vector<T, Allocator> &lhs_,
                          const p1v0t::vector<T, Allocator> &rhs_) {
  return !(lhs_ < rhs_);
}

template <typename T, class Allocator>
constexpr bool operator>(const p1v0t::vector<T, Allocator> &lhs_,
                         const p1v0t::vector<T, Allocator> &rhs_) {
  return rhs_ < lhs_;
}

template <typename T, class Allocator>
constexpr bool operator<=(const p1v0t::vector<T, Allocator> &lhs_,
                          const p1v0t::vector<T, Allocator> &rhs_) {
  return !(rhs_ < lhs_);
}

template <typename T, class Allocator>
constexpr void
swap(vector<T, Allocator> &lhs_,
     vector<T, Allocator> &rhs_) noexcept(noexcept(lhs_.swap(rhs_))) {
  lhs_.swap(rhs_);
}

template <typename T, class Allocator, class U>
constexpr void erase(p1v0t::vector<T, Allocator> &container_, const U &value_) {

  container_.erase(std::remove(container_.begin(), container_.end(), value_),
                   container_.end());
}

template <typename T, class Allocator, class Pred>
constexpr void erase_if(p1v0t::vector<T, Allocator> &container_,
                        const Pred predicate_) {
  container_.erase(
      std::remove_if(container_.begin(), container_.end(), predicate_),
      container_.end());
}

template <class Allocator>
class vector<bool, Allocator> {
public:
  using allocator_type = Allocator;
  using value_type = bool;

  using reference = value_type &;
  using const_reference = const value_type &;

  using pointer = typename std::allocator_traits<Allocator>::pointer;
  using const_pointer =
      typename std::allocator_traits<Allocator>::const_pointer;

  using iterator = value_type *;
  using const_iterator = const value_type *;

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

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

  allocator_type m_allocator;
  value_type *m_data = nullptr;

  size_type m_capacity = 0;
  size_type m_size = 0;

  explicit constexpr vector();
  explicit constexpr vector(size_type count_);
  constexpr vector(size_type n_, const bool &val_);
  constexpr vector(std::initializer_list<bool>);

  template <class InputIt>
  constexpr vector(InputIt first_, InputIt last_);

  constexpr vector(const vector<bool, Allocator> &other_);
  constexpr vector<bool, Allocator> &
  operator=(const vector<bool, Allocator> &other_);
  constexpr vector &operator=(std::initializer_list<bool>);

  constexpr vector(vector &&);
  constexpr vector<bool, Allocator> &operator=(vector<bool, Allocator> &&);

  virtual ~vector() noexcept;

  constexpr void assign(size_type, const bool &);
  template <class InputIt>
  constexpr void assign(InputIt, InputIt);
  constexpr void assign(std::initializer_list<bool>);

  constexpr allocator_type get_allocator() const noexcept;

  constexpr reference at(size_type n_);
  constexpr const_reference at(size_type n_) const;

  constexpr reference operator[](size_type n_);
  constexpr const_reference operator[](size_type n_) const;

  constexpr reference front();
  constexpr const_reference front() const;

  constexpr reference back();
  constexpr const_reference back() const;

  constexpr iterator begin() noexcept;
  constexpr const_iterator begin() const noexcept;
  constexpr iterator end() noexcept;
  constexpr const_iterator end() const noexcept;

  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;

  constexpr const_iterator cbegin() const noexcept;
  constexpr const_iterator cend() const noexcept;
  const_reverse_iterator crbegin() const noexcept;
  const_reverse_iterator crend() const noexcept;

  constexpr size_type size() const noexcept;
  constexpr size_type max_size() const noexcept;
  constexpr void resize(size_type);
  constexpr void resize(size_type, const bool &);
  constexpr size_type capacity() const noexcept;
  [[nodiscard]] constexpr bool empty() const noexcept;
  constexpr void reserve(size_type n);
  constexpr void shrink_to_fit();

  template <class... Args>
  constexpr void emplace_back(Args &&...);
  constexpr void push_back(const bool &);
  constexpr void push_back(bool &&);
  constexpr void pop_back();

  template <class... Args>
  constexpr iterator emplace(const_iterator, Args &&...);
  constexpr iterator insert(const_iterator, const bool &);
  constexpr iterator insert(const_iterator, bool &&);
  constexpr iterator insert(const_iterator, size_type, const bool &);
  template <class InputIt>
  constexpr iterator insert(const_iterator, InputIt, InputIt);
  constexpr iterator insert(const_iterator, std::initializer_list<bool>);

  constexpr iterator erase(const_iterator);
  constexpr iterator erase(const_iterator, const_iterator);
  constexpr void swap(vector<bool, Allocator> &);
  constexpr static void swap(reference x, reference y) noexcept;
  constexpr void flip() noexcept;
  constexpr void clear() noexcept;

private:
  const uint8_t m_growing_rate = 2;
}; // end class vector bool

template <class Allocator>
constexpr vector<bool, Allocator>::vector() {
  reserve(1);
  m_size = 0;
}

template <class Allocator>
constexpr vector<bool, Allocator>::vector(size_type n_) {
  reserve(n_ * m_growing_rate);
  m_size = n_;
}

template <class Allocator>
constexpr vector<bool, Allocator>::vector(size_type n_, const bool &val_) {
  m_size = m_capacity = n_;
  m_data = m_allocator.allocate(m_capacity);

  std::fill(begin(), end(), val_);
}

template <class Allocator>
template <class InputIt>
constexpr vector<bool, Allocator>::vector(InputIt first_, InputIt last_) {
  assign(first_, last_);
}

template <class Allocator>
constexpr vector<bool, Allocator>::vector(std::initializer_list<bool> lst_) {
  reserve(lst_.size() * m_growing_rate);

  std::move(lst_.begin(), lst_.end(), this->begin());
  m_size = lst_.size();
}

template <class Allocator>
constexpr vector<bool, Allocator>::vector(
    const vector<bool, Allocator> &other_) {
  reserve(other_.size() * m_growing_rate);
  std::move(other_.begin(), other_.end(), this->begin());
  m_size = other_.size();
}

template <class Allocator>
constexpr vector<bool, Allocator> &vector<bool, Allocator>::
operator=(const vector<bool, Allocator> &other_) {
  assign(other_.begin(), other_.end());

  return *this;
}

template <class Allocator>
constexpr vector<bool, Allocator> &vector<bool, Allocator>::
operator=(std::initializer_list<value_type> il_) {
  reserve(il_.size() * m_growing_rate);

  std::move(il_.begin(), il_.end(), this->begin());
  m_size = il_.size();

  return *this;
}

template <class Allocator>
constexpr vector<bool, Allocator>::vector(vector &&other_) {
  m_data = std::move(other_.m_data);
  m_size = other_.m_size;
  m_capacity = other_.m_capacity;

  other_.m_data = nullptr;
  other_.m_capacity = 0;
  other_.m_size = 0;
}

template <class Allocator>
constexpr vector<bool, Allocator> &vector<bool, Allocator>::
operator=(vector &&other_) {

  m_data = std::move(other_.m_data);
  m_size = other_.m_size;
  m_capacity = other_.m_capacity;

  other_.m_data = nullptr;
  other_.m_capacity = 0;
  other_.m_size = 0;

  return *this;
}

template <class Allocator>
vector<bool, Allocator>::~vector() noexcept {
  m_allocator.deallocate(m_data, m_capacity);
  m_size = 0;
  m_capacity = 0;
}

template <class Allocator>
constexpr void vector<bool, Allocator>::assign(size_type count_,
                                               const bool &value_) {
  reserve(count_ * m_growing_rate);
  m_size = count_;
  std::fill(begin(), end(), value_);
}

template <class Allocator>
template <class InputIt>
constexpr void vector<bool, Allocator>::assign(InputIt first_, InputIt last_) {

  size_type length_of_interval =
      static_cast<size_type>(std::distance(first_, last_));

  reserve((size() + length_of_interval) * m_growing_rate);

  std::move(first_, last_, begin());
  m_size += static_cast<size_type>(std::distance(first_, last_) * 2);
}

template <class Allocator>
constexpr void
vector<bool, Allocator>::assign(std::initializer_list<bool> il_) {
  reserve(il_.size() * m_growing_rate);
  std::move(il_.begin(), il_.end(), begin());
  m_size = il_.size();
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::allocator_type
vector<bool, Allocator>::get_allocator() const noexcept {
  return m_allocator;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::reference
vector<bool, Allocator>::at(size_type index_) {
  if (index_ >= size()) {
    throw std::out_of_range("Billions of Bilious Blue Blistering Barnacles! "
                            "You attempted to access out of range");
  }
  return m_data[index_];
}

template <class Allocator>
typename vector<bool, Allocator>::const_reference constexpr vector<
    bool, Allocator>::at(size_type index_) const {
  if (index_ >= size()) {
    throw std::out_of_range("Billions of Bilious Blue Blistering Barnacles! "
                            "Attemp to access out of range");
  }
  return m_data[index_];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::reference vector<bool, Allocator>::
operator[](size_type pos_) {
  return m_data[pos_];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_reference
    vector<bool, Allocator>::operator[](size_type pos_) const {
  return m_data[pos_];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::reference
vector<bool, Allocator>::front() {
  return m_data[0];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_reference
vector<bool, Allocator>::front() const {
  return m_data[0];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::reference
vector<bool, Allocator>::back() {
  return m_data[m_size - 1];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_reference
vector<bool, Allocator>::back() const {
  return m_data[m_size - 1];
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::begin() noexcept {
  return (m_data + 0);
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_iterator
vector<bool, Allocator>::begin() const noexcept {
  return (m_data + 0);
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_iterator
vector<bool, Allocator>::cbegin() const noexcept {
  return (m_data + 0);
}

template <class Allocator>
typename vector<bool, Allocator>::reverse_iterator
vector<bool, Allocator>::rbegin() noexcept {
  return reverse_iterator(end());
}

template <class Allocator>
typename vector<bool, Allocator>::const_reverse_iterator
vector<bool, Allocator>::rbegin() const noexcept {
  return const_reverse_iterator(end());
}

template <class Allocator>
typename vector<bool, Allocator>::const_reverse_iterator
vector<bool, Allocator>::crbegin() const noexcept {
  return const_reverse_iterator(end());
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::end() noexcept {
  return (m_data + m_size);
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_iterator
vector<bool, Allocator>::end() const noexcept {
  return (m_data + m_size);
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::const_iterator
vector<bool, Allocator>::cend() const noexcept {
  return (m_data + m_size);
}

template <class Allocator>
typename vector<bool, Allocator>::reverse_iterator
vector<bool, Allocator>::rend() noexcept {
  return reverse_iterator(begin());
}

template <class Allocator>
typename vector<bool, Allocator>::const_reverse_iterator
vector<bool, Allocator>::rend() const noexcept {
  return const_reverse_iterator(begin());
}

template <class Allocator>
typename vector<bool, Allocator>::const_reverse_iterator
vector<bool, Allocator>::crend() const noexcept {
  return const_reverse_iterator(cbegin());
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::size_type
vector<bool, Allocator>::size() const noexcept {
  return m_size;
}

template <class Allocator>
constexpr void vector<bool, Allocator>::resize(size_type count_) {
  m_size = count_;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);
}

template <class Allocator>
constexpr void vector<bool, Allocator>::resize(size_type count_,
                                               const value_type &value_) {
  size_type old_size = m_size;
  m_size = count_;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);

  if (old_size > count_) {
    std::fill(begin() + count_, begin() + old_size, value_);
  } else {
    std::fill(begin() + old_size, begin() + count_, value_);
  }
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::size_type
vector<bool, Allocator>::capacity() const noexcept {
  return m_capacity;
}

template <class Allocator>
constexpr bool vector<bool, Allocator>::empty() const noexcept {
  //  return m_size == 0;
  return begin() == end();
}
template <class Allocator>
constexpr void vector<bool, Allocator>::reserve(size_type new_cap_) {
  if (new_cap_ != m_capacity) {
    if (new_cap_ > max_size())
      throw std::length_error("You, imitation Incas, you... Length ERROR!!!");

    if (empty()) {
      m_data = m_allocator.allocate(new_cap_);
      m_capacity = new_cap_;
    } else {
      bool *tmp = m_allocator.allocate(new_cap_);
      std::move(begin(), end(), tmp);
      m_allocator.deallocate(m_data, m_capacity);

      m_data = tmp;
      tmp = nullptr;
      m_capacity = new_cap_;
    }
  }
}

template <class Allocator>
constexpr void vector<bool, Allocator>::shrink_to_fit() {
  m_capacity = m_size;
}

template <class Allocator>
template <class... Args>
constexpr void vector<bool, Allocator>::emplace_back(Args &&... args_) {
  ++m_size;

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  *(end() - 1) = std::move(bool(std::forward<Args>(args_)...));
}

template <class Allocator>
constexpr void vector<bool, Allocator>::push_back(const bool &val_) {
  m_data[m_size++] = val_;

  if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);
}

template <class Allocator>
constexpr void vector<bool, Allocator>::push_back(bool &&val_) {
  m_data[m_size++] = std::move(val_);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);
}

template <class Allocator>
constexpr void vector<bool, Allocator>::pop_back() {
  if (!empty()) {
    --m_size;

    if (size() <= capacity() / 4)
      reserve(size() / m_growing_rate);
  }
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::size_type
vector<bool, Allocator>::max_size() const noexcept {
  return std::numeric_limits<difference_type>::max();
}

template <class Allocator>
template <class... Args>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::emplace(const_iterator pos_, Args &&... args_) {

  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = std::move(std::forward<Args>(args_)...);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::insert(const_iterator pos_, const bool &val_) {
  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = val_;

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  if (empty()) {
    *begin() = val_;
    ++m_size;

    return begin();
  }

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::insert(const_iterator pos_, bool &&val_) {
  iterator ret = const_cast<iterator>(pos_);

  ++m_size;
  std::move_backward(ret, end() - 1, end());

  *ret = std::move(val_);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  if (empty()) {
    *begin() = std::move(val_);
    ++m_size;

    return begin();
  }

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::insert(const_iterator pos_, size_type count_,
                                const bool &val_) {

  iterator ret = const_cast<iterator>(pos_);

  if (empty() && capacity() < count_) {
    reserve(count_ * 2);
    m_size = count_;

    std::fill(begin(), end(), val_);
    return begin();
  } else {
    m_size += count_;

    std::move_backward(ret, end() - count_, end());
    std::fill(ret, ret + count_, val_);

    if (size() * 2 >= capacity())
      reserve(capacity() * m_growing_rate);

    return ret;
  }
}

template <class Allocator>
template <class InputIt>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::insert(const_iterator pos_, InputIt first_,
                                InputIt last_) {

  iterator ret = const_cast<iterator>(pos_);

  size_type diff = static_cast<size_type>(std::distance(first_, last_));

  m_size += diff;

  std::move_backward(ret, end() - diff, end());
  std::move(first_, last_, ret);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::insert(const_iterator pos_,
                                std::initializer_list<bool> lst_) {

  iterator ret = const_cast<iterator>(pos_);

  m_size += lst_.size();

  std::move_backward(ret, end() - lst_.size(), end());
  std::move(lst_.begin(), lst_.end(), ret);

  if (size() * 2 >= capacity())
    reserve(capacity() * m_growing_rate);

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::erase(const_iterator pos_) {

  iterator ret = const_cast<iterator>(pos_);
  std::move(ret + 1, end(), ret);
  --m_size;

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);

  return ret;
}

template <class Allocator>
constexpr typename vector<bool, Allocator>::iterator
vector<bool, Allocator>::erase(const_iterator first_, const_iterator last_) {
  difference_type diff = last_ - first_;
  iterator ret = const_cast<iterator>(first_);

  std::move(last_, cend(), ret);

  m_size -= static_cast<size_type>(diff);

  if (size() <= capacity() / 4)
    reserve(size() / m_growing_rate);
  else if (size() * 2 >= capacity())
    reserve(m_capacity * m_growing_rate);

  return ret;
}

template <class Allocator>
constexpr void vector<bool, Allocator>::flip() noexcept {
  std::for_each(begin(), end(), [](bool &element) { element = !element; });
}

template <class Allocator>
constexpr void vector<bool, Allocator>::clear() noexcept {
  m_size = 0;
}

template <class Allocator>
constexpr void vector<bool, Allocator>::swap(vector<bool, Allocator> &other_) {

  size_type tmp_size = other_.size();
  size_type tmp_capacity = other_.capacity();
  auto tmp_data = other_.m_data;

  other_.m_size = m_size;
  other_.m_capacity = m_capacity;
  other_.m_data = m_data;

  m_size = tmp_size;
  m_capacity = tmp_capacity;
  m_data = tmp_data;
}

template <class Allocator>
constexpr void vector<bool, Allocator>::swap(reference x,
                                             reference y) noexcept {
  reference tmp = x;
  x = y;
  y = tmp;
}

} // namespace p1v0t
\$\endgroup\$
1
  • \$\begingroup\$ @L.F. I really didn't know how to write it and simply copy pasted it from here. It encouraged me to write rest of implementation. \$\endgroup\$
    – user201793
    Jul 11, 2019 at 7:09

1 Answer 1

6
\$\begingroup\$

Here are some suggestions.

Non conformance

Many of your functions are marked constexpr. This is non-conforming. Per [constexpr.functions]:

This document explicitly requires that certain standard library functions are constexpr ([dcl.constexpr]). An implementation shall not declare any standard library function signature as constexpr except for those where it is explicitly required. Within any header that provides any non-defining declarations of constexpr functions or constructors an implementation shall provide corresponding definitions.

And generally speaking, you cannot expect allocation to be constexpr anyway.

You are missing allocator overloads for the constructors. Specifically, the following overloads vanish altogether:

explicit vector(const Allocator&) noexcept;     
vector(const vector&, const Allocator&);
vector(vector&&, const Allocator&);

And the allocator parameters are missing in the following overloads:

explicit vector(const Allocator&) noexcept;
explicit vector(size_type n, const Allocator& = Allocator());
vector(size_type n, const T& value, const Allocator& = Allocator());
template<class InputIterator>
  vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
vector(const vector&, const Allocator&);
vector(vector&&, const Allocator&);
vector(initializer_list<T>, const Allocator& = Allocator());

They aren't hard to implement, so why not implement them anyway?

You mark your destructor virtual. This is definitely wrong. vector is not designed for runtime polymorphism. Marking the destructor virtual can lead to severe consequences.

max_size returns size_type, not difference_type. data returns T* and const T*, not pointer and const_pointer (they can be different). swap is not unconditionally noexcept; the correct version is

void swap(vector&)
      noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
               allocator_traits<Allocator>::is_always_equal::value);

You use fill on uninitialized memory:

template <typename T, class Allocator>
constexpr vector<T, Allocator>::vector(size_t n_, const value_type &val_) {
  m_size = m_capacity = n_;
  m_data = m_allocator.allocate(m_capacity);

  std::fill(begin(), end(), val_);
}

This is undefined behavior because the lifetime of the objects are not started. You should use uninitialized_fill instead, which requires #include <memory>. (This happens multiple times in your code.)

The iterator overload of the constructor participates in overload resolution only when InputIt is an input iterator. The extent to which the library determines input iterators is unspecified, but at least integer types should not qualify as input iterator. Your version participates in overload resolution even if InputIt is an integer type. This can be fixed with SFINAE:

template <class InputIt, typename std::iterator_traits<InputIt>::iterator_category* = nullptr>
vector(InputIt first, InputIt last);

Or, with C++20, concepts:

template <std::input_iterator InputIt>
vector(InputIt first, InputIt last);

Moving from initializer_list does not do what you expect it to do because the elements of initializer_list are const. Moreover, using move on uninitialized memory is undefined behavior. Use uninitialized_copy instead.

The copy constructor of vector calls std::allocator_traits<allocator_type>::select_on_container_copy_construction to select the appropriate allocator. And again, don't use move. Use uninitialized_copy.

Similarly, the copy assignment operator should decide whether to propagate the allocator depending on whether std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment is true or not.

These also apply to the move operations. And consider using the copy-and-swap idiom when feasible.

Your shrink_to_fit is problematic:

template <typename T, class Allocator>
void vector<T, Allocator>::shrink_to_fit() {
  m_capacity = m_size;
}

This breaks the class invariant and causes problems on deallocation.

You never call constructors or destructors on the elements. This makes your vector unable to handle nontrivial types.

Other suggestions

Generally speaking, #pragma once is OK for me. But in this case, since you are implementing a component in the standard library, I'd advise you to resort to #ifndef#define#endif for portability.

Your data members m_allocator, m_data, m_capacity, and m_size are all public. I don't see a reason. I suggest making them private. Also, why is m_growing_rate of type uint8_t (which should be std::uint8_t and requires #include <cstdint>), and why is it not constexpr?

You love assignment and hate initializer clauses. This way, you first default initialize (or use the in class member initializer) and then assign, causing performace degradation. Use initializer clauses. Instead of:

template <typename T, class Allocator>
vector<T, Allocator>::vector() noexcept(noexcept(Allocator())) {
  m_size = 0;
  reserve(1);
}

It is sufficient to do

template <typename T, class Allocator>
vector<T, Allocator>::vector() noexcept(noexcept(Allocator())) { }

Since you already provided an in class initializer for m_size.

Your allocation policy is to always reserve a lot of space. vector is not always resized. If the user doesn't intend to grow it, your policy actually decreases efficiency. I would suggest reserving space only on insert or the like.

It is not wrong to use m_allocator.allocate(m_capacity), but it is still advised to do std::allocator_traits<Allocator>::allocate(m_allocator, m_capacity).

Your code features duplication. For example, it may be a good idea to let the initializer_list overloads delegate to the iterator overloads.

\$\endgroup\$
5
  • \$\begingroup\$ Gosh... Thanks from the heart!! I will definitely consider all the things you point. \$\endgroup\$
    – user201793
    Jul 11, 2019 at 7:16
  • \$\begingroup\$ Can you give me one more pointer for how to implement one of the member functions that take the allocator as a parameter. I checked out the some other Standard Library implementations, the vector class inherited from other base class. I thought it's something related with it and didn't try to implement them. \$\endgroup\$
    – user201793
    Jul 11, 2019 at 7:28
  • 2
    \$\begingroup\$ @adem You do not necessarily need to use inheritance. Simply initialize m_allocator with the given argument and use std::allocator_traits<Allocator>::allocate(m_allocator, ...) to allocate memory, std::allocator_traits<Allocator>::deallocate(m_allocator, ...) to deallocate memory, std::allocator_traits<Allocator>::construct(m_allocator, ...) to construct the elements, and std::allocator_traits<Allocator>::destroy(m_allocator, ...) to destroy them. \$\endgroup\$
    – L. F.
    Jul 11, 2019 at 9:16
  • \$\begingroup\$ @adem Also, implementing vector properly is extremely nontrivial. You should probably start simpler if you consider yourself a beginner. I cannot say for sure I can implement vector well either :) \$\endgroup\$
    – L. F.
    Jul 11, 2019 at 9:17
  • 2
    \$\begingroup\$ Yeah, when I saw the propagate things... I got 'umm I shouldn't be here' feeling :))) \$\endgroup\$
    – user201793
    Jul 11, 2019 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.