Constant-sized vector

Question

Does someone know the way to define constant-sized vector?

For example, instead of defining

std::vector<int>

it will be

std::vector<10, int>

It should be completely cross-platformed. Maybe an open source class?

Answer 1

Jason Turner shares simple_stack_vector on his github

I modified ::resize () method as it was causing some issue:

constexpr void resize ( const size_type new_size )
{
    if ( new_size <= size_ )
    {
        size_ = new_size;
    }
    else
    {
        if ( new_size > Capacity )
        {
            // throw std::length_error("resize would exceed static capacity");
        }
        else
        {
            size_ = new_size;
        }
    }
}

And the original code

https://github.com/lefticus/tools/blob/main/include/lefticus/tools/simple_stack_vector.hpp

#ifndef LEFTICUS_TOOLS_SIMPLE_STACK_VECTOR_HPP
#define LEFTICUS_TOOLS_SIMPLE_STACK_VECTOR_HPP

#include <array>
#include <cstdint>
#include <stdexcept>
#include <vector>

namespace lefticus::tools {


// changes from std::vector
//  * capacity if fixed at compile-time
//  * it never allocates
//  * items must be default constructible
//  * items are never destroyed until the entire stack_vector
//    is destroyed.
//  * iterators are never invalidated
//  * capacity() and max_size() are now static functions
//  * should be fully C++17 usable within constexpr
template<typename Contained, std::size_t Capacity> struct simple_stack_vector
{
  using value_type = Contained;
  using data_type = std::array<value_type, Capacity>;
  using size_type = typename data_type::size_type;
  using difference_type = typename data_type::difference_type;
  using reference = value_type &;
  using const_reference = const value_type &;

  static_assert(std::is_default_constructible_v<Contained>);

  using iterator = typename data_type::iterator;
  using const_iterator = typename data_type::const_iterator;
  using reverse_iterator = typename data_type::reverse_iterator;
  using const_reverse_iterator = typename data_type::const_reverse_iterator;

  constexpr simple_stack_vector() = default;
  constexpr explicit simple_stack_vector(std::initializer_list<value_type> values)
  {
    for (const auto &value : values) { push_back(value); }
  }

  template<typename OtherContained, std::size_t OtherSize>
  constexpr explicit simple_stack_vector(const simple_stack_vector<OtherContained, OtherSize> &other)
  {
    for (const auto &value : other) { push_back(Contained{ value }); }
  }

  template<typename Type> constexpr explicit simple_stack_vector(const std::vector<Type> &values)
  {
    for (const auto &value : values) { push_back(Contained{ value }); }
  }

  template<typename Itr> constexpr simple_stack_vector(Itr begin, Itr end)
  {
    while (begin != end) {
      push_back(*begin);
      ++begin;
    }
  }

  [[nodiscard]] constexpr iterator begin() noexcept { return data_.begin(); }

  [[nodiscard]] constexpr const_iterator begin() const noexcept { return data_.cbegin(); }
  [[nodiscard]] constexpr const_iterator cbegin() const noexcept { return data_.cbegin(); }

  [[nodiscard]] constexpr iterator end() noexcept
  {
    return std::next(data_.begin(), static_cast<difference_type>(size_));
  }

  [[nodiscard]] constexpr const_iterator end() const noexcept
  {
    return std::next(data_.cbegin(), static_cast<difference_type>(size_));
  }

  [[nodiscard]] constexpr value_type &front() noexcept { return data_.front(); }
  [[nodiscard]] constexpr const value_type &front() const noexcept { return data_.front(); }
  [[nodiscard]] constexpr value_type &back() noexcept { return data_.back(); }
  [[nodiscard]] constexpr const value_type &back() const noexcept { return data_.back(); }

  [[nodiscard]] constexpr const_iterator cend() const noexcept { return end(); }

  [[nodiscard]] constexpr reverse_iterator rbegin() noexcept
  {
    return std::next(data_.rbegin(), static_cast<difference_type>(Capacity - size_));
  }

  [[nodiscard]] constexpr const_reverse_iterator rbegin() const noexcept
  {
    return std::next(data_.crbegin(), static_cast<difference_type>(Capacity - size_));
  }
  [[nodiscard]] constexpr const_reverse_iterator crbegin() const noexcept { return rbegin(); }

  [[nodiscard]] constexpr bool empty() const noexcept { return size_ == 0; }

  [[nodiscard]] constexpr reverse_iterator rend() noexcept { return data_.rend(); }

  [[nodiscard]] constexpr const_reverse_iterator rend() const noexcept { return data_.crend(); }

  [[nodiscard]] constexpr const_reverse_iterator crend() const noexcept { return data_.crend(); }

  template<typename Value> constexpr value_type &push_back(Value &&value)
  {
    if (size_ == Capacity) { throw std::length_error("push_back would exceed static capacity"); }
    data_[size_] = std::forward<Value>(value);
    return data_[size_++];
  }

  template<typename... Param> constexpr value_type &emplace_back(Param &&...param)
  {
    if (size_ == Capacity) { throw std::length_error("emplace_back would exceed static capacity"); }
    data_[size_] = value_type{ std::forward<Param>(param)... };
    return data_[size_++];
  }

  [[nodiscard]] constexpr value_type &operator[](const std::size_t idx) noexcept { return data_[idx]; }

  [[nodiscard]] constexpr const value_type &operator[](const std::size_t idx) const noexcept { return data_[idx]; }

  [[nodiscard]] constexpr value_type &at(const std::size_t idx)
  {
    if (idx > size_) { throw std::out_of_range("index past end of stack_vector"); }
    return data_[idx];
  }

  [[nodiscard]] constexpr const value_type &at(const std::size_t idx) const
  {
    if (idx > size_) { throw std::out_of_range("index past end of stack_vector"); }
    return data_[idx];
  }

  // resets the size to 0, but does not destroy any existing objects
  constexpr void clear() { size_ = 0; }


  // cppcheck-suppress functionStatic
  constexpr void reserve(size_type new_capacity)
  {
    if (new_capacity > Capacity) { throw std::length_error("new capacity would exceed max_size for stack_vector"); }
  }

  // cppcheck-suppress functionStatic
  [[nodiscard]] constexpr static size_type capacity() noexcept { return Capacity; }

  // cppcheck-suppress functionStatic
  [[nodiscard]] constexpr static size_type max_size() noexcept { return Capacity; }

  [[nodiscard]] constexpr size_type size() const noexcept { return size_; }


  constexpr void resize(const size_type new_size)
  {
    if (new_size <= size_) {
      size_ = new_size;
    } else {
      if (new_size > Capacity) {
        throw std::length_error("resize would exceed static capacity");
      } else {
        auto old_end = end();
        size_ = new_size;
        auto new_end = end();
        while (old_end != new_end) {
          *old_end = data_type{};
          ++old_end;
        }
      }
    }
  }

  constexpr void pop_back() noexcept { --size_; }

  // cppcheck-suppress functionStatic
  constexpr void shrink_to_fit() noexcept
  {
    // nothing to do here
  }


private:
  // default initializing to make it more C++17 friendly
  data_type data_{};
  size_type size_{};
};


template<typename Contained, std::size_t LHSSize, std::size_t RHSSize>
[[nodiscard]] constexpr bool operator==(const simple_stack_vector<Contained, LHSSize> &lhs,
  const simple_stack_vector<Contained, RHSSize> &rhs)
{
  if (lhs.size() == rhs.size()) {
    for (std::size_t idx = 0; idx < lhs.size(); ++idx) {
      if (lhs[idx] != rhs[idx]) { return false; }
    }
    return true;
  }

  return false;
}

}// namespace lefticus::tools


#endif

Answer 2

Since C++20 there's spans. Which've been introduced exactly to modify a view of a sequence container. Presume you got the value for number (EVEN AT RUNTIME). Then, after initializing some vector vec<T> with appropriate ctor (see your fave STD refs), you can use std::span named above as follows:

/*some initializing process  of vec<T> here...*/
std::span<T> fixedSizeVec{vec};
/*use of fixedSizeVec as alias of array variable*/

Subscript operators overloaded, and range-based for-loops are available of course, too, so you just use that fixed-sizeVector in the remainder of your code as alias for original vec, which behaves exectly as fixes-size array, since you can't trigger any object-adding/creating/deleting member function by std::span.

Answer 3

I had a reason to want this: someone else's code that used std::vector, plus not wanting to use dynamic allocation for this data. std::array didn't work for me. I used Allocator to do it.

Templated allocator:

template<class Tp>
struct FixedVectorAllocator
{
  typedef Tp value_type;
  int mCount;
  Tp *mData;
  FixedVectorAllocator() = delete;

  template<class T>
  FixedVectorAllocator (const FixedVectorAllocator<T>&) {}

  /* Constructor takes a count and a pre-existing buffer
  template<class T>
  FixedVectorAllocator (int count, T* buffer)
  {
    mCount = count;
    mData = buffer;
  };
 
  Tp* allocate(std::size_t n)
  {
    if (n == mCount)
      {
        Tp* p = mData;
      std::cout << "allocating " << n << " records @ " << p << " from Buffer!\n";
        return mData;
      }
    else
      {
      return nullptr; /* If you trust your code never to call this */
      n *= sizeof(Tp);
      Tp* p = (Tp*) (::operator new(n));
      std::cout << "allocating " << n << " bytes @ " << p << '\n';
        return p;
      }
  }
 
  void deallocate(Tp* p, std::size_t n)
  {
    if (p == mData)
    {
      std::cout << "No deallocation here!\n";
    }
    else {
      std::cout << "deallocating " << n * sizeof *p << " bytes @ " << p << " " << mCount << "\n\n";
      ::operator delete(p);
    }
  }
};

/* Didn't pay any attention to these, never came up. */

    template<class T, class U>
    bool operator==(const FixedVectorAllocator<T>&, const FixedVectorAllocator<U>&) { return true; }
    template<class T, class U>
    bool operator!=(const FixedVectorAllocator<T>&, const FixedVectorAllocator<U>&) { return false; }

/* Define an array of data and an allocator using it:
int myIntegers[30];

static FixedVectorAllocator<int> integers(30,myIntegers);

/* Define the std::vector using the fixed vector */
  std::vector<int,FixedVectorAllocator<int>> myVector(30,integers);

/* Now, use the vector */
DoSomethingWithAVector (myVector);

This was helpful for me; the consuming code required a vector, and in the situation in which I was using it, the consuming code never tries to resize the vector.

My recollection is that reserve() which gets called during construction doesn't specify getting the exact number, but >=, but that in practice it's exact. I have test suites to notice if something changes, though I don't expect it to.

Pardon any typos above.

Answer 4

I found that std::vector actually has max_size() member and there is a customization point in the std library to tune vector behavior accordingly. So I just tuned std::vector to apply a cap on max_size() and narrow size_type. Compiles with c++11 and newer

• -Werror -Wextra
  • gcc >= 4.9.0
  • clang >= 3.3
• /W4 /WX /external:anglebrackets /external:W3
  • MSVC >= 19.20

Most of the code is meaningless boilerplate you can easily cut off if you don't need to support cross platform compilation and/or older versions of c++, the only real logic is inside of Allocator members. Use any allocator and vector types that are compatible with the standard and you can have a caped vector. using CapedVector = Caped<uint16_t>::Vector<char>; You can drop Vector and just use template <class T> using CapedVector = std::vector<T, Caped<uint16_t>::Allocator<std::allocator<T>>> if you don't need to narrow size_type

#include <algorithm>
#include <limits>
#include <memory>
#include <vector>
#include <type_traits>

#if __cpp_constexpr >= 201603L
// c++17
#define NODISCARD [[nodiscard]]
#else
#define NODISCARD
#endif

#if __cpp_constexpr > 200704L
// c++14
#define CONSTEXPR constexpr
#else
#define CONSTEXPR
#endif

#ifndef __cpp_concepts
template <class Size, Size maxSize = std::numeric_limits<Size>::max(), class = typename std::enable_if<std::is_unsigned<Size>::value>::type>
#elif defined CONSTEXPR
template <class Size, Size maxSize = std::numeric_limits<Size>::max(), class = std::enable_if_t<std::is_unsigned_v<Size>>>
#else
template <class Size, Size maxSize = std::numeric_limits<Size>::max()> requires(std::is_unsigned_v<Size>)
#endif
struct Caped
{
    using size_type = Size;
    template <class A>
    struct Allocator : A
    {
        using value_type = typename std::allocator_traits<A>::value_type;
        using pointer = typename std::allocator_traits<A>::pointer;
        using const_pointer = typename std::allocator_traits<A>::const_pointer;
        using void_pointer = typename std::allocator_traits<A>::void_pointer;
        using const_void_pointer = typename std::allocator_traits<A>::const_void_pointer;
        using difference_type = typename std::allocator_traits<A>::difference_type;
        using propagate_on_container_copy_assignment = typename std::allocator_traits<A>::propagate_on_container_copy_assignment;
        using propagate_on_container_move_assignment = typename std::allocator_traits<A>::propagate_on_container_move_assignment;
        using propagate_on_container_swap = typename std::allocator_traits<A>::propagate_on_container_swap;
#ifdef __cpp_lib_allocator_traits_is_always_equal
        using is_always_equal = typename std::allocator_traits<A>::is_always_equal;
#endif
        using A::A;

        using size_type = Caped::size_type;

        template <class U>
        struct rebind
        {
            using other = Allocator<typename std::allocator_traits<A>::template rebind_alloc<U>>;
        };
        CONSTEXPR size_type max_size() const noexcept
        {
            using BaseSize = typename std::allocator_traits<A>::size_type;
            static_assert(sizeof(BaseSize) >= sizeof(size_type), "allocator size_type must be bigger than cap type");
            return static_cast<size_type>(std::min<BaseSize>(maxSize, std::allocator_traits<A>::max_size(*this)));
        }
        NODISCARD CONSTEXPR pointer allocate(std::size_t n)
        {
            return n <= max_size() ? std::allocator_traits<A>::allocate(*this, n) : throw std::bad_array_new_length();
        }
#ifdef __cpp_lib_allocate_at_least
        NODISCARD constexpr pointer allocate_at_least(std::size_t n)
        {            
            return n <= max_size() ? std::allocator_traits<A>::allocate_at_least(*this, n) : throw std::bad_array_new_length();
        }
#endif
    };

    template<class T, template <class, class> class V = std::vector, class A = std::allocator<T>>
    struct Vector : V<T, Allocator<A>>
    {
        using Base = V<T, Allocator<A>>;
        using typename Base::value_type;
        using typename Base::allocator_type;
        using typename Base::difference_type;
        using typename Base::reference;
        using typename Base::const_reference;
        using typename Base::pointer;
        using typename Base::const_pointer;
        using typename Base::iterator;
        using typename Base::const_iterator;
        using typename Base::reverse_iterator;
        using typename Base::const_reverse_iterator;
        using Base::Base;
        using Base::assign;
        using Base::insert;

        using size_type = typename allocator_type::size_type;

        CONSTEXPR Vector(size_type count, const T& value, const allocator_type& alloc = allocator_type()) : Base(count, value, alloc){}
#if _MSVC_LANG <= 201402L
        CONSTEXPR explicit Vector(size_type count) : Base(count) {};
        CONSTEXPR explicit Vector(size_type count, const allocator_type& alloc) : Base(count, alloc){}
#else
        CONSTEXPR explicit Vector(size_type count, const allocator_type& alloc = allocator_type()) : V(count, alloc){}
#endif
        CONSTEXPR void assign(size_type count, const T& value) { Base::assign(count, value); }
        CONSTEXPR reference at(size_type pos) { return Base::at(pos); }
        CONSTEXPR const_reference at(size_type pos) const { return Base::at(pos); }
        CONSTEXPR reference operator[](size_type pos) { return Base::operator [](pos); };
        CONSTEXPR const_reference operator[](size_type pos) const { return Base::operator [](pos); };
        CONSTEXPR size_type size() const noexcept { return static_cast<size_type>(Base::size()); }
        CONSTEXPR size_type max_size() const noexcept { return static_cast<size_type>(Base::max_size()); }
        CONSTEXPR size_type capacity() const noexcept { return static_cast<size_type>(Base::capacity()); }
        CONSTEXPR iterator insert(const_iterator pos, size_type count, const T& value) { return Base::insert(pos, count, value); };
        CONSTEXPR void resize(size_type count) { Base::resize(count); };
        CONSTEXPR void resize(size_type count, const value_type& value) { Base::resize(count, value); };
    };
};

godbolt snippet

Answer 5

Improving the answer from Pari
I have been using the following class for many years in number crunching applications:

inline void nodeleter(void*) {}

/// Array of T with ownership. Like \see std::unique_ptr<T[]> but with size tracking.
/// @tparam T Element type.
template <typename T>
class unique_array : public std::unique_ptr<T[],void (*)(void*)>
{   size_t Size;
private:
    typedef std::unique_ptr<T[],void (*)(void*)> base;
protected:
    unique_array(T* ptr, size_t size, void (*deleter)(void*)) noexcept : base(ptr, deleter), Size(size) {}
    void reset(T* ptr, size_t size) noexcept { base::reset(ptr); Size = size; }
public:
    constexpr unique_array() noexcept : base(nullptr, operator delete[]), Size(0) {}
    explicit unique_array(size_t size) : base(new T[size], operator delete[]), Size(size) {}
    template <size_t N> unique_array(T(&arr)[N]) : base(arr, &nodeleter), Size(N) {}
    unique_array(unique_array<T>&& r) : base(move(r)), Size(r.Size) { r.Size = 0; }
    void reset(size_t size = 0) { base::reset(size ? new T[size] : nullptr); Size = size; }
    void swap(unique_array<T>&& other) noexcept { base::swap(other); std::swap(Size, other.Size); }
    void assign(const unique_array<T>& r) const { assert(Size == r.Size); std::copy(r.begin(), r.end(), begin()); }
    const unique_array<T>& operator =(const unique_array<T>& r) const { assign(r); return *this; }
    size_t size() const noexcept { return Size; }
    T* begin() const noexcept { return base::get(); }
    T* end() const noexcept { return begin() + Size; }
    T& operator[](size_t i) const { assert(i < Size); return base::operator[](i); }
    unique_array<T> slice(size_t start, size_t count) const noexcept
    {   assert(start + count <= Size); return unique_array<T>(begin() + start, count, &nodeleter); }
};

• Assignment is possible but this must not change the size (although it would be easy to implement).
• You may change the size by calling reset, but as the name suggests this discards any data.
• Move semantics are supported.
• const instances do not make their content const. Only the storage cannot be changed.
• It has also limited support for slices not owned by the instance. But they have not lifetime management. You need to care about dangling references yourself.
• There are some features missing to be fully compatible to the C++ Container requirement, first of all the typedefs. I never needed them so far.
• It is easy to extend this type for numeric types and add further vector operations. But there is no straight forward automatism since at least std::is_arithmetic<std::complex<double>>::value is false.

Answer 6

This is an old question but if someone just needs constant-size indexed container with size defined at runtime, I like to use unique_ptr:

// c++14
auto constantContainer = std::make_unique<YourType []> ( size );

// c++11
std::unique_ptr<YourType[]> constantContainer {new YourType[ size ]};


// Access
constantContainer[ i ]

Answer 7

If you want a fixed compile-time specified size (ala std::array<T, N>), but you want to be able to populate the vector with varying numbers of elements between 0 and N, then a good option is eastl::fixed_vector.

std::vector:

The size of a std::vector is dynamic - it will allocate required storage dynamically, and you cannot limit the size and enforce an error.

You can however reserve a certain size, and then add elements up that size before it needs to allocate new storage.

vector.size() is initially 0, and increases as you add elementss

std::array:

The size of a std::array is a compile-time constant - it will allocate required storage statically, and you cannot change the size.

array.size() is always the size of the array, and is equal to array.max_size()

eastl::fixed_vector:

The size of an eastl::fixed_vector can be either static or dynamic.

It will allocate a certain number of elements initially, and then if you allow dynamic growth, will allocate dynamically if required.

For the purpose you originally asked for, you can disable growth (via bEnableOverflow in the template instantiation below)

fixed_vector.size() is initially 0, and increases as you add elements.

template<typename T, 
         size_t nodeCount, 
         bool bEnableOverflow = true, 
         typename OverflowAllocator = 
                      typename eastl::type_select<bEnableOverflow,
                                                  EASTLAllocatorType, 
                                                  EASTLDummyAllocatorType>::type>
class fixed_vector;

Simple example:

#include <iostream>
#include <vector>
#include <array>
#include "EASTL/fixed_vector.h"

int main()
{
    std::vector<int> v;
    v.reserve(10);
    std::cout << "size=" << v.size() << " capacity=" << v.capacity() << '\n';

    std::array<int, 10> a;
    std::cout << "size=" << a.size() << " capacity=" << a.max_size() << '\n';

    eastl::fixed_vector<int, 10, false> fv;
    std::cout << "size=" << fv.size() << " capacity=" << fv.capacity() << '\n';

    return 0;
}

Output:

size=0 capacity=10
size=10 capacity=10
size=0 capacity=10

Note that the size of array is 10, whereas vector and fixed_vector are 0

Answer 8

The std::vector can always grow dynamically, but there are two ways you can allocate an initial size:

This allocates initial size and fills the elements with zeroes:

std::vector<int> v(10);
v.size(); //returns 10

This allocates an initial size but does not populate the array with zeroes:

std::vector<int> v;
v.reserve(10);
v.size(); //returns 0

Answer 9

This ----> std::vector<10, int> is invalid and causes error. But the new C++ standard has introduced a new class; the std::array. You can declare an array like this:

std::array<int, 5> arr; // declares a new array that holds 5 ints
std::array<int, 5> arr2(arr); // arr2 is equal to arr
std::array<int, 5> arr3 = {1, 2, 3, 4, 5}; // arr3 holds 1, 2, 3, 4, 5

The std::array has constant size and supports iterator/const_iterator/reverse_iterator/const_reverse_iterator. You can find more about this class at http://cplusplus.com/reference/stl/array/.

Answer 10

There is no way to define a constant size vector. If you know the size at compile time, you could use C++11's std::array aggregate.

#include <array>

std::array<int, 10> a;

If you don't have the relevant C++11 support, you could use the TR1 version:

#include <tr1/array>

std::tr1::array<int, 10> a;

or boost::array, as has been suggested in other answers.

Answer 11

Use std::array c++11

For better readability you can make typedef:

typedef std::array<int, 10> MyIntArray;

Answer 12

A std::vector is a dynamic container, there is no mechanism to restrict its growth. To allocate an initial size:

std::vector<int> v(10);

C++11 has a std::array that would be more appropriate:

std::array<int, 10> my_array;

If your compiler does not support C++11 consider using boost::array:

boost::array<int, 10> my_array;