0
\$\begingroup\$

I have a std::unordered_map where a key will map to a value that is an array of a simple type (a type with no dynamically allocated members). The array can't be templated (to my knowledge) because it has to be stored in the std::unordered_map. This is the implementation that I came up with to deal with this.

class Pool {
private:
    std::size_t m_componentSize = 0; // Size of a component instance
    std::vector<std::uint8_t> m_data; // Contiguous array of uint8_t which make up the individual bytes of all the component instances in the pool
    std::vector<std::size_t> m_deleted; // list of indices into m_data where (m_deleted[n] -> m_deleted[n] + componentSize) is freed component instance memory

public:
    // Create a pool for a given component size
    Pool(std::size_t componentSize) :
        m_componentSize{ componentSize }
    { };

    Pool() = default;

    // Add component instance to pool
    // Will reuse deleted component instances
    // Returns the index of the new component instance
    std::size_t addComponent() {
        std::size_t index;

        if (m_deleted.size() > 0) { // Reuse an old component instance's memory to create new component instance
            index = m_deleted.back();
            m_deleted.pop_back();

            // Intialize the component instance's byte values to zero
            for (std::size_t offset = 0; offset < m_componentSize; offset++)
                m_data[index + offset] = 0;
        }
        else { // Create new component instance
            index = m_data.size();

            std::vector<uint8_t> temp(m_componentSize, 0);
            m_data.insert(m_data.begin() + index, temp.begin(), temp.end());
        }
        return index / m_componentSize;
    }

    // Free component instance from pool
    // Component instance will be marked for reusedto be freed
    void deleteComponent(std::size_t index) {
        m_deleted.push_back(index * m_componentSize);
    }

    // Returns true if a component instance specified by the index has been freed
    bool isComponentFree(std::size_t index) {
        return std::find(m_deleted.begin(), m_deleted.end(), index * m_componentSize) != m_deleted.end() ? true : false;
    }
    // Access a component instance
    template <typename Component>
    Component& at(std::size_t index) {
        return *reinterpret_cast<Component*>(m_data.data() + (index * m_componentSize));
    }
    // Get array of all component instances (including instances that have been freed)
    template <typename Component>
    Component* data() {
        return reinterpret_cast<Component*>(m_data.data());
    }
    // Return the number of component instances in pool
    std::size_t size() {
        return m_data.size() / m_componentSize;
    }
    // Make space for [count] component instances
    void reserve(std::size_t count) {
        m_data.reserve(count * m_componentSize);
    }
    // Return size of the component stored by this pool
    std::size_t componentSize() {
        return m_componentSize;
    }
};

Questions for Reviewers:

  • How can I make this more type safe?
  • Are there better alternatives for storing an array of values in a type-agnostic way?
  • Is it performance friendly?
  • How can I make the interface more user friendly?
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Questions

How can I make this more type safe?

There are a number of problems that make this not only not type safe, but straight-up UB.

Let’s start with the fundamental problem. You say this is for “simple” types… but what exactly is a “simple” type? A type with “no dynamically allocated members”? std::mutex has no dynamically allocated members. You think that is a simple type? It certainly won’t work with this class.

You need to really clarify EXACTLY what you mean by “simple”. Do you mean trivially copyable? If so, then yeah, this class will sorta-kinda work (not counting the other UB issues). If you don’t mean trivially copyable, then you need to do a lot more to make this class type safe: manual copy/move construction/assignment, manual deletion, etc., etc., etc..

Other major problems with type safety have to do with the fact that you’re using a std::vector<std::uint8_t> as your byte array.

First of all, std::uint8_t is just plain wrong. The only types you can use for raw memory storage are char, unsigned char, or std::byte. std::byte is the logical choice, as of C++17. std::uint8_t isn’t even guaranteed to exist.

Second, std::vector doesn’t (naturally) allow you to set the alignment. Since you’re allocating raw bytes, std::vector is perfectly within its rights to use an alignment of 1… which will very likely break for everything on a system that doesn’t tolerate misaligned data. (You can technically specify alignment by using a custom allocator… but let’s not go there.)

You’re going to need to manually allocate the array, probably using alignof(std::max_align_t). That means you’re going to have to deal with all the headaches of manual memory management. It also means that, by all rights, you should be using allocators… but I don’t even know how you’d ask for arbitrary alignment with allocators, so… 🤷🏼.

So the bottom line is: this won’t work, and I don’t even know how to suggest that it could… unless you want to just not use allocators (which wouldn’t be a great idea).

Are there better alternatives for storing an array of values in a type-agnostic way?

As I mentioned above, if you’re not using allocators, you have one and only one option that I can think of: a manually allocated array of std::byte, with maximum alignment. If you are using allocators (as you should), then… 🤷🏼.

Note that this assumes you actually need to be able to get an array of T. Your description of the problem you are trying to solve is too vague. Do you actually need something that can be “an array of intOR “an array of double” (but not an array where some elements are int and some are double)? Or do you just want “an array of stuff”, where each array element could be an int or a double?

In other words, is this intended to be okay:

auto data = Pool{std::max(sizeof(int), sizeof(double)};

auto const double_index = data.addComponent();
auto const int_index = data.addComponent();

data.at<double>(double_index) = 1.0;
data.at<int>(int_index) = 3;

Because that’s currently possible with the interface.

If that’s supposed to be okay, then you might consider a std::vector<std::any> instead.

If that’s not supposed to be okay—meaning you want a homogeneous array—then your current interface won’t do. You need to consider alternatives.

You might consider deciding exactly which specific types are okay, rather than trying to support any arbitrary “simple” type (whatever that means), and using a std::variant<std::vector</*first valid type*/>, std::vector</*second valid type*/>, ...> for a limited set of types.

If you really want to be able to support arbitrary types, then… you’re back to a manually managed array of std::byte.

Is it performance friendly?

Your first concern should be making it work, not making it fast. There’s no point in making a class that’s very efficiently wrong.

When it comes to performance, it depends on what things need to be performant. You can’t have it all; programming is engineering, and engineering is all about trade-offs.

What do you want To be “performance friendly”? Construction? Modification? Access?

And what kind of performance do you want to be friends with? Speed? Size in memory? Short term or long term?

How can I make the interface more user friendly?

This interface will be a nightmare to work with, in practice.

Let’s imagine, for example, a fairly simple scenario: I have put a bunch of ints in an instance of this class, and I want to remove all that are equal to 7. Here’s what I would have to do:

// This is what I start with:
auto data = Pool{};
// ... fill data with integers somehow...

// Step 1: Get the size of the data
auto const size = data.size();

// Step 2: Write a loop that iterates over the data
// Note: Have to write a loop, because this structure uses indexes, rather
//       iterators, so I can't use standard algorithms, or even a range for.
for (auto i = decltype(size){}; i != size; ++i)
{
    // Step 3: First, make sure the element actually exists
    if (not data.isComponentFree(i))
    {
        // Step 4: Manually check the element
        if (data.at<int>(i) == 7) // hope and pray the type is right, because there's no checking!!!
        {
            // Step 5: Manually delete the element
            data.deleteComponent(i);

            // Note that this is not safe! deleteComponent() pushes the index
            // onto the m_deleted vector... which may trigger an exception!
        }
    }
}

// Step 6: Go through the data AGAIN, keeping track of the number of deleted items
// Note: Technically, you could work this into the above loop, and only do
//       one pass... but it would be an extremely complicated pass, and if
//       there were any errors, the data set could be left in a mess.

// ... you know what, I'm not bothering to even *try* to write any more steps.
// It's going to be dozens and dozens of lines of *very* tricky code, and I
// think my point is well made by now.

Compare that to what I have to do for most containers in C++20:

// This is all it takes:
std::erase(data, 7);

// And it's perfectly safe, with no chance of exceptions (in any container
// I've ever worked with). Not to mention probably *hundreds* of times faster
// than the code above.

And that's for a very simple, and trivial operation. Imagine if you wanted to do something more complicated, like a stable partition followed by a transform of the elements in the second group, then a search of the results.

Or, hell, just imagine trying to sort the contents.

Even the simple act of adding an element is a chore:

// All I want to do is add the number 12 to the data.

// Step 1: Add the "component", remembering the index
auto const index = data.addComponent();

// Step 2: Actually set it to the value I want
data.at<int>(index) = 12;

The problem is that this class doesn’t follow the interface standards for containers, or ranges, or anything really. That’s really bad. It means I can’t use this class with standard algorithms, or the ranges library, or pretty much anything. It means that if I were forced to use this class in a code base, it would become a viral problem; it would infect every function it has to be used with, making me have to do extra work everywhere to interact with it. (Which would require extra, custom algorithms, which would all need to be tested, etc. etc. … basically, a viral problem.)

To put it bluntly, not only would I never use it, I would strongly recommend that nobody ever uses it. If used in a code base, I’d consider that code base a lost cause.

If you want to fix that, the first thing you need to do is study up on standard interfaces. Basically, you want your class to be a drop-in replacement for std::vector, as much as possible. At the very least in the most modern versions of C++, you need iterators and std::begin()/std::end() support. Not having that makes the class useless.

I would suggest that you rethink the basic idea, and instead of having a single class that does everything—which is known as the god object anti-pattern—break up the responsibilities. For example, you could have one class that provides appropriately-aligned raw memory… and a second class that provides a type-specific view. For example:

class type_agnostic_array
{
    // This class does all the work of managing an array of std::byte,
    // maximally aligned.
};

template <typename T>
class typed_view
{
    // This class has exactly the same interface as std::vector<T>.
    // Internally it uses type_agnostic_array as the storage.
};

Code review

You are missing the required includes/imports for this class.

class Pool {

This is a terrible name. It doesn’t describe, even in the vaguest sense, what this class does.

Indeed, the naming is pretty bad throughout. “Component” doesn’t make sense at all; “element” or “item” would make more sense. size() doesn’t actually give the number of elements… or if it does, then deleteComponent() doesn’t do what it says. (It’s all incoherent. I can create a Pool, call addComponent() twice, then call deleteComponent() twice, and size() says 2. So… deleteComponent() doesn’t actually delete any components. Also, addComponent() doesn’t actually add any components; it just adds space for a component… but it does increase the size. 😵‍💫)

    Pool(std::size_t componentSize) :
        m_componentSize{ componentSize }
    { };

This constructor should be explicit, to start with.

But it’s really a terrible idea. I would expect that Pool{4} constructs a pool (whatever that means) with 4 components. Instead, I get a pool with zero components.

    Pool() = default;

Think about this for a moment; think about what state this constructor is leaving the object in.

Thought about it? Alright, now consider this innocent code:

auto p = Pool{};

std::cout << "The size of a default-constructed pool is: " << p.size();

Boom. Crash.

    std::size_t addComponent() {
        std::size_t index;

        if (m_deleted.size() > 0) { // Reuse an old component instance's memory to create new component instance
            index = m_deleted.back();
            m_deleted.pop_back();

            // Intialize the component instance's byte values to zero
            for (std::size_t offset = 0; offset < m_componentSize; offset++)
                m_data[index + offset] = 0;
        }
        else { // Create new component instance
            index = m_data.size();

            std::vector<uint8_t> temp(m_componentSize, 0);
            m_data.insert(m_data.begin() + index, temp.begin(), temp.end());
        }
        return index / m_componentSize;
    }

Okay, let’s consider the first branch to start:

if (m_deleted.size() > 0) { // Reuse an old component instance's memory to create new component instance
    index = m_deleted.back();
    m_deleted.pop_back();

    // Intialize the component instance's byte values to zero
    for (std::size_t offset = 0; offset < m_componentSize; offset++)
        m_data[index + offset] = 0;
}

For starters, that test should probably be if (not m_deleted.empty()).

Next, you should avoid naked loops wherever possible. That loop should be:

std::fill_n(m_data.data() + offset, m_componentSize, 0);
// or, if m_data is an std::byte vector, the last argument could be std::byte{}

But setting the element’s bytes to zero is a terrible, terrible idea. You don’t even know what type it is! This is a type-erased class! How do you know all zeros is a valid value for an unknown type? You have literally no idea what this could result in. For example, suppose it’s supposed to be a double in there… the moment it gets cast and accessed as a double, it could be a trap representation, and trigger a hardware fault, crashing the entire system (obviously only in an embedded system, not a desktop). Even if it doesn’t immediately crash the whole system, you could have just screwed up the invariants for whatever happens to be there… which could cause any kind of problem later.

As for the second branch…:

else { // Create new component instance
    index = m_data.size();

    std::vector<uint8_t> temp(m_componentSize, 0);
    m_data.insert(m_data.begin() + index, temp.begin(), temp.end());
}

What’s with the temporary vector (a whole new allocation!)? All you need to do is m_data.resize(m_data.size() + m_componentSize).

Again, you’ve just got a bunch of zeros there. That’s not necessarily a valid value for whatever is supposed to be there. Of course, the catch is… you don’t have a clue what’s supposed to be there! That means this function is fundamentally broken.

What you need here is for this function to take the type… and, arguably, the construction arguments. In other words, more like:

template <typename T, typename... Args>
auto addComponent(Args&&... args) -> std::size_t
{
    auto index = std::size_t(0);

    if (not m_deleted.empty())
    {
        index = m_deleted.back();
        m_deleted.pop_back()
    }
    else {
        index = m_data.size();

        // I'm simplifying a lot here!!!
        //
        // In reality, if you’re not dealing with trivially copyable types,
        // you need to make a temporary raw memory array, and move everything
        // into it. (And if moving is not noexcept... well, that's a whole
        // other kettle of fish.)
        m_data.resize(m_data.size() + m_component_size());
    }

    // Again, simplifying!
    //
    // You need to consider what will happen if this throws.
    std::ranges::construct_at(reinterpret_cast<T*>(m_data.data() + index), std::forward<Args>(args)...);

    return index / m_componentSize;
}

So you can’t add components without knowing their type anymore. (But that’s just the tip of a very big iceberg, because you would also need to be able to properly destroy all the objects, and so on.)

    template <typename Component>
    Component& at(std::size_t index) {
        return *reinterpret_cast<Component*>(m_data.data() + (index * m_componentSize));
    }

In the standard container interface, at() is bounds-checked. Since it isn’t here, that could lead to nasty surprises.

Also, this and several of the other functions could and should be const safe. For this function, you’d need two versions: one that is const and one that isn’t.

    std::size_t size() {
        return m_data.size() / m_componentSize;
    }

As I hinted above, when m_componentSize is zero….

Summary

Before going any further with this type, I think you need to do a lot of very hard, very thorough thinking about EXACTLY what it is you’re trying to accomplish, and why. I strongly suspect that whatever made you think you need this is a symptom of a much bigger design problem.

But okay, let’s assume you really do need a type that is an “any array”—a contiguous array of an unknown (but homogeneous) type. In that case:

  1. You need to make sure the internal raw storage is appropriate aligned. std::vector<std::byte> won’t do that for you.
  2. You need to manually handle all the tedious operations: construction, destruction, copying, moving, etc.. If by “simple” type you mean a trivial type, then you can get away with ignoring most of those operaitons (because they’d be trivial)… but you still have to be very, very, VERY careful about which.
  3. It will be impossible to have a standard container/range interface for a type-erased array… but you should still try to get as close to it as possible. You should probably pair the class with a view class that fixes the type (with the standard interface), so you can use standard algorithms and range stuff.

But really, my bottom line recommendation is: Don’t even try to do this. Whatever situation you have that is making you think you need this is probably just the symptom of a much bigger design problem.

The reason I say don’t even try to do this is because I think you are MASSIVELY underestimating how difficult it would be to do this properly. For starters, you are basically trying to reimplement std::vector… which is already one of the hardest things to do in C++. But you’re actually trying to go a step further, and trying to implement a type-erased std::vector. If you can actually manage to get that done, then you should submit a talk at the next C++ conference. That should give an indication of how crazy difficult this would be to pull off.

\$\endgroup\$
3
  • \$\begingroup\$ I had a bad idea at the start of the whole design process for the bigger project and I ran with it and it lead to this. Really only posted it so someone could tell me "just do this instead", because there's usually a standard class that does it better. The types are trivial and the array should only hold one type. I'm making an Entity Component System, and this is really only accessed internally. The main interface abstracts all the... kinks.. away, but I still wanted to get an alternative or something so the code I write isn't so painful. Any recommendations for alternatives to... this class? \$\endgroup\$
    – fortytoo
    Apr 1, 2022 at 4:47
  • \$\begingroup\$ Without knowing the details, I can’t give any solid suggestions. 1) Do you need a contiguous array of the stuff? If not, a vector<any> (or vector<variant<T1, T2, ...>>) might work. 2) Is the set of types limited? Then a variant<vector<T1>, vector<T2>, ...> might work. Or even just use an any to holds vectors of whatever. If nothing else can possibly work, then I might even reluctantly fall back on a void* (or, more realistically, something like a unique_ptr<byte, void (byte*)>, maybe bundled with a tag identifying the erased type). \$\endgroup\$
    – indi
    Apr 3, 2022 at 16:18
  • \$\begingroup\$ I did go with an unordered_map with the key being a type_index and the value being an any that gets assigned a vector of the type specified by the type_index. Thank you for your help \$\endgroup\$
    – fortytoo
    Apr 4, 2022 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.