一般集合键只保存整数且集合的大小不大时,采用整数集合作为其底层实现
结构
typedef struct intset {
//编码方式
uint32_t encoding;
//整数集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
- contents作为整数集合的底层实现,每个元素都是contents数组的一个项,各个节点从小到大排列,并且不会重复
- contents的项的大小不一定为uint8_t,具体是根据encoding的值来决定
整数集合的升级
- 当整数集合中的添加的元素大于现有所有元素的类型都要长时,会将contents中元素的类型进行升级
- 步骤:
- 首先会根据新加入元素的大小为现有的元素重新分配数组代销
- 将原来的元素,通过类型转之后,放入新数组的对应位置
- 将新元素添加入新集合
- 因为每次新添加元素时,可能会发生升级,会遍历所有的元素进行类型转换,所有时间复杂度为O(n)
升级带来的好处
- 提高了灵活性,一般数组中我们都会存储相同类型的int值,集合添加元素时,我们不需要关心是插入uint64还是uint32,intset自动适类型的转化
- 节省了内存空间:当数组中不存在uint64的数时,没有比要把数组初始化为uint64-t类型,这样节约了空间
降级
整数集合不支持降级,整数一旦进行升级之后,不能进行降级