STL map变量的实际memory usage估算 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

STL map变量的实际memory usage估算

STL map变量的实际memory usage估算# Programming - 葵花宝典

c*a2008-04-26 07:04

1 楼

提交了学校申请了，希望能给我OFFER。。。。
我是个努力而有理想的人，有着回报社会的志气和干一翻事业的大气。。。。希望老天
爷眷顾我，能拿到OFFER和奖学金~~~~
blessing blessing:)

g*s2008-04-26 07:04

2 楼

比如声明这样一个变量
using namespace std；
map *nameMap = new(map);
... // 在nameMap里插入了1000个(string, int) pair
现在需要估算这时heap的size增加了多少？
估算如下：
本身sizeof(map<...>)是48个字节。
一个string s的size是 sizeof(string) + s.size()，假定字符串长度都是8，则是16。
一个int是4字节。
这样至少是48+1000*(4+16)=2048 bytes。
但是map是用rb_tree实现，加上开销是多少呢？看了一下source code，不太确定是不
是算对了。
每个node包含color, left, right, parent, key, value，其中(key, value)前面算过。
color 1 byte，三个指针，64位机器上，24字节，这样就是25byte。总的字节是：
48+1000*(4+16+1+24)=4548。
如果node是按8-byte

c*t2008-04-26 07:04

3 楼

bless

【在 c******a 的大作中提到】

: 提交了学校申请了，希望能给我OFFER。。。。
: 我是个努力而有理想的人，有着回报社会的志气和干一翻事业的大气。。。。希望老天
: 爷眷顾我，能拿到OFFER和奖学金~~~~
: blessing blessing:)

g*s2008-04-26 07:04

4 楼

查了源代码。_Rb_tree_node_base确实有alignment问题。另外Rb_tree还有一个size_type的字段，一个compare字段。
所以sizeof(map<>) = sizeof(_Rb_tree_node_base) + sizeof(size_type) + sizeof(void *) = 32 + 16 = 48.

16。

【在 g*********s 的大作中提到】

: 比如声明这样一个变量
: using namespace std；
: map *nameMap = new(map);
: ... // 在nameMap里插入了1000个(string, int) pair
: 现在需要估算这时heap的size增加了多少？
: 估算如下：
: 本身sizeof(map<...>)是48个字节。
: 一个string s的size是 sizeof(string) + s.size()，假定字符串长度都是8，则是16。
: 一个int是4字节。
: 这样至少是48+1000*(4+16)=2048 bytes。