0

次の値を持つ2つのベクトルがv1あります。v2

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

それらが「等しい」かどうかをチェックするための最もSTLアプローチは何ですか？「等しい」とは、順序に関係なく内容が同じであることを意味します。ソートせずにこれを実行したいと思います。

std::map<double, int>私は、ベクトルの各要素を数えるために2つを構築することに傾倒していました。

必要なのは、アルゴリズムからのブール値のはい/いいえです。

何て言うの？

Stack Overflowでの他の会話は、ベクトルの並べ替えに頼っていますが、それは避けたいと思います。したがって、この新しいスレッド。

4

6 に答える 6

4

ベクトルの各要素をカウントアップするために、2 つの std::map を作成することに傾いていました。

これは、ソートされたベクトルを作成するよりもはるかに遅くなります。(これはソートによって強化されていることに注意してくださいstd::map 。赤黒ツリーまたは AVL ツリーを使用するだけです) マップは、挿入と検索が均等に混在するように最適化されたデータ構造です。しかし、あなたのユースケースは、一連の挿入とそれに続く一連のルックアップであり、重複はありません。

ベクトルを並べ替えて (または、ソース コピーを破棄することが許可されていない場合は、コピーを作成して並べ替えて)、ベクターの組み込み を使用しoperator ==ます。

于 2012-11-27T00:56:09.673 に答える
4

ベクトルを並べ替えて set_difference を呼び出すのが最善の方法です。コピーが重い場合、並べ替えられていない 2 つの配列の比較はさらに悪化しますか?

現在の配列をそのままにしたい場合は、現在の配列のコピーを作成できますか?

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

// can trade before copy/sort heavy work
if (v1.size() != v2.size()){
}     
std::vector<int> v3(v1);
std::vector<int> v4(v2);

sort(v3.begin(), v3.end());
sort(v4.begin(), v4.end());

return v3 == v4;
于 2012-11-27T01:04:34.837 に答える
3

何らかの理由でベクトルを並べ替えることができないと思います。おそらく、元の順序でまだ必要であるか、コピーするのに費用がかかるためです。それ以外の場合は、並べ替えてください。

ベクトルを任意の順序で表示できるように、各ベクトルに「ビュー」を作成します。これは、要素を順番に指すことから始まるポインターのベクトルを使用して行うことができます。次に、2 つのビューを並べ替えて、並べ替えられたビューを各ベクトルに生成します。次に、ビューの順序で 2 つのベクトルを比較して、2 つのビューを比較します。これにより、ベクトル自体のソートが回避されます。

于 2012-11-27T00:57:02.197 に答える
1

もともとはセットの観点から作業することを考えていました。それはあなたが実際に考えていることだからですが、それはソートを必要とします。これはO(n)、両方をハッシュマップに変換し、そこで等しいかどうかをチェックすることで実行できます。

于 2012-11-27T00:52:15.220 に答える
-1

このutilメソッドは、2つのint []を比較するのに役立ちます。問題が発生した場合は、お知らせください。

public static boolean compareArray（int [] v1、int [] v2）{

    boolean returnValue = false;

    if(v1.length != v2.length)
        returnValue = false;

    if(v1.length == 0 || v2.length == 0)
        returnValue = false;

    List<Integer> intList =  Ints.asList(v2);

    for(int element : v1){
        if(!intList.contains(element)){
            returnValue = false;
            break;
        }else{
            returnValue = true;
        }
    }
于 2012-11-27T02:03:14.333 に答える
-1

最初のベクトルを取得して、2 番目のベクトルの各要素と比較するだけです。

最初の値の 1 つの値が 2 番目の値で見つからない場合、ベクトルは異なります。最悪の場合、n = 最初のベクトルのサイズ、m = 2 番目のベクトルのサイズである O(n*m) 時間かかります。

于 2012-11-27T00:54:07.267 に答える