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/blog/2016/03/19/vector-simple-optimizations/
//

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)];