6
\$\begingroup\$

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

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];
}
\$\endgroup\$
  • \$\begingroup\$ You can use something along the lines of union Buffer { T elem; char dummy; }; Buffer elems[N]; std::size_t count; to support constexpr non-POD types. \$\endgroup\$ – L. F. Oct 3 '19 at 6:54
  • \$\begingroup\$ I thought about support trivially destructible but those are still unclear to me. what i mean, suppose you have a class that extends another class probably with virtual methods, but without any destructor. it will be OK to be inserted into the vector as well. \$\endgroup\$ – Nick Oct 3 '19 at 7:50
  • \$\begingroup\$ by without any destructor I mean no d-tor at all, not even ~ = default; \$\endgroup\$ – Nick Oct 3 '19 at 7:51
  • \$\begingroup\$ How are destructors relevant? I suggested union because that’s the only way you can control lifetime at compile time. (Good news: since C++20 std::construct_* and std::destroy_* are allowed in constexpr contexts, so we can do it the normal way. ) \$\endgroup\$ – L. F. Oct 4 '19 at 23:54
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is there any reason why you would advise against making function parameters const. That is anithetical to const-correcteness and consequently a bad advise. \$\endgroup\$ – miscco Oct 5 '19 at 8:38
  • 1
    \$\begingroup\$ @miscco It doesn't matter to the caller for value types (it's a copy so the caller doesn't need to know). It makes the important consts harder to notice (reference types / pointer types). It can also be misleading, since C++ matches declarations with a const parameter with function definitions where the parameter isn't specified as const. \$\endgroup\$ – user673679 Oct 5 '19 at 9:59
  • \$\begingroup\$ @user673679 That it doesnt matter for the caller is a non argument. He does not care so there is no value here. The same with C++ ignoring const from function definitions. Its sad but why do something bad because the language does something else badly? Also there are no important parts of beeing correct. You either are or not. \$\endgroup\$ – miscco Oct 6 '19 at 18:37
  • 1
    \$\begingroup\$ Extra consts may make your code slightly safer, but you pass the burden on to the user, who has to read the function declaration. InputIt find(InputIt begin, const InputIt end, const T& value); - begin isn't const because we use it as a loop variable (an implementation detail), whereas end doesn't change. end being const is meaningless noise to the user of the function. Only the last const actually conveys useful information. Pointers are especially messy: std::size_t do_a_thing(char* const data, const std::size_t data_size) - it's easy to misread that first parameter. \$\endgroup\$ – user673679 Oct 6 '19 at 19:29
  • 1
    \$\begingroup\$ @miscco I also find user673679's mycopy(T* first, T* const last, const T* src) very explanatory \$\endgroup\$ – L. F. Oct 7 '19 at 4:42
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This container has dynamic size. std::array has static size. The fact that this container uses the stack and imposes an upper limit on the size does not matter. Keeping track of the actual number of elements is definitely useful. \$\endgroup\$ – L. F. Oct 5 '19 at 9:52
  • \$\begingroup\$ perfectly OK except is not constexpr until c++17 \$\endgroup\$ – Nick Oct 5 '19 at 20:52
1
\$\begingroup\$

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());
}
\$\endgroup\$
  • 1
    \$\begingroup\$ std::equal is not constexpr until C++20 \$\endgroup\$ – L. F. Oct 5 '19 at 10:39

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.