Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ vector with fixed capacity after initialization

Tags:

c++

vector

I need a C++ container with the following requirements:

  • The container can store non-copyable AND non-movable objects in continuous memory. For std::vector the object has to be either copyable or movable.
  • The capacity of the container is known during the construction at run-time, and fixed until destruction. All the needed memory space is allocated during the construction. For boost::static_vector the capacity is known at compile time.
  • The size of the container can increase over time when emplace_back more element in the container, but should never exceeds capacity.
  • Since the object is not copyable or movable, reallocation is not allowed.

It appears that neither STL nor BOOST has the container type I need. I have also searched in this side extensively but did not find an answer. So I have implemented one.

#include <memory>

template<class T>
class FixedCapacityVector {
private:
    using StorageType = std::aligned_storage_t<sizeof(T), alignof(T)>;
    static_assert(sizeof(StorageType) == sizeof(T));
public:
    FixedCapacityVector(FixedCapacityVector const&) = delete;
    FixedCapacityVector& operator=(FixedCapacityVector const&) = delete;
    FixedCapacityVector(size_t capacity = 0):
        capacity_{ capacity },
        data_{ std::make_unique<StorageType[]>(capacity) }
    { }
    ~FixedCapacityVector()
    {
        for (size_t i = 0; i < size_; i++)
            reinterpret_cast<T&>(data_[i]).~T();
    }
    template<class... Args>
    T& emplace_back(Args&&... args) 
    {
        if (size_ == capacity_)
            throw std::bad_alloc{};
        new (&data_[size_]) T{ std::forward<Args>(args)... };
        return reinterpret_cast<T&>(data_[size_++]);
    }
    T& operator[](size_t i) 
    { return reinterpret_cast<T&>(data_[i]); }
    T const& operator[](size_t i) const 
    { return reinterpret_cast<T const&>(data_[i]); }
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    T* data() { return reinterpret_cast<T*>(data_.get()); }
    T const* data() const { return reinterpret_cast<T const*>(data_.get()); }
private:
    size_t const capacity_;
    std::unique_ptr<StorageType[]> const data_;
    size_t size_{ 0 };
};

My questions are:

  • Why would I do this by hand? I could not find a standard container. Or maybe I did not look at the right place? Or because what I am trying to do is not conventional?
  • Is the hand-written container correct implemented? How about the exception safety, memory safety, etc.?
like image 570
Tony Xiang Avatar asked Feb 15 '26 01:02

Tony Xiang


1 Answers

It probably does not answer the question completely but it seems like fixed_capacity_vector might be added into future C++ standard(s) according to the following paper:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0843r1.html

Introduction

This paper proposes a modernized version of boost::container::static_vector [1]. That is, a dynamically-resizable vector with compile-time fixed capacity and contiguous embedded storage in which the elements are stored within the vector object itself.

Its API closely resembles that of std::vector. It is a contiguous container with O(1) insertion and removal of elements at the end (non-amortized) and worst case O(size()) insertion and removal otherwise. Like std::vector, the elements are initialized on insertion and destroyed on removal. For trivial value_types, the vector is fully usable inside constexpr functions.

like image 164
dshvets1 Avatar answered Feb 16 '26 16:02

dshvets1



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!