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