6

私はノード構造体を持っています

struct Node{CString text, int id;};

ソートされたベクトルで。

ベクトルのバイナリ検索を実行して要素を見つけるアルゴリズムに関数があるかどうか疑問に思っています。

4

4 に答える 4

21

std::binary_search()コンテナに値が存在するかどうかを教えてくれます。

std::lower_bound()/std::upper_bound()値の最初/最後のオカレンスへの反復子を返します。

operator<これらのアルゴリズムが機能するには、オブジェクトを実装する必要があります。

于 2008-12-15T18:28:49.747 に答える
6

はい、「binary_search」 std::binary_search という関数があります

最初、最後、および値または述語を指定します。

サンプルはこちら

これをMartin York のoperator== と組み合わせれば問題ないはずです (代わりに、述語ファンクターを書くこともできます

于 2008-12-15T18:15:58.667 に答える
0

ソートされた vector<Node>
ではなく、マップを使用しないのはなぜですか。仕分けコンテナです。そのため、 std::find() を介してこれに対して行われた検索は、自動的に二分検索と同じプロパティを持ちます。

于 2008-12-15T18:30:03.880 に答える
0

std::equal_range並べ替えられたベクトル内の要素の範囲を検索するために 使用します。指定した引数に等しい要素のベクトルの範囲を指定して、イテレータstd::equal_rangeの a を返します。std::pair範囲が空の場合、アイテムはベクターに含まれておらず、範囲の長さからアイテムがベクターに出現する回数がわかります。

の代わりに int を使用した例を次に示しますstruct Node。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main(int argc, const char * argv[])
{
    std::vector<int> sorted = { 1, 2, 2, 5, 10 };

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
    // Outputs "5 5"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), 5);
    // Outputs "3 4"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), -1);
    // Outputs "0 0"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    return 0;
}

これを機能させるには、 forstruct Nodeを提供するか、コンパレータを に渡す必要があります。これを行うには、構造体を比較する引数としてラムダを指定します。operator < struct Nodestd::equal_rangestd::equal_range

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
                               [](Node lhs, Node rhs) { return lhs.id < rhs.id; });
于 2013-12-05T02:46:10.143 に答える