1
\$\begingroup\$

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.

};
\$\endgroup\$
2
\$\begingroup\$

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)];
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.