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