有快速插入和快速搜索的排序序列最简单的DS是什么？

Question

我正在寻找一个易于实现的(在C++中)数据结构D，它维护一个排序的整数序列(或任何类似的对象)，具有快速插入和快速搜索(例如，可以检查X在D中，还是在get ith元素中)。Fast应该是像O(log(n))、O(1)或O(sqrt(N))这样的东西吗？

template<type T>
Class D {
  D(...) { ... }
  void insert(T x);
  int get_ith(int x);
  boolean check_x(T x);
}

目前，我知道AVL树，红色黑树，跳表，尝试，哈希。所有这些都需要非常复杂的解决方案，这些解决方案很难编写代码。尝试可能是最不复杂的。但是，很难做一些事情，比如删除元素和为trie选择一个字母表。

我希望探索新的解决方案，希望是简短和快速的。

提前谢谢你！

Answer 1

如果您知道整数值的上限，则只需取一段内存并使用集合中数字的设置位。

• 如果X在D: O(1)中
• 插入: O(1)
• 删除: O(1)

如果整数在最低值到最高值范围内稀疏，则迭代速度很慢。在这种情况下，内存消耗可能是不可接受的。