constexpr SmallVector - std::vector like container on the stack

Question

2 years ago I did this:

SmallVector - std::vector like container on the stack

now, 2 years later, I am reinventing the wheel again, this time with fully constexpr SmallVector.

This time, because I decided it will have only constexpr functions, I decided to remove all non POD types.

#ifndef MY_SMALL_VECTOR_H_
#define MY_SMALL_VECTOR_H_

#include <stdexcept>        // std::bad_alloc while push_back
#include <type_traits>      // std::is_trivial, std::is_standard_layout
#include <initializer_list>

//
// Based on
//  http://codereview.stackexchange.com/questions/123402/c-vector-the-basics
//  http://lokiastari.com/posts/Vector-SimpleOptimizations
//

template<typename T, std::size_t SIZE>
class SmallVector{
    static_assert(std::is_trivial<T>::value,        "T must be POD...");
    static_assert(std::is_standard_layout<T>::value,    "T must be POD...");

private:
    static constexpr std::size_t SIZEOF = sizeof(T);

    static constexpr bool DEBUG_ = true;

public:
    // TYPES

    using value_type    = T;
    using size_type     = std::size_t;

    using iterator      =       T*;
    using const_iterator    = const T*;

private:
    size_type   length  = 0;
    T       buffer[SIZE] = {};

public:
    // STANDARD C-TORS

    constexpr SmallVector() = default;

    template<class IT>
    constexpr SmallVector(IT begin, IT end){
        appendCopy(begin, end);
    }

    constexpr SmallVector(const std::initializer_list<T> & list) :
        SmallVector(list.begin(), list.end()){}


    // MISC

    constexpr
    void reserve(size_type const) const noexcept{
        // left for compatibility
    }

    constexpr
    void clear() noexcept{
        length = 0;
    }

    // COMPARISSON

    constexpr bool operator==(const SmallVector &other) const noexcept{
        if (length != other.length)
            return false;

        auto first = other.begin();
        auto last  = other.end();
        auto me    = begin();

        for(; first != last; ++first, ++me){
            if ( ! (*first == *me) )
                return false;
        }

        return true;
    }

    template<typename CONTAINER>
    constexpr bool operator!=(const CONTAINER &other) const noexcept{
        return ! operator==(other);
    }

    // ITERATORS

    constexpr
    iterator begin() noexcept{
        return buffer;
    }

    constexpr
    iterator end() noexcept{
        return buffer + length;
    }

    // CONST ITERATORS

    constexpr const_iterator begin() const noexcept{
        return buffer;
    }

    constexpr const_iterator end() const noexcept{
        return buffer + length;
    }

    // C++11 CONST ITERATORS

    constexpr const_iterator cbegin() const noexcept{
        return begin();
    }

    constexpr 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

    constexpr size_type capacity() const noexcept{
        return SIZE;
    }

    constexpr size_type max_size() const noexcept{
        return SIZE;
    }

    // DATA

    constexpr
    value_type *data() noexcept{
        return buffer;
    }

    constexpr const value_type *data() const noexcept{
        return buffer;
    }

    // ACCESS WITH RANGE CHECK

    constexpr
    value_type &at(size_type const index){
        validateIndex_(index);
        return buffer[index];
    }

    constexpr const value_type &at(size_type const index) const{
        validateIndex_(index);
        return buffer[index];
    }

    // ACCESS DIRECTLY

    constexpr
    value_type &operator[](size_type const index) noexcept{
        // see [1] behavior is undefined
        return buffer[index];
    }

    constexpr const value_type &operator[](size_type const index) const noexcept{
        // see [1] behavior is undefined
        return buffer[index];
    }

    // FRONT

    constexpr
    value_type &front() noexcept{
        // see [1] behavior is undefined
        return buffer[0];
    }

    constexpr const value_type &front() const noexcept{
        // see [1] behavior is undefined
        return buffer[0];
    }

    // BACK

    constexpr
    value_type &back() noexcept{
        // see [1] behavior is undefined
        return buffer[length - 1];
    }

    constexpr const value_type &back() const noexcept{
        // see [1] behavior is undefined
        return buffer[length - 1];
    }

    // MUTATIONS

    constexpr
    void push_back(const value_type &value){
        emplace_back(value);
    }

    constexpr
    void push_back(value_type &&value){
        emplace_back(std::move(value));
    }

    template<typename... Args>
    constexpr
    void emplace_back(Args&&... args){
        if (length == SIZE){
            throw std::bad_alloc{};
        }

        buffer[length++] = value_type(std::forward<Args>(args)...);
    }

    constexpr
    void pop_back() noexcept{
        // see [1]
        --length;
    }

public:
    // NON STANDARD APPEND

    template<class IT>
    constexpr
    void appendCopy(IT begin, IT end) {
        for(auto it = begin; it != end; ++it)
            push_back(*it);
    }

private:
    constexpr
    void validateIndex_(size_type const index) const{
        if (index >= length){
            throw std::out_of_range("Out of Range");
        }
    }

    // Remark [1]
    //
    // If the container is not empty,
    // the function never throws exceptions (no-throw guarantee).
    // Otherwise, it causes undefined behavior.

};

#endif

Here is small demo / test:

#include "smallvector.h"

using vectorPod = SmallVector<int, 5>;

namespace{

    constexpr auto test_constexpr2(){
        vectorPod v{};
        v.push_back(4);
        v.clear();
        v.emplace_back(5);
        v.push_back(54);
        int a = 9;
        v.push_back(a);

        vectorPod w{ 5, 54, 9 };

        if (v == w)
            v.at(0) = 7;

        auto x = v.begin();
        ++x;
        *x = 4;

        return v;
    }

} // namespace

int main(){
    constexpr auto v = test_constexpr2();

    return v[0];
}

Answer 1

Here's my suggestions:

Design

• Calling the constructors and destructors at the correct time with constexpr is indeed nontrivial, but disrespect object lifetime != POD. Your implementation is conceptually fine with some non-POD types. Maybe "trivial" is what you are looking for.

• You are missing a lot of functionality. Users may want to use them, so you shouldn't be omitting them. In particular:

  • Missing types: (const_)?(reference|pointer|reverse_iterator) and difference_type.

  • Missing constructors: (count), (count, value).

  • Missing functions: assign, c?r(begin|end), resize, emplace, insert, erase, swap.

  • Missing operators: <, <=, >, >=.

• Don't provide a feature for the sake of providing it. For example, capacity or reserve isn't applicable, so drop them.

• Many things can be noexcept.

• std::bad_alloc is for dynamic allocation failures. Don't abuse it for stack overflow.

• appendCopy should check the total size first instead of failing halfway done.

Code

• Sort the include directives in alphabetical order.

• Don't use ALL CAPS names for template parameters. Reserve them for macros.

• The SIZEOF and DEBUG_ variables are never used. Remove them.

• Don't use multiple public: and private: labels.

• In T buffer[SIZE] = {};, is there a special reason for copy-initialization from {}? If yes, state it in a comment. Otherwise, just remove the =.

• std::initializer_list should be taken by value, not const reference.

• The (first, last) constructor should be constrained.

• The comparison operators should be non-members.

• Don't make function parameters const.

• operator[], front, back shouldn't be noexcept even though it does not actually throw an exception in a well-defined way. noexcept should be used for functions that never fail.

Answer 2

Here is my unpopular opinion: This class has no reason to exist and you should use std::array instead which does what you need.

If you need it to be compatible with std:: vector for template meta programming, you can just add a thin wrapper on top or use SFINAE to call reserve only if it exists.

Answer 3

We can use the standard library for equality comparison:

#include <algorithm>

constexpr bool operator==(const SmallVector &other) const noexcept {
    return std::equal(begin(), end(), other.begin(), other.end());
}