C++値の配列の要素のインデックスを取得

Question

これまで、私はベクトルに配列を格納し、ベクトルをループして一致する要素を見つけ、インデックスを返しました。

これをC++で行う方法はありますか？配列を格納するために私が使用するSTL構造体は、私にとって重要ではありません（ベクトルである必要はありません）。私の配列は一意でもあり（繰り返し要素なし）、順序付けされています（例えば、日付の順番が順番に並んでいます）。

Answer 1

要素がソートされているので、バイナリ検索を使用して一致する要素を見つけることができます。 C++標準ライブラリには、この目的で使用できるstd::lower_boundアルゴリズムがあります。私は明快さとシンプルさのために、独自のバイナリサーチアルゴリズムでそれを包むお勧めします：

/// Performs a binary search for an element 
/// 
/// The range `[first, last)` must be ordered via `comparer`. If `value` is 
/// found in the range, an iterator to the first element comparing equal to 
/// `value` will be returned; if `value` is not found in the range, `last` is 
/// returned. 
template <typename RandomAccessIterator, typename Value, typename Comparer> 
auto binary_search(RandomAccessIterator const first, 
        RandomAccessIterator const last, 
        Value    const& value, 
        Comparer     comparer) -> RandomAccessIterator 
{ 
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer)); 
    if (it == last || comparer(*it, value) || comparer(value, *it)) 
     return last; 

    return it; 
} 

（C++標準ライブラリはstd::binary_searchを持っていますが、それはbool返します。範囲はそれ以外の要素、falseが含まれている場合trueを。要素への反復子が必要な場合は役に立ちません）。

要素への反復子を取得したら、std::distanceアルゴリズムを使用して範囲内の要素のインデックスを計算できます。

どちらのアルゴリズムも、std::vectorと通常の配列の両方を含む任意のランダムアクセスシーケンスで同様に機能します。

Answer 2

値をインデックスに関連付けてインデックスをすばやく検索する場合は、std::mapまたはstd::unordered_mapを使用できます。データに対して実行する他の操作に応じて、これらを他のデータ構造（例えばstd::listまたはstd::vector）と組み合わせることもできます。例えば

、我々はまた、ルックアップテーブルを作成するベクトルを作成：

今

vector<int> test(test_size); 
unordered_map<int, size_t> lookup; 
int value = 0; 
for(size_t index = 0; index < test_size; ++index) 
{ 
    test[index] = value; 
    lookup[value] = index; 
    value += rand()%100+1; 
} 

をインデックスをルックアップするためにあなたは、単に：

size_t index = lookup[find_value]; 

をハッシュテーブルベースのデータ構造を使用して（たとえば、 unordered_map）はかなり古典的な空間/時間のトレードオフであり、多くのルックアップを行う必要があるときに、このような「逆」ルックアップ操作のバイナリ検索を行うことができます。もう1つの利点は、ベクトルがソートされていないときにも機能することです。

50000〜に要素を：私はすべてのベクトルに、線形検索とルックアップのためのunordered_mapを使用してジェームズのバイナリ検索コードを比較VS2012RCで迅速なベンチマークを行ってきた:-)楽しみのために

unordered_setは期待されるO（log N）の振る舞いを示しているバイナリサーチをoutpeformするが、unordered_mapはおそらくハッシュの衝突、おそらく実装によるO（1）の振る舞いを10000を超えて失う。問題。

EDIT：順序付けされていないマップのmax_load_factor（）は1であるため、衝突はありません。非常に大きなベクトルのバイナリ検索とハッシュテーブルの間のパフォーマンスの違いは、キャッシング関連であるように見え、ベンチマークのルックアップパターンによって異なります。

Choosing between std::map and std::unordered_map順序付けられたマップと順序付けられていないマップの違いについて説明します。