CODEWITHSUNDEEP
c++qtstl
Martin Drozdik
Martin Drozdik

Reputation: 13303

How to preallocate memory for a std::map or QMap?

I am developing a program, where performance is critical. There I use a QMultiMap, which is a class provided by the Qt framework, similar to std::map. 

QMultiMap<int, SomeClass> heavilyUsedMap;

void prepareMap()
{
    ...
    heavilyUsedMap.reserve(nEntries); // There is no reserve.
    // fill heavilyUsedMap with a known number of entries.
}

void useMap()
{
    // computations
    heavilyUsedMap.clear();
}

I use prepareMap() a lot. When I want to optimize, it would make sense to allocate the memory for heavilyUsedMap .

Indeed the containers: QVector<T>, QHash<Key, T>, QSet<T>, QString, and QByteArray all provide this possibility, but QMap<Key, T> and QMultiMap<Key, T> don't.

Why is this so and how can I preallocate memory for the QMap<Key, T> and QMultiMap<Key, T>?

Upvotes: 2

Views: 4750

Answers (2)

Andrew Tomazos
Andrew Tomazos

Reputation: 68618

It's most likely backed by a binary search tree, so preallocation isn't common as it is usually a linked structure with each node dynamically allocated as required.

If order is not important consider using a hash map instead, you can preallocate and it is also more performant generally. So QHashMap<int, SomeClass>.

I also see your key type is int, if the domain is sufficiently small you can use a perfect hash which is essentially an array. So QVector<SomeClass>, which will be even more performant than a hash map.

Upvotes: 3

Kerrek SB
Kerrek SB

Reputation: 476980

The map is a node-based container, so each element is allocated separately. There is no such thing as "preallocation", and it would have no advantage (i.e. the total time spent would be the same).

Upvotes: 5

Related Questions