Nested STL vector using way too much memory

Question

I have an STL vector My_Partition_Vector of Partition objects, defined as

struct Partition // the event log data structure
{
    int key;
    std::vector<std::vector<char> > partitions;
    float modularity;
};

The actual nested structure of Partition.partitions varies from object to object but in the total number of chars stored in Partition.partitions is always 16.

I assumed therefore that the total size of the object should be more or less 24 bytes (16 + 4 + 4). However for every 100,000 items I add to My_Partition_Vector, memory consumption (found using ps -aux) increases by around 20 MB indicating around 209 bytes for each Partition Object.

This is a nearly 9 Fold increase!? Where is all this extra memory usage coming from? Some kind of padding in the STL vector, or the struct? How can I resolve this (and stop it reaching into swap)?

Answer 1

For one thing std::vector models a dynamic array so if you know that you'll always have 16 chars in partitions using std::vector is overkill. Use a good old C style array/matrix, boost::array or boost::multi_array.

To reduce the number of re-allocations needed for inserting/adding elements due to it's memory layout constrains std::vector is allowed to preallocate memory for a certain number of elements upfront (and it's capacity() member function will tell you how much).