- Implements most (if not all) applicable member functions from std::vector and std::array
- Compatible with C++11, C++14, C++17, C++20
- [] operator allows unchecked access, all other member functions throw
#ifndef STAT_VEC_H
#define STAT_VEC_H
#include <memory>
#include <cstddef>
#include <cstring>
#include <iterator>
#include <stdexcept>
#include <type_traits>
// A growable, stack based vector
#if ((defined(_MSVC_LANG) && _MSVC_LANG >= 201703L) || __cplusplus >= 201703L)
#define STAT_VEC_HAS_CXX17 1
#endif
#if ((defined(_MSVC_LANG) && _MSVC_LANG >= 202002L) || __cplusplus >= 202002L)
#define STAT_VEC_HAS_CXX20 1
#endif
#ifdef STAT_VEC_HAS_CXX20
#define STAT_VEC_CONSTEXPR_CXX20 constexpr
#else
#define STAT_VEC_CONSTEXPR_CXX20 inline
#endif
#ifdef STAT_VEC_HAS_CXX17
#define STAT_VEC_NODISCARD [[nodiscard]]
#define STAT_VEC_BYTE_T std::byte
#else
#define STAT_VEC_NODISCARD
#define STAT_VEC_BYTE_T unsigned char
#endif
template <typename StaticVectorT>
class static_vec_const_iter {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename StaticVectorT::value_type;
using difference_type = ptrdiff_t;
using pointer = const value_type*;
using reference = const value_type&;
private:
using arr_pointer = const StaticVectorT*;
arr_pointer m_arr;
size_t m_idx;
void check_compat(const static_vec_const_iter& other) const
{
if (m_arr != other.m_arr) {
throw std::logic_error("Non-compatible iterators");
}
}
template <typename T, size_t Capacity>
friend class static_vec;
public:
STAT_VEC_CONSTEXPR_CXX20 explicit static_vec_const_iter(arr_pointer arr, size_t idx) noexcept : m_arr{ arr }, m_idx{ idx } {}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 reference operator*() const
{
return *operator->();
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 pointer operator->() const
{
if (m_idx >= m_arr->size()) {
throw std::out_of_range("Cannot dereference out of range iterator");
}
return m_arr->data() + m_idx;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter& operator++()
{
if (m_idx >= m_arr->size()) {
throw std::out_of_range("Cannot increment iterator past end");
}
++m_idx;
return *this;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter operator++(int)
{
static_vec_const_iter ret = *this;
++* this;
return ret;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter& operator--()
{
if (m_idx == 0) {
throw std::out_of_range("Cannot decrement iterator before end");
}
--m_idx;
return *this;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter operator--(int)
{
static_vec_const_iter ret = *this;
--* this;
return ret;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter& operator+=(const ptrdiff_t offset)
{
if (offset < 0 && size_t{ ptrdiff_t{0} - offset } > m_idx) {
throw std::out_of_range("Cannot decrement iterator before end");
}
if (offset > 0 && static_cast<size_t>(offset) > m_arr->size() - m_idx) {
throw std::out_of_range("Cannot increment iterator past end");
}
m_idx += static_cast<size_t>(offset);
return *this;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter operator+(const ptrdiff_t offset)
{
static_vec_const_iter ret = *this;
return ret += offset;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter& operator-=(const ptrdiff_t offset)
{
return *this += -offset;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 static_vec_const_iter operator-(const ptrdiff_t offset)
{
static_vec_const_iter ret = *this;
return ret -= offset;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 ptrdiff_t operator-(const static_vec_const_iter& other) const
{
check_compat(other);
return static_cast<ptrdiff_t>(m_idx - other.m_idx);
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 reference operator[](const ptrdiff_t offset) const
{
return *(*this + offset);
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator==(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx = other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator!=(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx != other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator<(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx < other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator>(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx < other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator<=(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx <= other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator>=(const static_vec_const_iter& other) const
{
check_compat(other);
return m_idx >= other.m_idx;
}
};
template <typename StaticVectorT>
class static_vec_iter {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename StaticVectorT::value_type;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
private:
using arr_pointer = StaticVectorT*;
arr_pointer m_arr;
size_t m_idx;
void check_compat(const static_vec_iter& other) const
{
if (m_arr != other.m_arr) {
throw std::logic_error("Non-compatible iterators");
}
}
template <typename T, size_t Capacity>
friend class static_vec;
public:
STAT_VEC_CONSTEXPR_CXX20 explicit static_vec_iter(arr_pointer arr, size_t idx) noexcept : m_arr{ arr }, m_idx{ idx } {}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 reference operator*() const
{
return *operator->();
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 pointer operator->() const
{
if (m_idx >= m_arr->size()) {
throw std::out_of_range("Cannot dereference out of range iterator");
}
return m_arr->data() + m_idx;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter& operator++()
{
if (m_idx >= m_arr->size()) {
throw std::out_of_range("Cannot increment iterator past end");
}
++m_idx;
return *this;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter operator++(int)
{
static_vec_iter ret = *this;
++* this;
return ret;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter& operator--()
{
if (m_idx == 0) {
throw std::out_of_range("Cannot decrement iterator before end");
}
--m_idx;
return *this;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter operator--(int)
{
static_vec_iter ret = *this;
--* this;
return ret;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter& operator+=(const ptrdiff_t offset)
{
if (offset < 0 && size_t{ ptrdiff_t{0} - offset } > m_idx) {
throw std::out_of_range("Cannot decrement iterator before end");
}
if (offset > 0 && static_cast<size_t>(offset) > m_arr->size() - m_idx) {
throw std::out_of_range("Cannot increment iterator past end");
}
m_idx += static_cast<size_t>(offset);
return *this;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 static_vec_iter operator+(const ptrdiff_t offset)
{
static_vec_iter ret = *this;
return ret += offset;
}
STAT_VEC_CONSTEXPR_CXX20 static_vec_iter& operator-=(const ptrdiff_t offset)
{
return *this += -offset;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 static_vec_iter operator-(const ptrdiff_t offset)
{
static_vec_iter ret = *this;
return ret -= offset;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 ptrdiff_t operator-(const static_vec_iter& other) const
{
check_compat(other);
return static_cast<ptrdiff_t>(m_idx - other.m_idx);
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 reference operator[](const ptrdiff_t offset) const
{
return *(*this + offset);
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator==(const static_vec_iter& other) const
{
check_compat(other);
return m_idx == other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator!=(const static_vec_iter& other) const
{
check_compat(other);
return m_idx != other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator<(const static_vec_iter& other) const
{
check_compat(other);
return m_idx < other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator>(const static_vec_iter& other) const
{
check_compat(other);
return m_idx < other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator<=(const static_vec_iter& other) const
{
check_compat(other);
return m_idx <= other.m_idx;
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool operator>=(const static_vec_iter& other) const
{
check_compat(other);
return m_idx >= other.m_idx;
}
operator static_vec_const_iter<StaticVectorT>() const
{
return static_vec_const_iter<StaticVectorT>(m_arr, m_idx);
}
};
template <typename T, size_t Capacity>
class static_vec {
public:
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using iterator = static_vec_iter<static_vec>;
using const_iterator = static_vec_const_iter<static_vec>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
private:
size_type m_size;
alignas(T) STAT_VEC_BYTE_T m_data[sizeof(T) * Capacity];
inline void check_not_full()
{
if (m_size >= Capacity) {
throw std::out_of_range("Buffer is full");
}
}
inline void check_not_empty()
{
if (m_size == 0) {
throw std::out_of_range("Buffer is empty");
}
}
inline void check_in_bounds(size_type idx)
{
if (idx >= m_size) {
throw std::out_of_range("Out of bounds");
}
}
inline void check_insert(size_type idx, size_type count)
{
if ((m_size + count) > Capacity) {
throw std::out_of_range("Not enough room in buffer");
}
if (idx > m_size) {
throw std::out_of_range("Out of bounds");
}
}
inline void check_erase(size_type idx, size_type count)
{
if (m_size == 0) {
throw std::out_of_range("Buffer is empty");
}
if (idx + count > m_size) {
throw std::out_of_range("Out of bounds");
}
}
template <class iterT>
inline void check_iters(iterT first, iterT last)
{
if (std::distance(first, last) < 0) {
throw std::out_of_range("Last iterator at or after first iterator");
}
}
inline pointer unchecked_ptr_at(size_type idx)
{
return reinterpret_cast<T*>(&m_data[idx * sizeof(T)]);
}
inline const_pointer unchecked_ptr_at(size_type idx) const
{
return reinterpret_cast<const T*>(&m_data[idx * sizeof(T)]);
}
inline reference unchecked_at(size_type idx)
{
return *unchecked_ptr_at(idx);
}
inline const_reference unchecked_at(size_type idx) const
{
return *unchecked_ptr_at(idx);
}
template <class... U>
using void_t = void;
template <class U, class = void>
struct is_input_iterator : std::false_type {
};
template <class U>
struct is_input_iterator<U, static_vec::void_t<
typename std::iterator_traits<U>::iterator_category,
typename std::iterator_traits<U>::value_type,
typename std::iterator_traits<U>::reference,
typename std::iterator_traits<U>::difference_type,
decltype(++std::declval<U&>()), // prefix incrementable,
decltype(std::declval<U&>()++), // postfix incrementable,
decltype(*std::declval<U&>()), // dereferencable via *,
decltype(std::declval<U&>().operator->()), // dereferencable via ->,
decltype(std::declval<U&>() == std::declval<U&>()) // comparable
> > : std::true_type {
};
template <class U>
using is_input_iterator_t = typename is_input_iterator<U>::type;
public:
static_vec()
: m_size{ 0 }
, m_data{}
{
}
~static_vec()
{
clear();
}
STAT_VEC_CONSTEXPR_CXX20 reference at(size_type idx)
{
check_in_bounds(idx);
return unchecked_at(idx);
}
STAT_VEC_CONSTEXPR_CXX20 const_reference at(size_type idx) const
{
check_in_bounds(idx);
return unchecked_at(idx);
}
STAT_VEC_CONSTEXPR_CXX20 reference operator[](size_type idx)
{
return unchecked_at(idx);
}
STAT_VEC_CONSTEXPR_CXX20 const_reference operator[](size_type idx) const
{
return unchecked_at(idx);
}
STAT_VEC_CONSTEXPR_CXX20 reference front()
{
check_not_empty();
return unchecked_at(0);
}
STAT_VEC_CONSTEXPR_CXX20 const_reference front() const
{
check_not_empty();
return unchecked_at(0);
}
STAT_VEC_CONSTEXPR_CXX20 reference back()
{
check_not_empty();
return unchecked_at(m_size - 1);
}
STAT_VEC_CONSTEXPR_CXX20 const_reference back() const
{
check_not_empty();
return unchecked_at(m_size - 1);
}
STAT_VEC_CONSTEXPR_CXX20 pointer data() noexcept
{
return reinterpret_cast<T*>(m_data);
}
STAT_VEC_CONSTEXPR_CXX20 const_pointer data() const noexcept
{
return reinterpret_cast<const T*>(m_data);
}
STAT_VEC_CONSTEXPR_CXX20 iterator begin() noexcept
{
return iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 const_iterator begin() const noexcept
{
return const_iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 const_iterator cbegin() const noexcept
{
return const_iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 iterator end() noexcept
{
return iterator(this, m_size);
}
STAT_VEC_CONSTEXPR_CXX20 const_iterator end() const noexcept
{
return const_iterator(this, m_size);
}
STAT_VEC_CONSTEXPR_CXX20 const_iterator cend() const noexcept
{
return const_iterator(this, m_size);
}
STAT_VEC_CONSTEXPR_CXX20 reverse_iterator rbegin() noexcept
{
return reverse_iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 const_reverse_iterator rbegin() const noexcept
{
return const_reverse_iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 const_reverse_iterator crbegin() const noexcept
{
return const_reverse_iterator(this, 0);
}
STAT_VEC_CONSTEXPR_CXX20 reverse_iterator rend() noexcept
{
return reverse_iterator(this, m_size);
}
STAT_VEC_CONSTEXPR_CXX20 const_reverse_iterator rend() const noexcept
{
return const_reverse_iterator(this, m_size);
}
STAT_VEC_CONSTEXPR_CXX20 const_reverse_iterator crend() const noexcept
{
return const_reverse_iterator(this, m_size);
}
STAT_VEC_NODISCARD STAT_VEC_CONSTEXPR_CXX20 bool empty() const noexcept
{
return m_size == 0;
}
STAT_VEC_CONSTEXPR_CXX20 size_type size() const noexcept
{
return m_size;
}
STAT_VEC_CONSTEXPR_CXX20 size_type max_size() const noexcept
{
return Capacity;
}
STAT_VEC_CONSTEXPR_CXX20 size_type capacity() const noexcept
{
return Capacity;
}
STAT_VEC_CONSTEXPR_CXX20 void clear() noexcept
{
for (size_type i = 0; i < m_size; i++) {
unchecked_at(i).~T();
}
m_size = 0;
}
STAT_VEC_CONSTEXPR_CXX20 iterator insert(const_iterator pos, const T& value)
{
check_insert(pos.m_idx, 1);
m_size++;
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i), unchecked_ptr_at(i - 1), sizeof(T));
}
new (unchecked_ptr_at(pos.m_idx)) T(value);
return iterator(this, pos.m_idx);
}
STAT_VEC_CONSTEXPR_CXX20 iterator insert(const_iterator pos, T&& value)
{
check_insert(pos.m_idx, 1);
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i), unchecked_ptr_at(i - 1), sizeof(T));
}
new (unchecked_ptr_at(pos.m_idx)) T(std::move(value));
m_size++;
return iterator(this, pos.m_idx);
}
iterator insert(const_iterator pos, size_type count, const T& value)
{
if (count > 0) {
check_insert(pos.m_idx, count);
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i + count - 1), unchecked_ptr_at(i - 1), sizeof(T));
}
for (size_t i = 0; i < count; i++) {
new (unchecked_ptr_at(pos.m_idx + i)) T(value);
}
m_size += count;
}
return iterator(this, pos.m_idx);
}
template <class InputIt, typename std::enable_if<static_vec::is_input_iterator_t<InputIt>::value, bool>::type = true>
STAT_VEC_CONSTEXPR_CXX20 iterator insert(const_iterator pos, InputIt first, InputIt last)
{
check_iters(first, last);
size_t count = std::distance(first, last);
if (count > 0) {
check_insert(pos.m_idx, count);
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i + count - 1), unchecked_ptr_at(i - 1), sizeof(T));
}
for (size_t i = 0; i < count; i++) {
new (unchecked_ptr_at(pos.m_idx + i)) T(*(first + i));
}
m_size += count;
}
return iterator(this, pos.m_idx);
}
STAT_VEC_CONSTEXPR_CXX20 iterator insert(const_iterator pos, std::initializer_list<T> ilist)
{
if (ilist.size() > 0) {
check_insert(pos.m_idx, ilist.size());
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i + ilist.size() - 1), unchecked_ptr_at(i - 1), sizeof(T));
}
for (size_t i = 0; i < ilist.size(); i++) {
new (unchecked_ptr_at(pos.m_idx + i)) T(*(ilist.begin() + i));
}
m_size += ilist.size();
}
return iterator(this, pos.m_idx);
}
template <class... Args>
STAT_VEC_CONSTEXPR_CXX20 iterator emplace(const_iterator pos, Args&&... args)
{
check_insert(pos.m_idx, 1);
for (size_t i = m_size; i > pos.m_idx; i--) {
std::memcpy(unchecked_ptr_at(i), unchecked_ptr_at(i - 1), sizeof(T));
}
new (unchecked_ptr_at(pos.m_idx)) T(std::forward<Args>(args)...);
m_size++;
return iterator(this, pos.m_idx);
}
STAT_VEC_CONSTEXPR_CXX20 iterator erase(const_iterator pos)
{
check_erase(pos.m_idx, 1);
unchecked_at(pos.m_idx).~T();
for (size_t i = pos.m_idx; i < m_size - pos.m_idx; i++) {
std::memcpy(unchecked_ptr_at(i), unchecked_ptr_at(i + 1), sizeof(T));
}
m_size--;
return iterator(this, pos.m_idx + 1);
}
STAT_VEC_CONSTEXPR_CXX20 iterator erase(const_iterator first, const_iterator last)
{
check_iters(first, last);
size_t count = std::distance(first, last);
if (count > 0) {
check_erase(first.m_idx, count);
for (size_t i = 0; i < count; i++) {
unchecked_at(first.m_idx + i).~T();
}
for (size_t i = first.m_idx; i < m_size - first.m_idx; i++) {
std::memcpy(unchecked_ptr_at(i), unchecked_ptr_at(i + count), sizeof(T));
}
m_size -= count;
}
return iterator(this, first.m_idx + count);
}
STAT_VEC_CONSTEXPR_CXX20 void push_back(const T& value)
{
check_not_full();
new (unchecked_ptr_at(m_size)) T(value);
m_size++;
}
STAT_VEC_CONSTEXPR_CXX20 void push_back(T&& value)
{
check_not_full();
new (unchecked_ptr_at(m_size)) T(std::move(value));
m_size++;
}
template <class... Args>
STAT_VEC_CONSTEXPR_CXX20 T& emplace_back(Args&&... args)
{
check_not_full();
auto ptr = unchecked_ptr_at(m_size);
new (ptr) T(std::forward<Args>(args)...);
m_size++;
return *ptr;
}
STAT_VEC_CONSTEXPR_CXX20 void pop_back()
{
check_not_empty();
m_size--;
unchecked_at(m_size).~T();
}
STAT_VEC_CONSTEXPR_CXX20 void fill(const T& value)
{
clear();
for (size_t i = 0; i < Capacity; i++) {
new (unchecked_ptr_at(i)) T(value);
}
m_size = Capacity;
}
STAT_VEC_CONSTEXPR_CXX20 void swap(static_vec<T, Capacity>& other) noexcept
{
size_t temp_size = 0;
alignas(T) STAT_VEC_BYTE_T temp_data[sizeof(T) * Capacity];
std::memcpy(temp_data, m_data, sizeof(T) * Capacity);
std::memcpy(m_data, other.m_data, sizeof(T) * Capacity);
std::memcpy(other.m_data, temp_data, sizeof(T) * Capacity);
temp_size = m_size;
m_size = other.m_size;
other.m_size = temp_size;
}
};
#endif /* STAT_VEC_H */