1

すべての要素をフォームの構造体として含むリストがあります

typedef struct person_node{
    string name;
    string country;
}person;

std::list<person> list;

リストはすでにperson name でソートされています。

これで組み込みのbinary_search()関数を使用するにはどうすればよいですか?

このbinary_search()を数値のみをデータとして持つリストで使用する方法は既に知っていますが、そのようなリストに対してどのように使用できるのだろうか。

このバイナリ関数を次のように使用しています。

binary_search (list.begin(), list.end(), value, compare_function);

私が知らないのは、「リスト内の特定の名前を探す必要がある場合、 valueの代わりに何を入力すればよいですか?」ということだけです。

また、見つかった場合は、イテレータがそのノードを指すようにします。

4

2 に答える 2

6

person検索するを含む を入力nameします。

binary_searchまた、はめったに役に立たないことに注意してください(アイテムがコレクション内のどこにあるかではなく、アイテムが存在するかどうかを示すだけstd::listです。 で二重に役に立ちstd::listません。提供）。

したがって、おそらく必要なのはstd::vector<person>or であり、おそらく orでstd::deque<person>検索したいと思うでしょう。そして、それぞれが見つけたアイテムへのイテレータを返し、そのオブジェクトにアクセスできるようにします。std::lower_boundstd::upper_boundstd::lower_boundstd::upper_bound

于 2013-01-14T14:37:24.853 に答える
2

3 番目の項目は、検索対象を呼び出し可能な方法で説明します。

compare_function(*iter, value )

また

compare_function( value, *iter )

whereiterはコレクション内の有効な反復子です。これは、ソートされたままにするためにリストの前に表示する必要がtrueある場合は最初のケースで返され、2 番目のケースではその逆になります。*itervalue

したがって、これらのオーバーロードの両方をサポートしている場合は、実際にstringは 3 番目のパラメーターとしてa を渡すことができることに注意してください。compare_functionプロトタイプは次のとおりです。

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

T が反復子の値型である必要はありません。

ちなみに、 astd::listに使用できますが、各std::advanceステートメントO(N)がO(N log N). レギュラーstd::findでも速いでしょう。

重複を許可する場合、または重複を許可しない場合は、vectororを使用します。multisetset

また、アイテムが存在し、アイテムが見つからないかどうかについてbinary_searchも返しますtrue/false(そのため、国はわかりません)。重複がある場合はstd::equal_range、そのようなすべての値のリストを取得するために使用できます。あなたが使用できない場合は、std::lower_boundあなたの名前と同じかそれ以上の名前を持つ最初のアイテムへのイテレータを取得し、それが等しいかどうかを確認してください。

于 2013-01-14T14:36:06.963 に答える