簡單的類層次結構
以靜態表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等。