2

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>?

4

2 回答 2

5

map 是一个基于节点的容器，因此每个元素都是单独分配的。没有“预分配”之类的东西，它没有任何优势（即花费的总时间相同）。

于 2012-08-23T10:39:35.650 回答
3

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.

于 2012-08-23T10:37:34.517 回答