C ++：用于有效插入和检索自定义数据的数据结构

我在C ++（在Windows）中遇到了一些情况，我需要保留一组int：pair对，其中起始值是唯一的（我们不需要担心这一点）。 所需的操作是：

插入对

检索对X：这应该返回Y对，其中Y的开始<X的开始<X的结束<Y的结束。 如果Y不存在，则返回false。

基本的解决方案是简单地保留一组配对。 为了检索，我们将依次遍历该集来检查。 这是O（n）。

我正在寻找更好的解决方案。 我目前看到2个候选数据结构：

排序的矢量

STL的集合（内部实现为二叉查找树？）

排序向量：优点：可以自定义二进制搜索以支持检索操作。 这是O（logn）缺点：如何有效地插入一对新的维护排序顺序。 如何避免O（nlogn）的重新排序成本？

设置：优点：使用标准插入方法轻松插入。 这是O（1）？ 缺点：如何避免顺序搜索？ 如何比O（n）做得更好？

谢谢你的建议。

我也对任何其他能够有效的结构（第一个标准是速度;第二个是内存）都支持上述的两个操作。

---

目前还不清楚范围是否可以重叠，但如果它们不能，那么这应该起作用。 我已经包含了一个完整的测试例子。

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <map>

struct RangeContainer {
  typedef std::map<int,int> RangeMap;
  typedef std::pair<int,int> Range;

  void insert(const Range &range)
  {
    range_map.insert(range);
  }

  Range find(const Range &x) const
  {
    RangeMap::const_iterator iter = range_map.upper_bound(x.second);
    if (iter==range_map.begin()) {
      return invalidRange();
    }
    --iter;
    Range y = *iter;
    if (y.first<x.first && x.second<y.second) {
      return y;
    }

    return invalidRange();
  }

  static Range invalidRange()
  {
    return Range(INT_MAX,INT_MIN);
  }

  RangeMap range_map;
};


static void test1()
{
  RangeContainer c;
  typedef RangeContainer::Range Range;
  c.insert(Range(1,10));
  c.insert(Range(20,30));
  assert(c.find(Range(-5,-4))==c.invalidRange());
  assert(c.find(Range(1,10))==c.invalidRange());
  assert(c.find(Range(2,9))==Range(1,10));
  assert(c.find(Range(2,10))==c.invalidRange());
  assert(c.find(Range(11,19))==c.invalidRange());
  assert(c.find(Range(21,29))==Range(20,30));
  assert(c.find(Range(20,29))==c.invalidRange());
  assert(c.find(Range(21,30))==c.invalidRange());
  assert(c.find(Range(35,40))==c.invalidRange());
}

int main(int argc,char **argv)
{
  test1();
  return EXIT_SUCCESS;
}

链接地址: http://www.djcxy.com/p/87899.html

上一篇: C++: Data structure for efficient insertion and retrieval of custom data

下一篇: How to allow your data structure to take in objects of any class