Skip to main content
gamedev.net
🔒 Locked

std::vector

Started by d000hg 3 replies 500+ views
Original Post
d000hg
d000hg
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?
Agony
Agony
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.
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o
Qw3r7yU10p!
Qw3r7yU10p!
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 objectsMyObjectItr 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;
Zahlman
Zahlman
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**>. 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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.