Take the 2-minute tour ×

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...

share|improve this question
Maybe using a normal container would do just as well and make your life much easier? Or if there are reasons you need this specific set up, what have you tried so far? –  aschepler Jan 14 '13 at 19:30
While you're asking about the difference between NULL and 0 (really should be asked in a separate question) don't forget the C++11 nullptr. –  Joachim Pileborg Jan 14 '13 at 19:33
"Lets say I have allocated" Or maybe show us some code you're working with? This is a coding site. –  GManNickG Jan 14 '13 at 19:33
I realize that on my own, you were just too fast :p –  Cody Smith Jan 14 '13 at 19:33
add comment

6 Answers

up vote 3 down vote accepted

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

// deleting a component at position 82

// looping through and checking for existence
for (auto& opt : components)
    if (opt) // component exists
    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; });
share|improve this answer
Reading the document explaining boost::optional exposed this problem in great detail. This is actually a very very good solution to the issue. –  Cody Smith Jan 14 '13 at 22:10
Excellent example code. –  GManNickG Jan 15 '13 at 0:26
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
I considered moving the last element into the "hole" but doing so means keeping track of any pointers pointing to every element. For simplicity and speed reasons I'd like to avoid moving elements. What if a certain byte was written to the first byte of the object? –  Cody Smith Jan 14 '13 at 19:39
yes, writing a single byte before (or after) element would also be helpful. Note that you have the same objects, with the same size, so it is quite easy to 'jump' over the whole array of objects. But for efficiency you should have some list of holes. But still, that is how memory managers work. –  fen Jan 14 '13 at 19:41
add comment

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.

share|improve this answer
add comment

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).

share|improve this answer
I am talking about an array, I dislike linked-lists because they fragment memory, and are asking for cache-misses. –  Cody Smith Jan 14 '13 at 19:45
You know about memory fragmentation and cache misses, but you don't know how to use arrays properly? –  Philipp Jan 14 '13 at 19:53
@Philipp: As standard arrays don't support the feature he is requesting, I'm curious why you say he doesn't know how to use arrays properly? –  Benjamin Lindley Jan 14 '13 at 20:11
add comment

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.

share|improve this answer
With the new C++, you can even go up to Warp 11. –  Kerrek SB Jan 14 '13 at 19:44
fixed it :P sorry –  Vladp Jan 14 '13 at 19:46
add comment

Your Answer


