属性よりも大きい要素のベクトルオブジェクトのバイナリ検索

Question

私はクラスXの要素が多いベクトルを持っています。 このベクトルの要素の最初の出現を見つける必要があります.Sattrribute1> someVariableです。 someVariableは修正されません。バイナリ検索を行うにはどうすればよいですか？ （C++ 11/C++ 14ではなく）。私は検索関数std :: binary_searchを書くことができます（これは理想的には平等のチェックを意味します）が間違っていますか？高速検索のための正しい戦略は何ですか？

Answer 1

std::binary_searchを成功させるには、範囲をソートする必要があります。 std::binary_search、std::lower_boundはソートされたコンテナで動作します。したがって、新しい要素をvectorに追加するたびに、ソートしておく必要があります。あなたの挿入でstd::lower_boundを使用することができます。この目的のために

：

class X; 
class XCompare 
{ 
public: 
    bool operator()(const X& first, const X& second) const 
    { 
     // your sorting logic 
    } 
}; 

X value(...); 
auto where = std::lower_bound(std::begin(vector), std::end(vector), value, XCompare()); 
vector.insert(where, value); 

そして再び、あなたはあなたのベクトルで検索するstd::lower_boundを使用することができます：std::lower_boundだった場合

auto where = std::lower_bound(std::begin(vector), std::end(vector), searching_value, XCompare()); 

はチェックすることを忘れないでください成功：

bool successed = where != std::end(vector) && !(XCompare()(value, *where)); 

または直接0要素がベクター内にあることだけを知りたい場合は、を入力します。ベクターは、定義により、バイナリサーチの述語に従ってソートされた順序にある場合

Answer 2

バイナリサーチのみ行うことができます。

"S.attribute1> someVariable"というベクトル内のすべての要素が、そうでないすべての要素の後に配置されている場合を除き、これはゲート外からすぐに始まります。

ベクター内のすべての要素が別の方法でソートされている場合、その「別の方法」が実装できる唯一のバイナリ検索です。

あなたが最初の場所であなたのソートされたベクトルを考え出すために、属性に厳しい弱い順序を指定するいくつかの並べ替え、の、コンパレータを使用している必要があり、彼らはと仮定すると：

class comparator { 

public: 
    bool operator()(const your_class &a, const your_class &b) const 
    { 
      return a.attribute1 < b.attribute1; 
    } 
}; 

std :: Bの

template< class ForwardIt, class T, class Compare > 
bool binary_search(ForwardIt first, ForwardIt last, 
        const T& value, Compare comp); 

：トリックは、あなただけでは、属性値を使用して検索したい場合は、あなたがdefined as followsあるstd::binary_searchで使用できるコンパレータを使用する必要があるということです要素<値またはCOMP（要素、値）である場合、すべての要素の

：それは、次の のすべての要件を満たさなければならないIE）[最初、最後、範囲を成功するためにinary_searchは、少なくとも部分的に、 注文する必要があります。真 そして！（値<要素）または！カンプ（値、要素は）

だから、唯一の要件はcomp(value, element)とcomp(element, value)ニーズが機能するということであるのも事実です。

class search_comparator { 

public: 
    bool operator()(const your_class &a, const attribute_type &b) const 
    { 
      return a.attribute1 < b; 
    } 

    bool operator()(const attribute_type &a, const your_class &b) const 
    { 
      return a < b.attribute1; 
    } 
}; 

さて、あなたはsearch_comparator代わりのcomparatorを使用することができるはずです：あなたがいる限り、あなたのコンパレータはそれに対処できるよう、検索するためにではなく、ベクトル全体の要素よりも、Tの属性値を渡すことができます属性値によるバイナリ検索を行います。

ベクトルが指定された属性でソートされていない場合は、私が言ったように、すべてのベットはオフです。その場合は、最初にstd::sortを明示的に使用するか、ベクトル要素をトラッキングするカスタムコンテナを明示的に、別々に、またそれを保持するメインベクターに加えてください。ポインタを使用すると、その場合は、代わりにポインタを参照する同様の検索コンパレータを使用して、ポインタ自体に対してバイナリ検索を実行できる必要があります。