Sign in to follow this  
d000hg

std::vector

Recommended Posts

d000hg    1199
I have a base class containing a vector. Objects can be registered with it, and each one is allocated some 'slots' in the vector. Ie the 1st object asks for 5 slots and gets allocated vector[0]-vector[4], the 2nd object registered wants 3 slots and is allocated [5] to [7], and so on. I can use resize/reserve to endure the vector is large enough, each time an object is registered. But say I have the following vector: vector{ 1.Object #1 2.Object #1 3.Object #1 4.Object #2 5.Object #2 6.Object #2 7.Object #3 8.Object #3 9.Object #3 } I want to unregister Object #2, which leaves: vector{ 1.Object #1 2.Object #1 3.Object #1 4.--- 5.--- 6.--- 7.Object #3 8.Object #3 9.Object #3 } My questions are about the behaviour of vector. If I use vector.remove(), do slots 4-6 just get abandoned or does the rest of the vector get moved up 3 places? Is it going to take more and more memory to register an object, then unregister it many times or will the vector be smart? What about using the array operator on the vector after removing items from the middle - will vector[5] still have the same value?

Share this post


Link to post
Share on other sites
Agony    3452
std::vector::remove() will shift all the items after the removed items forward, so that there is no empty space in the vector. As you can figure, this could take quite a bit of time when you remove early items from a large vector.

This situation that you described is basically the same as memory allocation and management. The idea is to have to avoid moving and shifting blocks of memory as much as possible, while still being able to quickly allocate more memory, and also while using the memory as efficiently as possible, so you don't have little wasted chunks laying around. It's complicated. Here is a quick link I found that seems to describe the complications reasonably well, although I'm sure there are better sites.

If you can, I suggest letting the actual memory manager of the OS do that for you. Just have a container of vectors or something. Each element in the outer container corresponds to an object that is registered with it. And then each vector in that element can be resized to be whatever size it needs to be. For the outer container I would suggest a linked list, if you plan on removing elements from the middle quite a bit, although a vector would still not be as bad as before (less data to copy), and would overcome a lot of limitations of linked lists.

If you absolutely need all of these individual elements to be in one single contiguous block, might I suggest researching various allocators for STL containers, primarily pool allocators.

Share this post


Link to post
Share on other sites
petewood    819
I'd go with std::deque or std::list.

Or hold in the vector pointers to objects rather than the objects themselves. Then remove use remove_if and erase.


bool ObjectMeetsSomeCondition(Object* obj) {
//..,etc.
}
typedef std::vector<MyObject*> MyObjectCont;
typedef MyObjectCont::iterator MyObjectItr;
MyObjectCont myObjects;
//push_back some objects
MyObjectItr begin = myObjects.begin();
MyObjectItr end = myObjects.end();
MyObjectItr it = std::remove_if(begin, end, ObjectMeetsSomeCondition);
myObjects.erase(it, end);



Of course the real objects won't be deleted. If you store a smart pointer instead it will automatically delete it for you. E.g if you have boost smart_ptr available, change the first typedef to:
typedef std::vector<smart_ptr<MyObject> > MyObjectCont;

Share this post


Link to post
Share on other sites
Zahlman    1682
If you want this "empty slot" behaviour for some weird reason, and you only want to have to change one thing in order to unregister an object, consider storing a vector<Object **>. Yep, double indirection.

To register an Object, create an Object*, then store the address of the Object* (which is an Object**) in several vector entries.

To unregister an Object, access the Object* (either by dereferencing one of its Object**s in the vector, or by some other means) and set it null. Now all the Object**s point at the same Object* which is null, so they represent "empty slots".

To access an Object, look up the Object** in the vector and dereference once; if the result is null then you have hit an empty slot, otherwise dereference again.

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