如何为std::map或QMap预分配内存？

Question

我正在开发一个程序，其中性能至关重要。在这里我使用了QMultiMap，这是Qt框架提供的一个类，类似于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();
}

我经常使用prepareMap()。当我想要优化时，将内存分配给heavilyUsedMap是有意义的。

实际上，容器：QVector<T>、QHash<Key, T>、QSet<T>、QString和QByteArray都提供了这种可能性，但QMap<Key, T>和QMultiMap<Key, T>不提供。

为什么会这样?我如何为QMap<Key, T>和QMultiMap<Key, T>预分配内存

Answer 1

它最有可能是由二进制搜索树支持的，所以预分配并不常见，因为它通常是一个链接结构，每个节点都根据需要动态分配。

如果顺序并不重要，请考虑使用散列映射，您可以进行预分配，通常它的性能也会更好。所以QHashMap<int, SomeClass>。

我还看到你的键类型是int，如果域足够小，你可以使用一个完美的散列，它本质上是一个数组。所以QVector<SomeClass>，它的性能甚至比散列映射更好。

Answer 2

map是一个基于节点的容器，因此每个元素都是单独分配的。没有“预分配”这回事，它也不会有任何优势(即总花费的时间是一样的)。