Hello, I've been experimenting with STD::Vector, And I've been trying to find the most efficient way to delete a large number of items from an Std::Vector, In the fastest way possible.

This Is the program I have been writing:

#include<iostream>
#include <memory>
#include <vector>


using namespace std;


struct SmallObject1
{
int a[256];
};


int main()
{
char a;
typedef vector<shared_ptr<SmallObject1>> ObjectList;
ObjectList * list1 = new ObjectList();
cout << "Allocate 65536, objects Lol!" << "\n";


for(unsigned int i = 0; i < 65536; i++)
{
SmallObject1 * smallObject1 = new SmallObject1;
shared_ptr<SmallObject1> a(smallObject1);
list1->push_back(a);
}


cout << "Allocated! Try Again?" << "\n";
/*while(list1.size() != 0)
{
list1.pop_back();
}*/
//list1->clear();
delete list1;
list1 = new ObjectList;
cout << "Deleted....";


for(unsigned int i = 0; i < 65536; i++)
{
SmallObject1 * smallObject1 = new SmallObject1;
shared_ptr<SmallObject1> a(smallObject1);
list1->push_back(a);
}


cout << "COMPLETE!!!1!!!";
while(1)
{
}


return 0;


}

Why all the pointers? Why is your vector not simply of type `std::vector<SmallObject1>'? And why is the vector itself a pointer?

They Are all pointers so that way I can share the objects with multiple lists (Display Lists, Collision lists, etc...), and the vector being a pointer so I can reference it to multiple objects that need the list.

Well, isn't there one of the vectors that naturally owns all those objects? The other vectors can store indices into the owner.

EDIT: The part about the vector being a pointer I didn't understand at all.

Ah, well I guess it doesn't need to be a Pointer vector, however If I had a Physics Class, or a Rendering Class, I might want each class to have an empty ObjectList * objectList variable to hold a reference to the list if it needs it.

Nyways, I tried converting the list to one Without smart pointers, and now it is much much faster, It works almost immediately. But, I need to use pointers, because if I have a base class of GameObject, that inherits to multiple different Classes, I will need a Vector of Pointers instead of just a GameObject Vector.

How have you profiled this code? I suspect that the "delete list1;" call might be pretty quick compared to the allocations and push_back() calls (which will dynamically resize your vector). First step is to verify that the slow part is actually what you think it is.

Second step is to be sure you are using a non-debug build, as allocations and deletes can be significantly slower with debug builds.

If you are using Visual Studio, be sure to turn off the STL debugging stuff, too, as that can be frightfully slow.

OK, if all of that doesn't help (and I think it will), the big optimization I can think of is to move away from std::vector and use the C-style array allocation mechanism directly. Then you can allocate and free a while bunch of objects at once. This is not nearly as maintainable, though, so be sure to exhaust other possibilities first.

Hmm... an object pool could work too. Also to be avoided if possible.

Good luck!

Geoff

Well, Every time I allocate all 65,536 Objects to the list, it happens very quickly, however deleting the list actually takes around 5 seconds, and I don't know why .

I switched to release mode and disables Secure Scl, and it improved, but not by much. I don't want to switch to the c-Style array until I have run out of options.

I know that games like minecraft have to allocate and deallocate Hundreds of Thousands of blocks and game objects at runtime, so there HAS to be a solution to this..

Every time I allocate all 65,536 Objects to the list

Why on earth are you allocating and deleting 2^16 objects? That seems like an awful lot of items...

Are you deleting things one at a time?

Whenever you delete an item from a vector that's not the last thing, all the elements afterwards get copied one space forward to fill the gap, and if you delete many items one at a time, at some point a re-allocation might occur to save memory space. So, for example, if you were to loop through the vector front-to-back deleting individual items, you're pretty much guaranteeing a pathologically-bad use-case. Doing the same back to front is a little better, but not by much (fewer iterations, but I don't think even enough to change the Big-O order).

The right way to delete many items from a vector is to first partition the vector into things you will keep, and things you will delete, and then you delete the things you want to get rid of after that. The way to do that is to call remove_if on your vector with a predicate that sorts the things you want to keep from those you don't. Then, it returns an iterator to the first thing that's removed, and you can use that iterator to call delete over the range from that iterator to the end of the container. This is better because only individual items are copied, and at most once. Also the memory re-allocation can only happen once, if it needs to.

Also, in regards to your using pointers, someone mentioned that one container could own the resource directly, and other vectors could reference them by index. If you frequently add/remove items from the owning list, the indexes will change every time you add or delete and item. This makes using indexes troublesome, unless you can build-up those indices in the other lists anew -- this is fairly common for a list of drawable objects, but might not be common for other uses. It depends on your use-case. Pointers of some type might be perfectly valid, but I'd look into the standard smart pointers like shared_ptr, weak_ptr, and unique_ptr. From your brief description, it sounds like you might want to do shared_ptr in the owning list, and weak_ptr in the other lists (unless you can build up those lists each frame, between delete/insert cycles).