问题描述
根据此,您不能为std::map
保留空间:
According to this you cannot reserve space for std::map
:
由此可见,std::map
为什么缺少cppreference.com上的reserve()
方法.但是,std::unordered_map
确实具有reserve()
方法,但是当我尝试将其与operator[]
,insert()
或emplace()
一起使用时,尽管我调用了reserve()
首先.
From this it is obvious why std::map
would lack a reserve()
method, which it does on cppreference.com. However, std::unordered_map
does have a reserve()
method, but when I try to use it with operator[]
, insert()
or emplace()
they all go to allocate memory despite me having called reserve()
first.
这是怎么回事?为什么reserve()
无法正确保留所需的空间?而且,就像在映射中一样,您不能事先分配内存,那么为什么std::unordered_map
甚至首先具有reserve()
方法?
What's up with this? Why won't reserve()
properly reserve the required space? And if it's as with the map that you cannot allocate memory beforehand, then why does std::unordered_map
even have a reserve()
method in the first place?
推荐答案
unordered_map
容器具有reserve
方法,因为它是使用存储桶而不是像map
中的树来实现的.
The unordered_map
container has a reserve
method because it is implemented using buckets, and not a tree as in map
.
一个桶是:
单个存储桶可容纳可变数量的项目.此数字基于 load_factor
.当load_factor
达到某个阈值时,容器会增加存储桶数并重新整理地图.
A single bucket holds a variable number of items. This number is based on the load_factor
. When the load_factor
reaches a certain threshold, the container increases the number of buckets and rehashes the map.
调用 reserve(n)
时,容器会创建足够的存储桶来至少容纳n
个项目.
这与直接设置数字的 rehash(n)
相反到n
的存储桶,并触发整个哈希表的重建.
This is in contrast to rehash(n)
which directly sets the number of buckets to n
and triggers a rebuild of the entire hash table.
另请参阅:在C ++ unordered_map中预分配存储桶
根据评论进行编辑
由于我不知道对评论中提出的问题的确切答案,并且由于我的初步研究未能证明富有成果,因此我决定进行实验性测试.
As I do not know the exact answer to the question posed in the comments, and as my preliminary research did not prove fruitful, I decided to test it experimentally.
作为参考,问题可归结为:
For reference, the question boils down to:
根据此答案,准确地获取unordered_map
中分配空间的大小是棘手且不可靠的.因此,我决定使用Visual Studio 2015的诊断工具.
According to this answer, accurately retrieving the size of the allocated space in an unordered_map
is tricky and unreliable. So I decided to make use of Visual Studio 2015's diagnostic tools.
首先,我的测试用例如下:
First, my test case is as follows:
#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;
// --> Snapshot A
mapReserve.reserve(1000);
// --> Snapshot B
for(uint32_t i = 0; i < 1000; ++i)
{
mapNoReserve.insert(std::make_pair(i, Foo()));
mapReserve.insert(std::make_pair(i, Foo()));
}
// -> Snapshot C
return 0;
}
在注释指示的地方,我拍摄了内存快照.
Where the comments indicate, I took a memory snapshot.
结果如下:
快照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
的地图,这两个地图的大小就会增大.
As you can see from the snapshot, it appears that both maps grow in size once we start adding elements to them, even the one that had called reserve
.
即使内存仍在分配,reserve
也会带来好处吗?我会说是,原因有两个:(1)它为存储桶预先分配了内存,并且(2)它可以避免需要rehash
的需求,如前所述,该rehash
完全重建了映射.
So does reserve
offer a benefit even though memory is still allocated? I would say yes for two reasons: (1) It pre-allocates the memory for the buckets, and (2) it can prevent the need of a rehash
, which as discussed earlier completely rebuilds the map.
这篇关于为什么std :: unordered_map具有保留方法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!