SmallVector - std::vector like container on the stack

Question

SmallVector is almost same as std::vector except it keeps its data inside a large array. Similar to std::array, its size can not get bigger than the SIZE parameter. However, unlike std::array it may hold less than SIZE elements.

I try to made it constexpr, but it is not really possible, because push_back need to throw an exception in case of memory allocation failure. I was able to make to make "empty" SmallVector, but it is not useful at all.

I skipped some functionality as well.

#include <algorithm> // std::equal
#include <stdexcept> // std::out_of_range
#include <type_traits> // std::is_trivially_destructible
#include <initializer_list>
#include <cstdio> // size_t, printf
//
// Based on
// http://codereview.stackexchange.com/questions/123402/c-vector-the-basics
// http://lokiastari.com/posts/Vector-SimpleOptimizations
//
template<typename T, size_t SIZE>
class SmallVector{
private:
 static constexpr bool DEBUG_ = true;
public:
 // TYPES
 using value_type = T;
 using size_type = size_t;
 using iterator = value_type *;
 using const_iterator = const value_type *;
private:
 size_type length = 0;
 char arena[ SIZE * sizeof(value_type) ];
public:
 // STANDARD C-TORS
 SmallVector() = default;
 SmallVector(const SmallVector &other){
 appendCopy(std::begin(other), std::end(other));
 log__("Copy C-Tor");
 }
 SmallVector(SmallVector &&other){
 appendMove(std::begin(other), std::end(other));
 other.length = 0;
 log__("Move C-Tor");
 }
 SmallVector &operator=(const SmallVector &other){
 clear();
 appendCopy(std::begin(other), std::end(other));
 log__("Copy Assign");
 return *this;
 }
 SmallVector &operator=(SmallVector &&other){
 clear();
 appendMove(std::begin(other), std::end(other));
 other.length = 0;
 log__("Move Assign");
 return *this;
 }
 // OTHER C-TORS
 template<class IT>
 SmallVector(IT begin, IT end){
 appendCopy(begin, end);
 log__("Iterator C-Tor");
 }
 SmallVector(const std::initializer_list<T> & list) :
 SmallVector(std::begin(list), std::end(list)){
 log__("Initializer C-Tor");
 }
 // D-TOR
 ~SmallVector(){
 destructAll_<value_type>(cbegin(), cend());
 }
 // MUTATIONS
 void clear(){
 destructAll_<value_type>(cbegin(), cend());
 length = 0;
 }
 void push_back(const value_type &value){
 placeBack_(value);
 }
 void push_back(value_type &&value){
 placeBack_(std::move(value));
 }
 template<typename... Args>
 void emplace_back(Args&&... args){
 placeBack_(std::forward<Args>(args)...);
 }
 void pop_back() noexcept{
 // see [1]
 --length;
 destruct_<value_type>( data_(length) );
 }
 // COMPARISSON
 template<typename CONTAINER>
 bool operator==(const CONTAINER &other) const noexcept{
 return equals_(other);
 }
 template<typename CONTAINER>
 bool operator!=(const CONTAINER &other) const noexcept{
 return ! equals_(other);
 }
 // ITERATORS
 iterator begin() noexcept{
 return data_();
 }
 iterator end() noexcept{
 return data_() + length;
 }
 // CONST ITERATORS
 const_iterator begin() const noexcept{
 return data_();
 }
 const_iterator end() const noexcept{
 return data_() + length;
 }
 // C++11 CONST ITERATORS
 const_iterator cbegin() const noexcept{
 return begin();
 }
 const_iterator cend() const noexcept{
 return end();
 }
 // SIZE
 constexpr size_type size() const noexcept{
 return length;
 }
 constexpr bool empty() const noexcept{
 return size() == 0;
 }
 // MORE SIZE
 static void reserve(size_type const){
 // left for compatibility
 }
 constexpr static size_type capacity(){
 return SIZE;
 }
 constexpr static size_type max_size(){
 return SIZE;
 }
 // DATA
 value_type *data() noexcept{
 return data_();
 }
 const value_type *data() const noexcept{
 return data_();
 }
 // ACCESS WITH RANGE CHECK
 value_type &at(size_type const index){
 validateIndex_(index);
 return data_(index);
 }
 const value_type &at(size_type const index) const{
 validateIndex_(index);
 return data_(index);
 }
 // ACCESS WITHOUT RANGE CHECK
 value_type &operator[](size_type const index) noexcept{
 // see [1] behavior is undefined
 return data_(index);
 }
 const value_type &operator[](size_type const index) const noexcept{
 // see [1] behavior is undefined
 return data_(index);
 }
 // FRONT
 value_type &front() noexcept{
 // see [1] behavior is undefined
 return data_(0);
 }
 const value_type &front() const noexcept{
 // see [1] behavior is undefined
 return data_(0);
 }
 // BACK
 value_type &back() noexcept{
 // see [1] behavior is undefined
 return data_(length - 1);
 }
 const value_type &back() const noexcept{
 // see [1] behavior is undefined
 return data_(length - 1);
 }
public:
 // NON STANDARD APPEND
 template<class IT>
 void appendCopy(IT begin, IT end){
 for(auto it = begin; it != end; ++it)
 push_back(*it);
 }
 template<class IT>
 void appendMove(IT begin, IT end){
 for(auto it = begin; it != end; ++it)
 push_back(std::move(*it));
 }
private:
 template<typename... Args>
 void placeBack_(Args&&... args){
 if (length >= SIZE){
 std::bad_alloc exception;
 throw exception;
 }
 void *placement = data_() + length;
 new(placement) value_type(std::forward<Args>(args)...);
 ++length;
 }
 template<typename CONTAINER>
 bool equals_(const CONTAINER &other) const noexcept{
 return length == other.length
 ? std::equal(begin(), end(), other.begin())
 : false;
 }
 void validateIndex_(size_type const index) const{
 if (index >= length){
 std::out_of_range exception("Out of Range");
 throw exception;
 }
 }
private:
 // LOW LEVEL DATA ACCESS
 T *data_() noexcept{
 return reinterpret_cast<T *>(arena);
 }
 const T *data_() const noexcept{
 return reinterpret_cast<const T *>(const_cast<char *>(arena));
 }
 T &data_(size_type const index) noexcept{
 return data_() [index];
 }
 const T &data_(size_type const index) const noexcept{
 return data_() [index];
 }
private:
 // TRIVIAL DESTRUCTOR
 template<typename X>
 typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
 static destruct_(const T &){
 // Trivially destructible objects can be re-used without using the destructor.
 }
 template<typename X, class IT>
 typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
 static destructAll_(const IT, const IT){
 // Trivially destructible objects can be re-used without using the destructor.
 }
 // NORMAL DESTRUCTOR
 template<typename X>
 typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
 static destruct_(const T &t){
 t.~T();
 }
 template<typename X, class IT>
 typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
 static destructAll_(IT begin, IT end){
 for(auto it = begin; it != end; ++it)
 destruct_<value_type>(*it);
 }
private:
 void log__(const char *msg) const noexcept{
 if (DEBUG_)
 printf("%-20s size: %5zu\n", msg, length);
 }
 void swap(SmallVector& other) noexcept{
 using std::swap;
 swap(length, other.length );
 swap(arena, other.arena );
 }
 // Remark [1]
 //
 // If the container is not empty,
 // the function never throws exceptions (no-throw guarantee).
 // Otherwise, it causes undefined behavior.
};

Answer 1

Unaligned memory

Your storage is aligned for char, which will lead to performance issues in most architectures and in others it just won't work (crash).

Replace:

char arena[SIZE * sizeof(value_type)];

With:

std::aligned_storage_t<SIZE * sizeof(value_type), alignof(value_type)> arena;

Some implementations (such as VC++) of std::aligned_storage_t<> will ignore the specified alignment template argument if it greater than alignof(std::max_align_t) and default to said value.

If you want to support over-aligned types in a portable way, you should specify storage alignment manually:

alignas(alignof(value_type)) char arena[SIZE * sizeof(value_type)];

• Nick: thanks. seems like here are an example with vector similar to mine: en.cppreference.com/w/cpp/types/aligned_storage

Answer 2

Consider Using Non-Portable Extensions

Many operating systems and compilers provide an extension such as alloca, _alloca or _malloca to allocate aligned memory on the stack. You can now reserve memory and set its size dynamically when it is created. This could even be used to let the vector grow. It also allows constant-time move.

There are a few disadvantages to doing so, if you don’t intend to use these purely locally. You can no longer return a SmallVector, and a SmallVector& that you pass to another function might be invalidated if its memory got moved.

If Not, Use Existing Classes

This class does add a little bit on top of a std::array, namely the ability to grow up to a maximum size. In most real-world applications, though, you can declare a std::array and then take a std::span within that array of the subrange you want. That gets you the interface of a sized view of the valid elements, which is what you want here. For those applications where you want to push_back and pop_back and that would not work better as loops, algorithms or ranges, you can use *++top and --top on an iterator.

If you’re just doing this as a learning exercise, nice work, but one lesson to reflect on is whether this was actually useful.

Fix Your Copy and Move Assignment

Although you have a swap member function that swaps the size and arena instead of doing a member-wise copy, you don’t use swap for the move assignment or copy-and-swap for the copy assign. This creates a bug in copy assignment: self-assignment wipes the contents of the object before copying the empty vector.

Since you use iterator algorithms for most other functions, it would be consistent (and good practice) to use std::copy for appendCopy and appendMove (whose names are confusing).