std::vector free list

Question

I'm trying to implement a free list by using a std::vector as its growable buffer. The reason I made this instead of just adding/removing elements directly into a vector, is because I'd like the indices to remain valid after an item is removed. Please take a look at the code below. I think it works pretty well with my use cases and tests. However it requires the data type, which is stored in the buffer, to always have a default constructor. I'd appreciate any improvements/fixes to this code as well as any alternative ideas to do this.

#pragma once
#include <vector>
#include <stdint.h>
#include <assert.h>

using u32 = uint32_t;
constexpr u32 u32_invalid_id{ 0xffffffff };

template <typename T>
class free_list_vector
{
static_assert(sizeof(T) >= sizeof(u32));
public:
explicit free_list_vector() = default;
explicit free_list_vector(size_t n)
{
    _array.reserve(n);
    _next_free_index = u32_invalid_id;
}
~free_list_vector() { clear(); }

template<class... params>
u32 add(params&&... p)
{
    u32 id{ u32_invalid_id };
    if (_next_free_index == u32_invalid_id)
    {
        id = (u32)_array.size();
        _array.emplace_back(std::forward<params>(p)...);
    }
    else
    {
        id = _next_free_index;
        assert(id < _array.size() && already_removed(id));
        _next_free_index = read_index(id);
        new (&_array[id]) T(std::forward<params>(p)...);
    }
    return id;
}

constexpr void remove(u32 id)
{
    assert(id < _array.size() && !already_removed(id));
    T& item{ _array[id] };
    item.~T();
    write_index(id, _next_free_index);
    _next_free_index = id;
}

constexpr void clear()
{
    clear_removed_items();
    _array.clear();
}
constexpr decltype(auto) size() const { return _array.size(); }

[[nodiscard]] T& operator[](u32 id)
{
    assert(id < _array.size());
    return _array[id];
}

[[nodiscard]] const T& operator[](u32 id) const
{
    assert(id < _array.size());
    return _array[id];
}

constexpr operator const std::vector<T>&() const
{
    return _array;
}
private:
constexpr void write_index(u32 id, u32 next_free_id)
{
    debug_op(memset(&_array[id], 0xcc, sizeof(T)));
    u32 *const p{ reinterpret_cast<u32 *const>(&_array[id]) };
    *p = next_free_id;
}

constexpr u32 read_index(u32 id) const
{
    return *reinterpret_cast<const u32 *const>(&_array[id]);
}

constexpr void clear_removed_items()
{
    while (_next_free_index != u32_invalid_id)
    {
        const u32 id{ _next_free_index };
        _next_free_index = read_index(id);
        new (&_array[id]) T{};
    }
}

#ifdef _DEBUG
constexpr bool already_removed(u32 id) const
{
    u32 i{ sizeof(u32) }; // skip the first 4 bytes
    const u8 *const p{ reinterpret_cast<const u8 *const>(&_array[id]) };
    while ((p[i] == 0xcc) && (i < sizeof(T))) ++i;
    return i == sizeof(T);
}
#endif

std::vector<T>  _array;
u32             _next_free_index{ u32_invalid_id };
};

Here is a little test:

struct _1 {
explicit _1() = default;
explicit _1(ID3DBlob* b, u32 size)
    :res1{ b }, blah{ size }
{

}
DISABLE_COPY(_1); // deletes copy constructor and copy assignment operator
explicit _1(_1&& o)
{
    *this = std::move(o);
}
~_1() { reset(); }
_1& operator=(_1&& o)
{
    reset();
    res1 = o.res1;
    blah = o.blah;
    new (&o) _1{}; // we don't want to release the COM-object after a move
    return *this;
}

ID3DBlob *const blob() { return res1; }
private:
void reset()
{
    if (res1)
    {
        res1->Release();
        res1 = nullptr;
    }
}
ID3DBlob* res1{ nullptr };
u32       blah{ u32_invalid_id };
};

void free_list_test()
{
free_list_vector<_1> list;
for (u32 i = 0; i < 10; ++i)
{
    ID3DBlob* b;
    D3DCreateBlob(4096, &b);
    list.add(b, 4096);
}

{
    u32 indices[]{ 3, 5, 8, 1, 6 };
    for (u32 i = 0; i < _countof(indices); ++i)
    {
        list.remove(indices[i]);
    }
}

for (u32 i = 0; i < 40; ++i)
{
    ID3DBlob* b;
    D3DCreateBlob(4096, &b);
    list.add(b, 4096);
}

size_t sizes{ 0 };
for (u32 i = 0; i < 45; ++i)
{
    sizes += list[i].blob()->GetBufferSize();
}
assert(sizes == 45 * 4096);

{
    u32 indices[]{ 23, 35, 18, 11, 26 };
    for (u32 i = 0; i < _countof(indices); ++i)
    {
        list.remove(indices[i]);
    }
}
}

int main(){
    free_list_test();
    return 0;
}

Answer 1

With the proviso that it will fail unpredictably if mis-used (ex: deleting an index and then accessing it), the implementation seems reasonable for the most part.

size however, is misleading since it doesn't take removals into account: list size 5 -> add 10 items -> remove 10 items -> list size 15. You could easily track the correct value in add / remove, so I'd suggest doing that.

Related to that, there's no way to traverse the list, or to see whether a particular index is valid. For the purposes you're using it, that might not matter, but it does limit the usage.

Adding a method to convert the contents to a gap-less vector, or to a map (key = index) would give a way to do that. Adding a method to check the validity of a given index is also an option, but at O(n) for each one it's not an efficient way to traverse the contents.

I would definitely suggest removing the implicit (incorrect) conversion to vector though! Treating a free_list_vector with any elements deleted as a normal vector will blow up as soon as you try to traverse it.