我正在寻找一种可以存储元素列表的数据结构,同时还允许O(n)
对给定元素的索引进行子查找,对给定索引的元素进行索引查找,以及在索引处进行插入。
元素是密集的(整数0..n
)并且是唯一的,但是没有排序。
例如,在Rust中,该数据结构将像这样使用:
fn main() {
let mut list = List::new();
list.extend(vec![5, 2, 0, 4, 1, 3]);
assert_eq!(list.get(2), 0);
assert_eq!(list.get(3), 4);
assert_eq!(list.index_of(0), 2);
assert_eq!(list.index_of(4), 3);
}
O(√n)
操作将是可以接受的,O(log n)
将是理想的。我在这里画一个空白。任何帮助,不胜感激!
出于兴趣,您是否在Rust中实现了此功能,如果是,它是开源的吗?我当时正考虑出于兴趣而去解决这个问题,并了解有关此数据结构的更多信息。
@Jason我确实已经在Rust中实现了它,但是不幸的是我无法开源(还!)。