6

メモリ内に 16 バイト幅のエントリの配列があります。各エントリは、2 つの 64 ビット整数フィールドで構成されます。エントリは、各エントリの最初の 64 ビット整数の数値に基づいてソートされています。最初にデータを std::vector にロードせずに、STL でこれをバイナリ検索することは可能ですか?

プレーンな配列で STL の lower_bound() メソッドを使用できることがわかりましたが、各エントリの 2 番目の 64 ビット フィールドを無視する必要があります。これは可能ですか？

4

3 に答える 3

7

を使用する必要はありませんがstd::vector<>、最初にデータを適切なデータ型に変換すると最も簡単です。

#include <cstdint>

struct mystruct
{
    std::int64_t first, second;
};

このデータを現在どのように保存しているかについての質問は不明ですが、上記のようなものだと思います。

operator<次に、データ型をオーバーロードできます。

#include <algorithm>

bool operator <(mystruct const& ms, std::int64_t const i)
{
    return ms.first < i;
}

int main()
{
    mystruct mss[10] = { /*populate somehow*/ };
    std::int64_t search_for = /*value*/;
    mystruct* found = std::lower_bound(mss, mss + 10, search_for);
}

または、カスタム コンパレータを定義して、それを に渡すこともできますstd::lower_bound。

#include <algorithm>

struct mystruct_comparer
{
    bool operator ()(mystruct const& ms, std::int64_t const i) const
    {
        return ms.first < i;
    }
};

int main()
{
    mystruct mss[10] = { /*populate somehow*/ };
    std::int64_t search_for = /*value*/;
    mystruct* found = std::lower_bound(mss,
                                       mss + 10,
                                       search_for,
                                       mystruct_comparer());
}

当然のことながら、C++11 では、コンパレーターの本格的なファンクターの代わりにラムダを使用できます。

于 2012-07-06T23:19:17.420 に答える
2 
struct Foo {
    int64_t lower;
    int64_t upper;
};

Foo arr[N];

Foo f;
f.lower = 42;

auto it = std::lower_bound(arr, arr + N, f,
    [](const Foo& lhs, const Foo& rhs){ return lhs.lower < rhs.lower; });
于 2012-07-06T23:23:32.313 に答える
0

はい、可能です。要素を適切な方法で反復するForwardIteratorの要件を満たすクラスを作成する必要があります（16バイト構造のポインターでうまくいく可能性があります）。次に、2番目の64ビットフィールドを無視して要素を比較するために、独自の比較を定義する必要があります。 詳細情報。

template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value, Compare comp );
于 2012-07-06T23:49:38.423 に答える