# Collecting objects with STL fast?

## Recommended Posts

Hello! Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop. I have written my own dynamic vector class of pointers which allocates a bigger array each time the array is full. I have a counter which i set at the beginning of each frame to 0. The good thing is that no new memory gets allocated for each frame i just set the counter to 0. Appending this way is very fast... The problem is that i now want to move to the STL but i cannot figure out how to make this very easy task with the STL. For example with lists each insertion would allocate a new node, would set pointers etc. Using vectors I dont know how to set the size to 0 without resitzing the whole array which i dont want to do. I just wanted to set the size of the vector to 0 without resizing the vector. How could i do that? Thank you a lot!!!

##### Share on other sites
Presumably your counter is to count the number of objects you've added to the array? The equivalent for the STL vector is the size() method which returns the number of items in the vector.

Now when you say that you set the counter to 0, do you mean you want to empty the array but without releasing the allocated memory? If so then then the clear() method will do this.

##### Share on other sites
std::vector.resize(0) just resets the size to 0, the capacity remains, no memory is freed. don't use clear(), as it is commonly implemented to free the allocated memory. In msvc2003 .clear() didn't free the memory, but that changed in msvc2005, where it now does, and I believe gcc and other implementations also commonly free memory with clear(), resize(0) is what you want.

filling and resize(0) a vector is about the fastest option.

Thank you a lot!

##### Share on other sites
Quote:
 Original post by DrEvilstd::vector.resize(0) just resets the size to 0, the capacity remains, no memory is freed. don't use clear(), as it is commonly implemented to free the allocated memory. In msvc2003 .clear() didn't free the memory, but that changed in msvc2005, where it now does, and I believe gcc and other implementations also commonly free memory with clear(), resize(0) is what you want.filling and resize(0) a vector is about the fastest option.

In VC++2005 Express calling clear doesn't deallocate the memory.
In-fact I believe that clear is meant to call erase( begin(), end()) and erase will not deallocate memory thus neither does clear.
However resize may actually allocate/deallocate memory.
I'm no standards guru though.

##### Share on other sites
It's been a while, I think I got it backwards. 2003 freed the memory and 2005 doesn't I think. The point still stands though, that it is implementation defined, and resize(0) I think is the more commonly accepted way to do that.

Edit: Yes just confirmed. 2003 frees the memory 2005 doesn't. I believe someone else has mentioned before that some other platform, I want to say some version of GCC frees the memory as well, but I don't recall specifically.

##### Share on other sites
Hmm, I'm still not convinced.
I think the standard semantics of clear() are that the capacity remains the same and the size will equal 0.
Whereas for resize(N) the capacity is atleast equal to N and size is at most equal to N.

If so, and 2003 releases the memory during a clear, then it's not being standards compliant.

##### Share on other sites
You may be right. Moreso than whether or not msvc2003 was compliant or not it's been discussed and documented in several optimization papers, such as a presentation at GDC2004 about stl misuse in games, that resize(0) seems to be the most accepted method. clear() may be equally acceptable if properly implemented, which may be safe to assume these days.

##### Share on other sites
Contrary to what I said before, I do not think resize will ever deallocate memory, meaning that resize(0) should preserve the capacity as intended.

That said, if clear() is implemented correctly - by that I mean it calls erase(begin(), end()); (whether that is standards defined or not I don't know) - it would be marginly more efficient than resize(0) due to it not needing to check for growth.

For reference: VC++2008 behaves as VC++2005 and the capacity is preserved upon a clear. [smile]

##### Share on other sites
Surprisingly, getting the standard C++ vector to release memory is nontrivial. The common idiom to do so is the "swap trick": myVector.swap(vector<int>()) to clear the vector and release its memory, or myVector.swap(vector<int>(myVector)) to trim the capacity to the current size.

##### Share on other sites
Quote:
 Original post by dmatterIf so, and 2003 releases the memory during a clear, then it's not being standards compliant.

I'm under the impression that this is exactly the case, and that's exactly why it changed in VS2005.

##### Share on other sites
Quote:
 Original post by extraneusHello!Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.I have written my own dynamic vector class of pointers which allocates a bigger array each time the array is full.

To me, this sounds like:

"I'm worried about performance. I don't want std::vector to allocate new memory on every iteration of the loop, so I made my own custom class that allocates new memory on every iteration of the loop. I am, meanwhile, unaware that the normal, simple usage of std::vector would not allocate new memory on every iteration."

Or were you talking about the outer (per-frame) loop?

##### Share on other sites
Quote:
 Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.

I think, std::list suits here better then std::vector

##### Share on other sites
Quote:
Original post by Ocelot
Quote:
 Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.

I think, std::list suits here better then std::vector

std::list allocates every time an object is added. If avoiding excessive allocation is what you want, std::list is not the way to go.

##### Share on other sites
In some cases you are able to use a list that doesn't allocate memory at all. You can achieve this by storing the next/prev pointers in the objects themselves. The trade-off is that such an object can only be at one list at any given time (although it might be possible to extend this).

An example:

// This class is only for convinience, FastList// will work fine without ittemplate <class T>class ListObject {public:	ListObject():next(NULL), prev(NULL) {}	T *next;	T *prev;};template <class T>class FastList {public:	FastList():head(NULL), tail(NULL), count(0) {}	void add(T &obj) {		if (!tail)			tail = &obj;		if (head) {			obj.prev = head;			head->next = &obj;		}		head = &obj;		++count;	}	void remove(const T &obj) {		if (obj.next)			obj.next->prev = obj.prev;		if (obj.prev)			obj.prev->next = obj.next;				--count;		if (tail == &obj)			tail = obj.next;	}	const T* first() const { return tail; }	int size() const { return count; }private:	T *tail;	// Points to first element	T *head;	// Points to last element added	int count;};

Here's a small program to test this class:

class Obj : public ListObject<Obj> {public:	explicit Obj(int val):id(val) {}	void print() const { cout << id << endl; }private:	int id;};template <class T>void print(const FastList<T> &list) {	for (const T *head = list.first(); head != NULL; head = head->next)		head->print();	cout << endl;}void testFastList() {	FastList<Obj> list;		Obj a(1), b(2), c(3);	list.add(a);	list.add(b);	list.add(c);	print(list);	list.remove(b);	print(list);}

This was quickly thrown together just now, so it might be buggy, inefficient or use poor style, but it illustrates the concept.

##### Share on other sites
Quote:

Storing pointers to stack based objects. Unless you are very careful where you use this, it will blow up in your face. It isn't suitable here because the OP doesn't have all the objects preallocated anywhere so they must allocate space for them somewhere.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628344
• Total Posts
2982186

• 9
• 24
• 9
• 9
• 13