Pre-Allocated List

Question

I have two lists of objects

list<QC> qcB;
list<QC> qcS;

and am using emplace_back() to insert items into them. Since I realized that inserting the items was taking too long, I started searching about allocators, which I have never used, to see if I was able to make things run faster. I read somewhere that I would be able to get the default allocator for the list, and allocate space on it ahead of time, so I tried allocating space in one of the lists:

qcB.get_allocator().allocate(100000);

I am unsure if this was supposed to work or not, but the truth is that the emplace_back() is taking the same amount of time with both the lists, even though one of them is allocating space beforehand.

Is this supposed to work? Should this be done in a different way, instead of trying to allocate space in the default allocator? I am clearing the lists from time to time, may this be affecting the allocated space?

Thank you for your help.

Answer 1

If you are talking about the Standard Library list, it is typically a linked list algorithm or similar.

Assuming that you have done a good profiling and the insertion is indeed the problem, and assuming that you only want to do emplace_back calls. Then use a vector, which allows you to call reserve and should have a little more performance.

vector<QC> qcB;
qcB.reserve(10000);

But I fear that your actual bottleneck is the object QC initialization, and this cannot be reserved. In this scenario, you could preinitialize the objects (in case it makes sense to initialize the object and then put actual data in it).

Like this (quick&dirty draft):

vector<QC> qcB;
qcB.resize(10000);

for (int i = 0; i < 10000; ++i) {
    qcB[i].populate_object();
}