简单的类层次结构
以静态表unorered_set为例,工作原理见下图


简单的效率测试

Sample是本处讲述的双数组unordered_xxx,standard是编译器的unordered_xxx,boost1.50表示它的unordered_xxx

测试环境:

Win7 x64 Ultimate (Kernel 6.1.7601), g++4.6.3 64bit (-O3), Intel Xeon E31230 3.2GHz, Hynix DDR3-1333 ECC DIMM 4GBx2 Dual Chanel, P8B-X (Intel Cougar Point C202), WD5000AADS-00M2B0, AMI BIOS 12/26/2011, Sapphire Radeon HD 5750 GDDR5 1GB, Samsung SyncMaster BX2250(H) (Digital) 1920x1080@60Hz

测试结果:

静态表

unordered_map (64位随机数1百万个)

unordered_multimap(32位随机数1百万个)

unordered_set(字符窜253674个单个窜长200以上)

unordered_multiset(字符窜81536个单个窜长低于20)

 

Sample

standard

boost1.50

Sample

standard

boost1.50

Sample

standard

boost1.50

Sample

standard

boost1.50

插入

ms

67.8525

180.929

212.671

50.9687

150.95

199.598

85.0928

73.3596

142.383

27.8756

18.9638

16.4688

查找

72.4412

62.884

93.388

48.6442

51.0842

87.3587

68.6096

63.8798

145.687

21.9548

10.7675

12.969

删除

168.938

179.079

289.612

126.764

164.087

285.196

135.997

66.9415

136.711

53.0243

12.6135

9.6811

内存

MB

32

40

52

24

36

52

81.2

85

85.1

9.3

9.9

10.6


动态表

unordered_map (64位随机数1百万个)

unordered_multimap(32位随机数1百万个)

unordered_set(字符窜253674个单个窜长200以上)

unordered_multiset(字符窜81536个单个窜长低于20)

 

Sample

standard

boost1.50

Sample

standard

boost1.50

Sample

standard

boost1.50

Sample

standard

boost1.50

插入

ms

129.523

270.424

262.842

92.9128

256.856

291.372

143.654

127.587

149.45

38.2729

26.3448

18.4614

查找

70.2685

61.971

94.4114

46.1028

51.017

85.9693

75.2463

66.1863

149.023

22.7871

11.7799

14.482

删除

148.089

178.864

295.409

110.26

163.184

297.173

133.305

70.1459

145.462

42.8773

13.0186

10.0248

内存

MB

32.2

40

52

24.2

36

52

82.7

85.1

85

7.8

9.5

9.6

 

Visual Studio 2012编译运行结果:

静态表

unordered_map (64位随机数1百万个)

unordered_multimap(32位随机数1百万个)

unordered_set(字符窜253674个单个窜长200以上)

unordered_multiset(字符窜81536个单个窜长低于20)

 

Sample

standard

Sample

standard

Sample

standard

Sample

standard

插入

ms

59.999

188.476

50.9861

174.008

142.694

146.148

27.3501

20.3516

查找

48.1513

78.2629

33.3826

55.69

80.589

136.024

19.8892

16.9792

删除

163.05

215.432

121.721

199.238

205.691

204.848

40.771

13.3655

内存

MB

32

60.7

24

45.4

96.5

111

5.7

10.8








动态表

unordered_map (64位随机数1百万个)

unordered_multimap(32位随机数1百万个)

unordered_set(字符窜253674个单个窜长200以上)

unordered_multiset(字符窜81536个单个窜长低于20)

 

Sample

standard

Sample

standard

Sample

standard

Sample

standard

插入

ms

118.021

273.997

91.9337

252.155

249.369

243.164

41.6276

24.7281

查找

45.8492

78.085

33.4889

58.0067

92.2518

138.624

21.8552

16.6643

删除

144.097

217.688

103.813

201.557

192.211

209.361

30.966

13.7178

内存

MB

32.5

60.7

24.7

45.4

97.6

111

5.7

8.8

编译:

尽管尽可能使用C++98的语法,但编译Sampleunordered_***代码仍然需要比较新的编译器(老编译器无能为力),例如g++4.6.3以后版本,VC++2012等。