C++：効率的なカスタムデータの挿入と取得のためのデータ構造

Question

私は、int：pairのペアを維持する必要があるC++（Windows上）の状況を抱えています。開始値はユニークですこれには関係ない）。必要な 操作は次のとおりです。

• 挿入ペア
• はペアの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はメモリ）にも対応しています。

Answer 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; 
}