稀疏向量

基于有序平坦数组的关联容器底层实现 更多...

类
struct	neforce::sparse_vector_iterator< IsConst, SparseVector >
	稀疏向量迭代器 更多...
class	neforce::sparse_vector< Key, Value, KeyOfValue, Compare, Alloc >
	稀疏向量容器 更多...

详细描述

基于有序平坦数组的关联容器底层实现

稀疏向量使用有序 vector 作为底层存储，通过二分查找提供 O(log n) 的查找操作。 插入和删除操作为 O(n)（需要移动元素），但迭代性能优异。

复杂度保证

操作	时间复杂度	说明
查找	O(log n)	二分查找
插入	O(n)	二分查找 + 元素移动
删除	O(n)	二分查找 + 元素移动
最小/最大	O(1)	有序数组首尾元素
迭代	O(1)	连续内存遍历

注解

本实现提供了两个插入策略：

• insert_unique：键必须唯一，重复键插入失败并返回已存在元素迭代器
• insert_equal：允许重复键，按插入顺序存储

警告

对稀疏向量的修改操作可能使所有迭代器失效（元素移动导致）。 比较函数对象（Compare）必须提供严格的弱序关系。