开发项目的某些部分，我需要实现一个类似结构的数据集，它应该允许我根据最小-最大键值获取子集：
ConstainedSet <- Set((key,value)*)
Subset <- ConstainedSet.Match(Constraint = "val1 <= key < val2")
那么Subset应该只包含ConstainedSet 中符合“val1 <= key < val2”限制的那些元素。也就是说，那些 key 大于或等于val1但小于val2的元素。
例如，如果我们有一个像这样的子集：
ConstrainedSet <- {(1,hand),(2,eye),(3,nose)}
然后是这样的操作：
Subset <- ConstainedSet.Match(Constraint = "1 <= key < 3")
应该结果生成这个子集：
Subset <- {(1,hand),(2,eye)}
我开发了一个解决方案，其中每个元素都存储在一个三元组向量中，例如
(minKey,maxKey+1,value)
我保持这个向量按minKey和maxKey排序，minKey顺序比maxKey顺序优先级高。然后每次调用“Match”都会对该向量执行二进制搜索。
如果我没记错的话，最坏情况的时间复杂度是：
- 每次调用“Match”的时间为 O(N)。
- O(N) 用于插入。
其中 N 是集合中的元素个数。
有更好的解决方案吗？