Re: list allocator
eno@saxobank.com wrote:
Hi,
As there is a lot copying involved when using the STL containers, I
was wondering about the default allocation strategie.
I have a list of objects that hold a number of primitive types like
(not real code):
class CSampleObject
{
private:
long m_Size;
public:
double m_Double1;
double m_Double2;
enum m_enum1;
long m_Long1;
DATE m_Date1;
enum2 m_enum2;
bool m_Bool1;
bool m_Bool2;
};
This list is heavely used with many insert, erase, lookup operations,
but the list never hold more than 25 elements.
Does there per default occur a new memory allocation each time a
element is inserted, or does the list hold a internal supply of memory
to use?
The number of copies depends on the container.
std:list, std::set, std::multiset, std::map, std::multimap will each copy
the object exactly once (when it's inserted), no matter the operations done
on the container.
std::vector will copy the object every time the vector changes capacity, or
when an element is inserted into or deleted from the vector at an index
lower than the element in question.
std::deque will be somewhere between std::list and std::map in terms on when
and how many copies are made. std::deque doesn't resize the same way a
vector does, and inserts/deletes are not guaranteed to affect elements at
higher indexes (in practice, some elements with higher indexes will be
affected, but not all).
The allocation strategy also depends on the container, and leads directly to
the copy behavior I described above.
std::list, std::set, std::multiset, std::map and std::multimap allocate a
new node for every element that's inserted.
std::vector has a single allocation that's resized as needed using
exponential growth, which provides amortized constant access time. You can
cause the vector to pre-allocate a buffer of (at least) a certain size by
calling vector::reserve.
std::deque is a hybrid that stores, in effect, a list of vectors (buckets).
Each bucket is typically a fixed-size allocation - when a bucket gets full,
another bucket is allocated and added to the list. Inserts and deletes
shuffle items between the buckets as necessary.
All of these requirements are spelled out very precisely in the C++
standard, so you can rely on exactly when a standard container is allowed to
copy your object.
For a small collection, even if it's sorted and randomly inserted/erase, a
plain vector usually gives the best performance - the copying of small
objects like yours is considerably cheaper than allocating memory.
-cd