I have a

std::vector<object>

now, lets say it has 500 objects in it. What i want to do, is to remove a object from the middle of it. I do not want to create a new vector or move the objects after it to fill in the space, but instead, i want to keep the space so that later i can check it and then be like "oh, theres a free space there, lets put this new object there instead of at the end of the vector"

What is the best way to do this?

Currently, my object has methods IsValid and Invalidate so i can check if the slot is free (i dont need any extra variables in the object to do this, i just set the existing variables to an otherwise impossible configuration)

Then when i want to put another object there, i do

vector[x]=anotherobject


This feels messy to me, but as i dont want to use extra memory to indicate wether a slot in the vector is empty and use the variables of the object, i dont see another way.

Should i just make it a class like

class ObjectVector
{
public:
operator[](blah);
IsFree(index);
Free(index);
private:
std::vector<object> vec;
}

To make it cleaner?

Cant do that as i index the vector so i cant move existing nodes.

I could call the destructor of the object manually, but i would need to set it to an invalid state in the destructor and call a method of it after its been destroyed to check the state and that feels ugly too.

I could call the destructor of the object manually, but i would need to set it to an invalid state in the destructor and call a method of it after its been destroyed to check the state and that feels ugly too.

That actually would be undefined behavior. When the vector gets destroyed, the Object's destructor would be called again. You really don't want to do that.

I think the best way is to redesign things. I think you have a design flaw here, and I can't really recommend a better way since I really don't know why you're doing this in the first place (ok, I get what you've explained, but why/what are you accomplishing?). But if you're not going to do that, then I'd say that wrapping an std::vector in a special class, something like you have above, would be ok.

@phantom: I think it's more like:

std::swap(foo[x], foo.back());
foo.pop_back();


I usually devise a way to mark objects as "dead" so in case of classes this might just be a "bool dead" or so and then simply ignore any dead objects. If its already a vector of pointers then just destroy the object and set the pointer to 0/nullptr... in addition I often keep a stack onto which I push deleted indices. So when I want to fill one of the empty spots i can get it from there.

It really depends on what it is you're doing with this vector the rest of the time and how performant/complex this needs to be.

There are a few options though, the "swap 'n' back-pop" trick has already been mentioned and if you could notify whatever indexes the last element that its index has changed then that works quite well. Alternatively you could choose to not store the objects by-value in the vector and just store a pointer. Rather than index into that vector just have things reference those objects directly using pointers. Now you can move the pointers around in that vector as needed.

You could maintain a collection of indicies that refer to free locations in the vector, then you just pick indicies from there before resorting to a push_back.

You could implement some kind of garbage-collection, so most of the time you just do push_backs but when some condition is met (could be when size() == capacity() and you want to add a new object but don't want to incur a reallocation of the vector) then you can compact the vector by shuffling all the objects down over the top of dead objects (represent 'dead' anyway you like), allowing you to continue to add new stuff to the back. As part of the compaction process you'd need to re-index.

Another idea, just don't sweat it
If you're not very likely to be adding or deleting stuff and/or not likely to be running low on memory then just leave them in the vector as zombies. If the vector is short lived (e.g. you recreate it for each level, or even if it stays around for the entire lifetime of your program but your program doesn't have to run continuously for days on end) then these zombies will get cleaned up eventually through the natural course of things.

Im using it as a node pool for my sparse octree class. I dont want to use extra memory (pointers etc.)

And yes im going to add something to compress the spaces out once in a while and keep track of sequences of empty nodes.

I guess ill just go with wrapping the vector into a nice little class.

These types of design questions are always interesting. Please state what your requirements are, and let's see what the best design would be. There are usually really neat solutions "out there", or design patterns that makes life easier. As you rejected some of the proposals above, it would indicate that you also have additional requirements than was shown in the original questions.

Yeah.

1.I need them in the vector as objects or else they need to be allocated using new (=scattered all around memory and slow)

2.I want to not use memory unless i need to (using a vector of pointers would add 4-8 bytes+all the memory fragmentation waste)


So i have to keep them as objects in the vector, and i have to use a special state of the object to indicate its "empty"

But, how do i do this in a nonmessy way?

It seems some of your requirements are of the optimization type, where the standard solution is not good enough. Usually, I try to design the code flexible and delay with these types of optimizations to later in the project, when measurements show they are really needed. I, at least, find it hard to clearly identify bottle necks early in the project.

When you say new() gives scattered memory, that can certainly be true. Scattered and fragmented memory can give worse performance if the application needs large amounts of memory, leading to swapping behaviour. is that the case in you application? There may also be degraded cache performance because of scattered memory, but that may be harder to take into account..

I suppose new() is "slow", but that depends on what you compare with. Having a linear vector where you have to search for free slots seems like a high risk of being slower.

new() will have some memory overhead for each memory block. Do you have a rough estimate on what the size will be of the blocks you plan to use?