unordered_map
容器具有reserve
方法,因为它是使用桶而不是像map
一样的树来实现的。
一个桶是:
容器内部哈希表中的一个槽,元素被分配到其中基于键的哈希值。桶从0到(bucket_count-1)进行编号。 (source)
单个桶可以容纳可变数量的项目。这个数字基于load_factor
。当load_factor
达到一定阈值时,容器会增加桶的数量并重新哈希映射。
当您调用reserve(n)
时,容器将创建足够的桶以至少容纳n
个项。
这与rehash(n)
不同,后者直接将桶的数量设置为n
并触发整个哈希表的重建。
另请参见:C++ unordered_map中预分配桶空间
根据评论编辑
由于我不知道评论中提出的问题的确切答案,并且我的初步研究没有取得成果,因此我决定进行实验测试。
参考文献,问题归结为:
请解释一下为什么为n个元素保留桶与为n个元素分配内存是相同的。
根据这个回答,准确检索unordered_map
中分配空间的大小是棘手且不可靠的。因此,我决定利用Visual Studio 2015的诊断工具。
首先,我的测试用例如下:
#include <unordered_map>
#include <cstdint>
struct Foo
{
Foo() : x(0.0f), y(0.0f), z(0.0f) { }
float x;
float y;
float z;
};
int32_t main(int32_t argc, char** argv)
{
std::unordered_map<uint32_t, Foo> mapNoReserve;
std::unordered_map<uint32_t, Foo> mapReserve;
mapReserve.reserve(1000);
for(uint32_t i = 0; i < 1000; ++i)
{
mapNoReserve.insert(std::make_pair(i, Foo()));
mapReserve.insert(std::make_pair(i, Foo()));
}
return 0;
}
当注释指示时,我进行了内存快照。
结果如下:
快照A:
┌──────────────┬──────────────┬──────────────┐
| Map | Size (Bytes) | Bucket Count |
|
| mapNoReserve | 64 | 8 |
| mapReserve | 64 | 8 |
└──────────────┴──────────────┴──────────────┚
快照 B:
┌──────────────┬──────────────┬──────────────┐
| Map | Size (Bytes) | Bucket Count |
|
| mapNoReserve | 64 | 8 |
| mapReserve | 8231 | 1024 |
└──────────────┴──────────────┴──────────────┚
快照 C:
┌──────────────┬──────────────┬──────────────┐
| Map | Size (Bytes) | Bucket Count |
|
| mapNoReserve | 24024 | 1024 |
| mapReserve | 24024 | 1024 |
└──────────────┴──────────────┴──────────────┚
解释:
从快照中可以看出,一旦我们开始向地图添加元素,两个地图的大小都会增长,即使是调用了reserve
的那一个。
那么,reserve
是否提供了好处,即使仍然分配了内存?我认为有两个原因:(1)它为桶预先分配内存,(2)它可以防止需要rehash
,如前所述完全重建地图。
List_buy()
或BuyNode()
调用,最终调用了operator new()
和malloc()
。 - Mikubyte