This is a revised and expanded implementation of the original static_vector implementation based on the various suggestions and corrections from the kind people who reviewed the original version.The static_vector essentially implements a fixed_capacity contiguous container with strictly inline storage. Again, please kindly provide any review/comments on this new implementation, in particular with regards to constexpr-correctness and exception-correctness. For those who are interested and for reference, here's the original implementation: original implementation
#ifndef OL_STATIC_VECTOR_HPP_
#define OL_STATIC_VECTOR_HPP_
#include <cstdint>
#include <cstddef>
#include <cassert>
#include <cstdlib>
#include <limits>
#include <utility>
#include <iterator>
#include <type_traits>
#include <algorithm>
#include <iostream>
#define OL_NO_EXCEPTIONS true
#define OL_CPP_VERSION_NEWER_THAN(x) (__cplusplus >= (x))
#define OL_CPP_VERSION_OLDER_THAN(x) (__cplusplus < (x))
#define OL_ASSERT(expr) assert(expr)
#if defined(__cpp_lib_unreachable) && __cpp_lib_unreachable >= 202202L
#include <utility> // For std::unreachable
#define OL_UNREACHABLE() std::unreachable()
#elif defined(__GNUC__) || defined(__clang__)
#define OL_UNREACHABLE() __builtin_unreachable()
#elif defined(_MSC_VER)
#define OL_UNREACHABLE() __assume(0)
#else
#define OL_UNREACHABLE() std::abort()
#endif
#if OL_NO_EXCEPTIONS //disable exceptions
#include <iostream>
#define OL_THROW(type, msg) \
do{ \
if(not std::is_constant_evaluated()) { \
std::cerr << msg << std::endl; \
std::abort(); \
} else { \
assert(false); \
} \
} while (0)
#else // has exceptions
#define OL_THROW(type, msg) throw type{msg}
#endif //OL_NO_EXCEPTIONS
#if defined(__GNUC__) && __GNUC__ >= 10 // For GCC 10 and later, constexpr placement new is available
#define OL_GCC10_CONSTEXPR constexpr
#else
#define OL_GCC10_CONSTEXPR
#endif // defined(__GNUC__) && __GNUC__ >= 10
#if OL_CPP_VERSION_NEWER_THAN(202002L) // C++20 or newer
#include <memory>
#define OL_CPP20_CONSTEXPR constexpr
#define OL_MOVE(...) std::move(__VA_ARGS__)
#define OL_MOVE_BACKWARD(...) std::move_backward(__VA_ARGS__)
#define OL_CONSTRUCT_AT(...) std::construct_at(__VA_ARGS__)
#define OL_DESTROY_AT(...) std::destroy_at(__VA_ARGS__)
#define OL_DESTROY(...) std::destroy(__VA_ARGS__)
#else // c++17 or older
#include <new>
#define OL_CPP20_CONSTEXPR
#define OL_MOVE(...) ol::internal::move(__VA_ARGS__)
#define OL_MOVE_BACKWARD(...) ol::internal::move_backward(__VA_ARGS__)
#define OL_CONSTRUCT_AT(...) ol::internal::construct_at(__VA_ARGS__)
#define OL_DESTROY_AT(...) ol::internal::destroy_at(__VA_ARGS__)
#if OL_CPP_VERSION_NEWER_THAN(201703L)
#define OL_DESTROY(...) std::destroy(__VA_ARGS__)
#else
#define OL_DESTROY(...) ol::internal::destroy(__VA_ARGS__)
#endif //OL_CPP_VERSION_NEWER_THAN(201703L)
#endif //OL_CPP_VERSION_NEWER_THAN(202002L)
namespace ol{
namespace internal{
template<typename T, typename... Args>
inline OL_GCC10_CONSTEXPR auto construct_at(T* p, Args&&... args)
noexcept(noexcept(::new((void*)0) T(std::declval<Args>()...)))
-> decltype(::new((void*)0) T(std::declval<Args>()...))
{ return ::new((void*)p) T(std::forward<Args>(args)...); }
template <typename T>
inline void destroy_at(T* p) { p->~T(); }
template <typename It>
inline void destroy(It first, It last)
{
for (; first != last; ++first)
ol::internal::destroy_at(std::addressof(*first));
}
template <typename InputIt, typename OutputIt>
inline constexpr OutputIt move(InputIt first, InputIt last, OutputIt d_first) {
while (first != last) {
*d_first++ = std::move(*first++);
}
return d_first;
}
template <typename BiDirItFrom, typename BiDirItTo>
inline constexpr BiDirItTo move_backward(BiDirItFrom first, BiDirItFrom last, BiDirItTo d_last) {
while (first != last) {
*--d_last = std::move(*--last);
}
return d_last;
}
template <typename InputIt, typename ForwardIt>
inline constexpr ForwardIt uninitialized_copy(InputIt first, InputIt last, ForwardIt d_first) {
using src_value_type = typename std::iterator_traits<InputIt>::value_type;
using dest_value_type = typename std::iterator_traits<ForwardIt>::value_type;
using src_ref_type = typename std::iterator_traits<InputIt>::reference;
using dest_ref_type = typename std::iterator_traits<ForwardIt>::reference;
static_assert(std::is_constructible_v<dest_value_type, decltype(*first)>,
"result type must be constructible from value type of input range");
constexpr bool is_copy_optimizable_v{
std::is_trivial_v<src_value_type> &&
std::is_trivial_v<dest_value_type> &&
std::is_assignable_v<dest_ref_type, src_ref_type>};
ForwardIt current = d_first;
try{
for(; first != last; ++first, ++current) {
if constexpr(is_copy_optimizable_v) {
return std::copy(first, last, d_first);
}else{
std::construct_at(std::addressof(*current), *first);
return current;
}
}
} catch (...) {
std::destroy(d_first, current);
throw;
}
}
template <typename InputIt, typename ForwardIt>
inline constexpr ForwardIt uninitialized_move(InputIt first, InputIt last, ForwardIt d_first)
{
return std::uninitialized_copy(
std::make_move_iterator(first),
std::make_move_iterator(last), d_first);
}
template<std::size_t Uint_>
using MinWidthSizeType = typename std::conditional_t<
(Uint_ <= std::numeric_limits<std::uint8_t>::max()), std::uint8_t,
typename std::conditional_t<
(Uint_ <= std::numeric_limits<std::uint16_t>::max()), std::uint16_t,
typename std::conditional_t<
(Uint_ <= std::numeric_limits<std::uint32_t>::max()), std::uint32_t,
uint64_t
>
>
>;
template <typename T, std::size_t Capacity>
struct sv_storage_base {
typedef T value_type;
typedef value_type* pointer;
typedef value_type const* const_pointer;
typedef T& reference;
typedef T const& const_reference;
typedef MinWidthSizeType<Capacity> size_type;
static constexpr std::size_t capacity() noexcept { return Capacity; }
static constexpr std::size_t max_size() noexcept { return Capacity; }
};
template <typename T>
struct zero_capcity_storage : public sv_storage_base<T, 0u> {
using Base = sv_storage_base<T, 0u>;
using typename Base::size_type;
using typename Base::const_reference;
static constexpr auto data() noexcept { return nullptr; }
static constexpr std::size_t size() noexcept { return 0; }
static constexpr void set_size(size_type) noexcept { OL_UNREACHABLE(); }
template <typename... Args>
constexpr void emplace_back(Args...) noexcept { OL_UNREACHABLE(); };
constexpr void insert(size_type, const_reference) noexcept { OL_UNREACHABLE(); }
template <typename Range>
constexpr void insert_range(size_type, Range&&) noexcept { OL_UNREACHABLE(); }
template <typename Range>
constexpr void push_back_range(Range&&) noexcept { OL_UNREACHABLE(); }
template <typename... Args>
constexpr void emplace(size_type, Args...) noexcept { OL_UNREACHABLE(); }
constexpr void pop_from_back() noexcept { OL_UNREACHABLE(); };
constexpr void erase(size_type) noexcept { OL_UNREACHABLE(); }
constexpr void destroy_all() const noexcept {}
template <typename InputIt>
constexpr void destroy_range(InputIt, InputIt) const noexcept {}
};
template <typename T, std::size_t Capacity>
struct trivial_storage : public sv_storage_base<T, Capacity> {
using Base = sv_storage_base<T, Capacity>;
using typename Base::pointer;
using typename Base::const_pointer;
using typename Base::size_type;
using typename Base::const_reference;
constexpr pointer data() noexcept { return data_; }
constexpr const_pointer data() const noexcept { return data_; }
constexpr std::size_t size() const noexcept { return size_; }
constexpr void set_size(size_type new_size) noexcept { size_ = new_size; }
constexpr void insert(size_type index, const_reference value) noexcept
{
OL_MOVE_BACKWARD(data() + index, data() + size_, data() + size_ + 1);
++size_;
data_[index] = value;
}
template <typename... Args>
constexpr void emplace(size_type index, Args... args) noexcept
{
OL_MOVE_BACKWARD(data() + index, data() + size_, data() + ++size_);
data_[index] = T{std::forward<Args>(args)...};
}
template <typename... Args>
constexpr void emplace_back(Args&&... args) noexcept
{
data_[size_++] = T{std::forward<Args>(args)...};
}
template <typename Range>
constexpr void insert_range(size_type index, Range&& range) noexcept
{
size_type const range_size{static_cast<size_type>(
std::distance(std::begin(range), std::end(range)))};
pointer const move_first{data() + size_};
pointer const move_last{move_first + range_size};
OL_MOVE_BACKWARD(data() + index, move_first, move_last);
for(const auto& elem : range){
data_[index] = elem;
}
size_ += range_size;
}
template <typename Range>
constexpr void push_back_range(Range&& range) noexcept
{
size_type const range_size{static_cast<size_type>(
std::distance(std::begin(range), std::end(range)))};
pointer const push_first{data() + size_};
pointer const push_last{push_first + range_size};
pointer push_pos{push_first};
size_type push_idx{};
auto const range_begin{std::begin(range)};
for(; push_pos < push_last; push_pos++, push_idx++){
*push_pos = *(range_begin + push_idx);
}
size_ += range_size;
}
constexpr void pop_from_back() noexcept { --size_; }
constexpr void erase(size_type index) noexcept {
OL_MOVE(data() + index + 1, data() + size_--, data() + index);
}
constexpr void destroy_all() noexcept { size_ = 0; }
template <typename InputIt>
constexpr void destroy_range(InputIt first, InputIt last) noexcept { size_ -= (last - first); }
private:
T data_[Capacity]{};
size_type size_{};
};
template <typename T, std::size_t Capacity>
struct non_trivial_storage : public sv_storage_base<T, Capacity> {
using Base = sv_storage_base<T, Capacity>;
using typename Base::pointer;
using typename Base::const_pointer;
using typename Base::size_type;
using typename Base::const_reference;
pointer data() noexcept { return reinterpret_cast<pointer>(data_); }
const_pointer data() const noexcept { return reinterpret_cast<const_pointer>(data_); }
constexpr std::size_t size() const noexcept { return size_; }
constexpr void set_size(size_type new_size) noexcept { size_ = new_size; }
void insert(size_type index, const_reference value) noexcept
{
OL_CONSTRUCT_AT(data() + size_, OL_MOVE(*(data() + size_ - 1)));
OL_MOVE_BACKWARD(data() + index, data() + size_ - 1, data() + size_++);
*(data() + index) = value;
}
template <typename... Args>
void emplace(size_type index, Args... args) noexcept
{
OL_CONSTRUCT_AT(data() + size_, std::forward<Args>(args)...);
OL_MOVE_BACKWARD(data() + index, data() + size_ - 1, data() + size_++);
*(data() + index) = T{std::forward<Args>(args)...};
}
template <typename... Args>
void emplace_back(Args&&... args)
noexcept(noexcept(OL_CONSTRUCT_AT(data() + size(), std::forward<Args>(args)...)))
{
OL_CONSTRUCT_AT(data() + size_++, std::forward<Args>(args)...);
}
template <typename Range>
void insert_range(size_type index, Range&& range)
noexcept(noexcept(std::is_nothrow_move_constructible_v<T> && std::is_nothrow_copy_assignable_v<T>))
{
size_type const range_size{static_cast<size_type>(
std::distance(std::begin(range), std::end(range)))};
pointer const move_first{data() + size_};
pointer const move_last{move_first + range_size};
for(pointer move_pos{move_first}; move_pos < move_last; move_pos++){
OL_CONSTRUCT_AT(move_pos, OL_MOVE(*(move_pos - 1)));
}
OL_MOVE_BACKWARD(data() + index, move_first, move_last);
for(const auto& elem : range){
*(data() + index) = elem;
}
size_ += range_size;
}
template <typename Range>
void push_back_range(Range&& range)
noexcept(noexcept(std::is_nothrow_copy_constructible_v<T>))
{
size_type const range_size{std::distance(std::begin(range), std::end(range))};
pointer const construct_first{data() + size_};
pointer const construct_last{construct_first + range_size};
pointer construct_pos{construct_first};
size_type construct_idx{};
auto const range_begin{std::begin(range)};
for(; construct_pos < construct_last; construct_pos++, construct_idx++){
OL_CONSTRUCT_AT(construct_pos, *(range_begin + construct_idx));
}
size_ += range_size;
}
void pop_from_back()
noexcept(std::is_nothrow_destructible_v<T>)
{ OL_DESTROY_AT(data() + --size_); }
void erase(size_type index) noexcept {
OL_MOVE(data() + index + 1, data() + size_, data() + index);
OL_DESTROY_AT(data() + --size_);
}
void destroy_all()
noexcept(std::is_nothrow_destructible_v<T>)
{ OL_DESTROY(data(), data() + size_); size_ = 0; }
template <typename InputIt>
void destroy_range(InputIt first, InputIt last)
noexcept(std::is_nothrow_destructible_v<T>)
{ OL_DESTROY(first, last); size_ -= (last - first); }
private:
alignas(alignof(T)) unsigned char data_[sizeof(T[Capacity])]{};
size_type size_{};
};
template <typename T, std::size_t Capacity>
using sv_storage_type = std::conditional_t<
Capacity == 0,
zero_capcity_storage<T>,
std::conditional_t<std::is_trivial_v<T>,
trivial_storage<T, Capacity>,
non_trivial_storage<T, Capacity>>>;
} //end ns internal
template<typename T, std::size_t Capacity>
class static_vector : private internal::sv_storage_type<T, Capacity> {
public:
using Base = internal::sv_storage_type<T, Capacity>;
using typename Base::value_type;
using typename Base::size_type;
using typename Base::reference;
using typename Base::const_reference;
using iterator = typename Base::pointer;
using const_iterator = typename Base::const_pointer;
constexpr static_vector() noexcept = default;
constexpr static_vector(static_vector const& other)
{
Base::set_size(other.size());
ol::internal::uninitialized_copy(other.begin(), other.end(), begin());
}
constexpr static_vector(static_vector&& other)
{
Base::set_size(other.size());
ol::internal::uninitialized_move(other.begin(), other.end(), begin());
other.clear();
}
constexpr static_vector& operator=(const static_vector& other) {
if (this != &other) {
clear();
Base::set_size(other.size());
ol::internal::uninitialized_copy(other.begin(), other.end(), begin());
}
return *this;
}
constexpr static_vector& operator=(static_vector&& other) {
if (this != &other) {
clear();
ol::internal::uninitialized_move(other.begin(), other.end(), begin());
Base::set_size(other.size());
other.clear();
}
return *this;
}
constexpr ~static_vector() noexcept(noexcept(clear())) {
clear();
}
template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, T>>>
constexpr static_vector(std::initializer_list<U> list)
noexcept(noexcept(Base::push_back_range(list)))
{
if(list.size() >= max_size()){
OL_THROW(std::length_error, "static_vector::initializer list ctor: size exceeds capacity");
}
Base::push_back_range(list);
}
constexpr iterator begin() noexcept {
return Base::data();
}
constexpr const_iterator begin() const noexcept {
return Base::data();
}
constexpr const_iterator cbegin() const noexcept {
return begin();
}
constexpr iterator end() noexcept {
return begin() + size();
}
constexpr const_iterator end() const noexcept {
return begin() + size();
}
constexpr const_iterator cend() const noexcept {
return end();
}
template <typename U, typename = std::enable_if_t<std::is_constructible_v<T, U>>>
OL_CPP20_CONSTEXPR void push_back(const U& value)
noexcept(OL_NO_EXCEPTIONS && std::is_nothrow_constructible_v<T>)
{
if (size() >= capacity()) {
OL_THROW(std::length_error, "static_vector::push_back: size exceeds capacity");
}
Base::emplace_back(value);
}
template <typename U, typename = std::enable_if_t<std::is_constructible_v<T, U>>>
OL_CPP20_CONSTEXPR void push_back(U&& value)
noexcept(OL_NO_EXCEPTIONS && std::is_nothrow_move_constructible_v<T>)
{
if (size() >= capacity()) {
OL_THROW(std::length_error, "static_vector::push_back: size exceeds capacity");
}
Base::emplace_back(std::move(value));
}
OL_CPP20_CONSTEXPR void pop_back()
noexcept(OL_NO_EXCEPTIONS)
{
if (empty()) {
OL_THROW(std::length_error, "static_vector::pop_back: cannot remove from an empty container");
}
Base::pop_from_back();
}
template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args...>>>
OL_CPP20_CONSTEXPR reference emplace_back(Args&&... args)
noexcept(OL_NO_EXCEPTIONS && std::is_nothrow_constructible_v<T>)
{
if (size() >= capacity()) {
OL_THROW(std::length_error, "static_vector::emplace_back: size exceeds capacity");
}
Base::emplace_back(std::forward<Args>(args)...);
return *(end() - 1);
}
template <typename = std::enable_if_t<std::is_copy_constructible_v<T>>>
OL_CPP20_CONSTEXPR iterator insert(const_iterator pos, const_reference value)
noexcept(OL_NO_EXCEPTIONS && std::is_nothrow_copy_constructible_v<T>)
{
size_type const idx = static_cast<size_type>(pos - cbegin());
if (idx > size() || size() >= capacity()) {
OL_THROW(std::length_error, "static_vector::insert: size exceeds capacity");
}
Base::insert(idx, value);
return begin() + idx;
}
template <typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args...>>>
OL_CPP20_CONSTEXPR iterator emplace(const_iterator pos, Args... args)
noexcept(OL_NO_EXCEPTIONS && std::is_nothrow_move_constructible_v<T>)
{
size_type const idx = static_cast<size_type>(pos - cbegin());
if (idx > size() || size() >= capacity()) {
OL_THROW(std::length_error, "static_vector::insert: size exceeds capacity");
}
Base::emplace(idx, std::forward<Args>(args)...);
return begin() + idx;
}
OL_CPP20_CONSTEXPR iterator erase(const_iterator pos)
noexcept(std::is_nothrow_destructible_v<T>)
{
size_type const idx = static_cast<size_type>(pos - cbegin());
if (idx >= size()) {
OL_THROW(std::range_error, "static_vector::erase: index out of range");
}
Base::erase(idx);
return begin() + idx;
}
constexpr void clear() noexcept(std::is_nothrow_destructible_v<T>) {
Base::destroy_all();
}
constexpr std::size_t size() const noexcept {
return Base::size();
}
static constexpr std::size_t capacity() noexcept {
return Base::capacity();
}
static constexpr std::size_t max_size() noexcept {
return Base::max_size();
}
constexpr bool empty() const noexcept {
return size() == 0;
}
OL_CPP20_CONSTEXPR reference at(size_type index) noexcept(OL_NO_EXCEPTIONS) {
if (index >= size()) {
OL_THROW(std::out_of_range, "Index out of range");
}
return begin()[index];
}
OL_CPP20_CONSTEXPR const_reference at(size_type index) const noexcept(OL_NO_EXCEPTIONS) {
if (index >= size()) {
OL_THROW(std::out_of_range, "Index out of range");
}
return begin()[index];
}
OL_CPP20_CONSTEXPR reference operator[](size_type index) noexcept {
OL_ASSERT(index < size());
return begin()[index];
}
OL_CPP20_CONSTEXPR const_reference operator[](size_type index) const noexcept {
OL_ASSERT(index < size());
return begin()[index];
}
constexpr reference front() noexcept {
return *begin();
}
constexpr const_reference front() const noexcept{
return *begin();
}
OL_CPP20_CONSTEXPR reference back() noexcept{
OL_ASSERT(not empty());
return *(end() - 1);
}
OL_CPP20_CONSTEXPR const_reference back() const noexcept{
OL_ASSERT(not empty());
return *(end() - 1);
}
}; //end struct static_vector
} //end ns ol
#undef OL_CPP_VERSION_NEWER_THAN
#undef OL_CPP_VERSION_OLDER_THAN
#undef OL_UNREACHABLE
#ifdef OL_NO_EXCEPTIONS
#undef OL_NO_EXCEPTIONS
#endif
#ifdef OL_CPP20_CONSTEXPR
#undef OL_NO_EXCEPTIONS
#endif
#undef OL_GCC10_CONSTEXPR
#undef OL_MOVE
#undef OL_MOVE_BACKWARD
#undef OL_CONSTRUCT_AT
#undef OL_DESTROY_AT
#undef OL_DESTROY
#undef OL_THROW
#undef OL_ASSERT
#endif /* OL_STATIC_VECTOR_HPP_ */