1、整數(shù)集合(intset)當一個集合鍵只包含整數(shù)值元素沪蓬,且數(shù)量不多時彤钟,底層是整數(shù)集合,可以保存int16 int32 int64
contents數(shù)組是整數(shù)集合的底層實現(xiàn)跷叉,整數(shù)集合每個元素都是contents數(shù)組的一個項逸雹,從小到大排序,無重復項 length:元素數(shù)量 encoding:intset_enc_16 intset_enc_32? intset_enc_64
2云挟、升級
2.1梆砸、集合添加新元素,新元素的類型比集合所有元素類型都要長時园欣,需要進行升級(upgrade)帖世,升級分為三步
2.2、第一步沸枯,根據(jù)新元素類型日矫,擴展集合底層數(shù)組空間大小赂弓,并且為新元素分配空間
第二步、將底層數(shù)組現(xiàn)有的所有元素轉(zhuǎn)換成與新元素相同的類型哪轿,并將類型轉(zhuǎn)換后的元素放置到正確的位置上拣展,放置過程,繼續(xù)維持底層數(shù)組有序性不變
第三步缔逛、將新元素添加到底層數(shù)組里面
2.3备埃、因為每次向整數(shù)集合添加新元素都可能會引起升級,每次升級都要對所有已有元素進行類型轉(zhuǎn)換褐奴,所以添加新元素時間復雜度是o(N)
3按脚、升級的好處
3.1、一提升整數(shù)集合的靈活性
因為c語言是靜態(tài)類型語言敦冬,為了避免類型錯誤辅搬,通常不會將兩種不同類型的值放在同一個數(shù)據(jù)結(jié)構(gòu)里面
3.2、盡可能地節(jié)省內(nèi)存
int_16 會判斷升級為int_32,或者int_64,而不是直接使用int_64
4.整數(shù)集合不支持降級操作