2

vector<node>10000 個のオブジェクトを含むオブジェクトがあるとします。

vect[0] to vect[9999]

struct node
{
    int data;
};

そして、たまたまノード 99 にあるこのデータ (「444」) を含むベクター ID を見つけたいとしましょう。

すべての要素をループしてから使用するために forループを実行する必要がありますか?

if (data == c[i].data)

それとももっと早い方法がありますか？私のデータは別個のものであり、他nodeの s で繰り返されないことを考慮してください。

4

5 に答える 5

3

この回答では、利用可能な他のコンテナよりもを使用するという十分な情報に基づいた決定を下したとstd::vector仮定しています。

すべての要素をループするために、本当に for ループを実行する必要がありますか?

forいいえ、要素を見つけるためにループを回す必要はありません。コンテナ内の要素を見つける慣用的な方法は、標準ライブラリのアルゴリズムを使用することです。自分でロールする必要があるかどうかは、状況によって異なります。

あなたが決めるのを助けるために...

代替案 1:

std::find()データ型に適した等価コンパレータが必要です。nodeこれは次のように単純な場合があります。

bool operator ==(node const& l, node const& r)
{
    return l.data == r.data;
}

次に、 を指定するrequired nodeと、要素を検索できます。これは、反復子(または、単純な古い配列を使用している場合はポインター) を返します。indexが必要な場合は、少し計算が必要です。

auto i = std::find(v.begin(), v.end(), required);
if (i != v.end())
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

代替案 2:

a の作成nodeが高すぎる場合、または等値演算子がない場合、より良いアプローチはstd::find_if()、述語を取る を使用することです (ここでは簡潔なのでラムダを使用しますが、この回答のようにファンクターを使用できます)。

// Alternative linear search, using a predicate...
auto i = std::find_if(v.begin(), v.end(), [](node const& n){return n.data == 444;});
if (i != v.end())
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

それとももっと早い方法がありますか？

繰り返しますが、それは依存します。-loopstd::find()と同じように、std::find_if()線形時間 ( O ( n )) で実行します。for

そうは言っても、std::find()orを使用してもコンテナーへのランダム アクセスやインデックス作成は必要ありませんが (イテレーターを使用します)、ループstd::find_if()と比較して少し余分なコードが必要になる場合があります。for-

代替案 3:

実行時間が重要で、配列がソートされている場合 (たとえば、 )、対数時間 ( O (log n ))std::sort()で実行されるバイナリ検索を実行できます。指定された値以上の最初の要素のバイナリ検索を実装します。残念ながら、述語は必要ありませんが、次のようなデータ型に適した小なりコンパレータが必要です。std::lower_bound()node

bool operator <(node const& l, node const& r)
{
    return l.data < r.data;
}

呼び出しは iterator に似ており、 iteratorstd::find()を返しますが、追加のチェックが必要です。

auto i = std::lower_bound(v.begin(), v.end(), required);
if (i != v.end() && i->data == required.data)
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

アルゴリズム ライブラリのこれらの関数は、反復子を提供する任意のコンテナーで動作するため、別のコンテナーへの切り替えは、std::vectorテストと保守が迅速かつ簡単になります。

決めるのはあなたです！

【デモンストレーションはこちら】

于 2013-02-17T02:42:28.547 に答える
0

を使用する必要がありますstd::find。ベクトルについて事前に何も知らない場合 (ソートされている場合など) 、線形複雑度 ( O(n)) よりも高速になることはありません。

于 2013-02-16T20:54:40.657 に答える
0

コンテナ内の要素を見つけたい場合vectorは、正しいデータ構造ではありません。std::setまたはなどの順序付きコンテナーを使用する必要がありますstd::map。これらのコンテナー内の要素は順序付け (ソート) されてO(log (n))いるため、順序付けられていないコンテナーの線形時間とは対照的に、時間内に要素を見つけることができます。

于 2013-02-16T20:56:25.133 に答える
0

使用std::find:

vector<int>::Iterator it = find (vect.begin(), vect.end(), 444);

ソートされたベクトルがある場合は、高速化できることに注意してください。

于 2013-02-16T20:57:08.647 に答える
0

適切な解決策は、構造体のインスタンスがある場合に、構造体に追加のint indexメンバーを追加して、データからインデックスへのマッピングを提供することです。そのような場合、たとえば、アイテムを削除するときにインデックスの更新を処理するクラスでnodeラップする必要があります(このような場合、削除される要素に先行する要素のインデックスから 1 を引くだけで十分です)。ベクトルが要素の数を変更しない場合、それは問題ではありません。それ以外に、構造体のインスタンスのサイズを大きくできない場合は、. コンテナーを繰り返し処理して 1 つのアイテムを見つけることは、非常にまれに行う必要があり、何かを複雑にすることが面倒でない限り、あまりスマートではありません。std::vectorNodeVectorstd::map

于 2013-02-16T21:05:17.623 に答える