Sign in to follow this  
Waterlimon

Best way to "remove" elements in a vector but keep the space?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
As ordering doesn't seem to be important then just swap the element to be removed with the last element in the vector and then remove that last element.

[CODE]
std::vector<int> foo;
// ...
// fill elements
// ...
// remove element at position 'x'
std::swap(foo[x], foo[foo.length()]);
foo.erase(foo.length());
[/CODE]

Or code like that.

Share this post


Link to post
Share on other sites
Cant do that as i index the vector so i cant move existing nodes. :P

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.

Share this post


Link to post
Share on other sites
[quote name='Waterlimon' timestamp='1339254708' post='4947664']
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.
[/quote]
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 [i]why/what are you accomplishing[/i]?). 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:
[code]
std::swap(foo[x], foo.back());
foo.pop_back();
[/code]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img]
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. Edited by dmatter

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. Edited by larspensjo

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
I use it for an sparse octree so it should be cache friendly. A node currently takes 5 bytes (+4 for parent pointer but i dont think i need that one) + The data carried

So the "structural" space requirement is 5 bytes. Doing it with pointers and new is out of the question, its just way too ugly ans would probably double the node size (might be way more inefficient than that, i think its designed for larger chunks of data)

I could put the objects in a class with a bool to indicate wether it exists or not and fill the array with those. I just dont like wasting a byte for each node.

Ive already made it by using a method to check an objects validity and invalidate one, so ill probably just keep it like that.

Share this post


Link to post
Share on other sites
[quote name='Waterlimon' timestamp='1339277478' post='4947757']I use it for an sparse octree so it should be cache friendly. A node currently takes 5 bytes (+4 for parent pointer but i dont think i need that one) + The data carried[/quote]

Pardon my ignorance, but what is a sparse octree? I know what a sparse matrix is, and an octree, but not a sparse octree.

[quote]Ive already made it by using a method to check an objects validity and invalidate one, so ill probably just keep it like that.[/quote]
It may be you already have the best solution.

How many objects do you think there will be in the octree?

Share this post


Link to post
Share on other sites
Sparse octree is an octree where a subnode may or may not exist. (if it doesnt exist, it means that node and everything that it should contain if it were a regular octree are empty)

I expect to have as many objects as possible. I dont have a goal to how much data i want, but more data at more efficiency will leave more room to mess around with other stuff or have higher detail.

I would use the tree for both large terrain and small objects if i ever get ar enough to implement them.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this