CODEWITHSUNDEEP
c++memory
Cody Smith
Cody Smith

Reputation: 2732

C++ Deleting objects from memory

Lets say I have allocated some memory and have filled it with a set of objects of the same type, we'll call these components.

Say one of these components needs to be removed, what is a good way of doing this such that the "hole" created by the component can be tested for and skipped by a loop iterating over the set of objects?

The inverse should also be true, I would like to be able to test for a hole in order to store new components in the space.

I'm thinking menclear & checking for 0...

Upvotes: 0

Views: 243

Answers (6)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

boost::optional<component> seems to fit your needs exactly. Put those in your storage, whatever that happens to be. For example, with std::vector

// initialize the vector with 100 non-components
std::vector<boost::optional<component>> components(100);

// adding a component at position 15
components[15].reset(component(x,y,z));

// deleting a component at position 82
componetnts[82].reset()

// looping through and checking for existence
for (auto& opt : components)
{
    if (opt) // component exists
    {
        operate_on_component(*opt);
    }
    else     // component does not exist
    {
        // whatever
    }
}

// move components to the front, non-components to the back
std::parition(components.begin(), components.end(),
    [](boost::optional<component> const& opt) -> bool { return opt; });

Upvotes: 3

MoonBun
MoonBun

Reputation: 4402

Two suggestions:

1) You can use a Linked List to store your components, and then not worry about holes.

Or if you need these holes:

2) You can wrap your component into an object with a pointer to the component like so:

class ComponentWrap : public
{
   Component component;
}

and use ComponentWrap.component == null to find if the component is deleted.

Exception way:

3) Put your code in a try catch block in case you hit a null pointer error.

Upvotes: 0

Philipp
Philipp

Reputation: 69663

When you say you have "allocated some memory" you are likely talking about an array. Arrays are great because they have virtually no overhead and extremely fast access by index. But the bad thing about arrays is that they aren't very friendly for resizing. When you remove an element in the middle, all following elements have to be shifted back by one position.

But fortunately there are other data structures you can use, like a linked list or a binary tree, which allow quick removal of elements. C++ even implements these in the container classes std::list and std::set.

A list is great when you don't know beforehand how many elements you need, because it can shrink and grow dynamically without wasting any memory when you remove or add any elements. Also, adding and removing elements is very fast, no matter if you insert them at the beginning, in the end, or even somewhere in the middle.

A set is great for quick lookup. When you have an object and you want to know if it's already in the set, checking it is very quick. A set also automatically discards duplicates which is really useful in many situations (when you need duplicates, there is the std::multiset). Just like a list it adapts dynamically, but adding new objects isn't as fast as in a list (not as expensive as in an array, though).

Upvotes: 0

Bart van Ingen Schenau
Bart van Ingen Schenau

Reputation: 15758

If it is not possible to move the "live" components up, or reorder them such that there is no hole in the middle of the sequence, then the best option if to give the component objects a "deleted" flag/state that can be tested through a member function.
Such a "deleted" state does not cause the object to be removed from memory (that is just not possible in the middle of a larger block), but it does make it possible to mark the spot as not being in use for a component.

Upvotes: 0

fen
fen

Reputation: 10105

There are at least two solutions:

1) mark hole with some flag and then skip it when processing. Benefit: 'deletion' is very fast (only set a flag). If object is not that small even adding a "bool alive" flag can be not so hard to do.

2) move a hole at the end of the pool and replace it with some 'alive' object.

this problem is related to storing and processing particle systems, you could find some suggestions there.

Upvotes: 0

DrM
DrM

Reputation: 1142

The short answer is it depends on how you store it in memmory.

For example, the ansi standard suggests that vectors be allocated contiguously.

If you can predict the size of the object, you may be able to use a function such as size_of and addressing to be able to predict the location in memory.

Good luck.

Upvotes: 0

Related Questions