1

C ++（Windows）で、開始値が一意であるint：pairのペアのセットを保持する必要がある状況があります（これを気にする必要はありません）。必要な操作は次のとおりです。

  • インサートペア
  • ペアXを取得します。これにより、Yの開始<Xの開始<Xの終了<Yの終了であるペアYが返されます。Yが存在しない場合は、falseを返します。

基本的な解決策は、単にペアのセットを保持することです。検索のために、チェックするセットを順番に繰り返します。これはO（n）です。

より良い解決策を探しています。現在、2つの候補データ構造が表示されています。

  1. ソートされたベクトル
  2. STLのセット（バイナリ検索ツリーとして内部的に実装されていますか？）

ソートされたベクトル：長所：検索操作をサポートするために二分探索をカスタマイズできます。これはO（logn）短所です：ソートされた順序を維持するために新しいペアを効率的に挿入する方法。O（nlogn）の再ソートコストを回避するにはどうすればよいですか？

セット：長所：標準の挿入方法を使用して簡単に挿入できます。これはO（1）ですか？短所：順次検索を回避する方法は？O（n）よりもうまくやるには？

アドバイスありがとうございます。

また、上記の2つの操作を効率的にサポートできる（1番目の基準は速度、2番目の基準はメモリ）他の構造も利用できます。

4

1 に答える 1

1

範囲がオーバーラップできるかどうかは明らかではありませんが、オーバーラップできない場合は、これで機能するはずです。テストを含む完全な例を含めました。

#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;
}
于 2012-04-18T04:41:07.440 に答える