How to handle object destruction in a custom container?

user_782181 0
Viewed 83

I'm writing a custom Stack container that stores its elements in a fixed-size array:

template<typename T, uint32 TCapacity>
class Stack {
    // Member functions omitted
    T mData[TCapacity];
    uint32 mSize;
};

When an element is popped off the stack, I can just decrement the size. However, I think that if the item is popped off the stack, you'd also expect the destructor to be called on the object.

So, I could manually call the destructor on the object when popping, like so:

void Pop() { 
    assert(mSize > 0);
    mSize--;
    mData[mSize].~T();
}

However, when the Stack object itself is destructed, doesn't that cause the destructor to be called again for each object in mData, which could effectively "double destruct" certain elements? It might not be safe to double destruct all types, so this doesn't seem like a good idea.

I guess one alternative approach would be to construct a new object to overwrite the previous object, but that seems kind of inefficient potentially:

void Pop() { 
    assert(mSize > 0);
    mSize--;
    mData[mSize] = T();
}

The only other thing I can think of is to have the data array just be an array of bytes (unsigned char) and then deal with the extra complexity of constructing/destructing objects inside that raw memory. Which doesn't seem ideal, but maybe it's the true solution?

Does anyone have insight into a good way to deal with this? I imagine that a built-in container like std::vector also has to deal with this problem (though of course the data memory is allocated from the heap in that case).

memory stack destructor c++
1 Answers

As noted in the comments, the key is to not have an array of type T. You want an array of something like optional<T>, i.e. a type which can hold a T or hold nothing. But in this case, the container knows which items are populated, so the optional<T>'s internal knowledge of whether it holds a T is unnecessary.

For example, the following optional-like type should work:

template <typename T>
union storage
{
    char no_value_ = {};
    T value_;

    constexpr void assign(T&& obj)
        noexcept(std::is_nothrow_move_constructible_v<T>)
    {
        this->value_ = std::move(obj);
    }

    constexpr void assign(const T& obj)
        noexcept(std::is_nothrow_copy_constructible_v<T>)
    {
        this->value_ = obj;
    }

    constexpr void reset() noexcept
    {
        this->value_.T::~T();
        this->no_value_ = {};
    }
};

But this type itself is difficult to use, because it doesn't know whether it holds a value.

So, when you use it in a container, you must be particularly careful:

template <typename T, std::size_t Capacity>
class stack
{
public:
    constexpr stack() noexcept = default;

    constexpr stack(const stack& other) noexcept
        requires std::is_copy_constructible_v<storage<T>>
        = default;

    constexpr stack(const stack& other)
        noexcept(std::is_nothrow_copy_constructible_v<T>)
        : size_{other.size_}
    {
        for (std::size_t i = 0; i < size_; ++i)
            data_[i].assign(other.data_[i].value_);
    }

    constexpr stack(stack&& other) noexcept
        requires std::is_move_constructible_v<storage<T>>
        = default;

    constexpr stack(stack&& other)
        noexcept(std::is_nothrow_move_constructible_v<T>)
        : size_{std::exchange(other.size_, 0)}
    {
        for (std::size_t i = 0; i < size_; ++i)
        {
            data_[i].assign(std::move(other.data_[i].value_));
            other.data_[i].reset();
        }
    }

    constexpr ~stack()
        requires std::is_destructible_v<storage<T>>
        = default;

    constexpr ~stack()
    {
        for (std::size_t i = 0; i < size_; ++i)
            data_[i].reset();
    }

    constexpr void push(T&& obj)
        noexcept(std::is_nothrow_move_constructible_v<T>)
    {
        assert(size_ < Capacity);
        data_[size_++].assign(std::move(obj));
    }
    constexpr void push(const T& obj)
        noexcept(std::is_nothrow_copy_constructible_v<T>)
    {
        assert(size_ < Capacity);
        data_[size_++].assign(obj);
    }

    constexpr T& top() noexcept
    {
        assert(size_ > 0);
        return data_[size_-1].value_;
    }

    constexpr const T& top() const noexcept
    {
        assert(size_ > 0);
        return data_[size_-1].value_;
    }

    constexpr void pop()
    {
        assert(size_ > 0);
        data_[size_--].reset();
    }

private:
    std::size_t size_ = 0;
    storage<T> data_[Capacity];
};

See a full example.

user_32421460
Related