c++ - ベクトル要素のペアワイズ比較を行うための標準アルゴリズムはありますか?

Question

私は基本的に、等しいかどうかのみをチェックできる順序付けられていない要素を持つ2つのベクトルを持っています。すべての n^2 ペアを比較し、1 つのベクトルのすべての要素が他のベクトルにあるかどうかを確認する std::equal のような標準アルゴリズムはありますか?

Answer 1

より大きなベクトルの最も安価な方法は、両方を並べ替えてから、等しいかどうかをテストする可能性が最も高いです

#include <vector>
#include <algorithm>

// ....

vector<yourType> v1;
vector<yourType> v2;

sort(v1);
sort(v2);
bool result = equal(begin(v1), end(v1), begin(v2));

Answer 2

ベクトルがデータを保持していると仮定すると、コピーまたはスワップにはコストがかかります。

#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_set>

typedef std::vector<std::size_t> Index;
typedef std::vector<int> Data;
inline void init(Index& index, const Data& data) {

    struct Less
    {
        const Data& data;

        Less(const Data& data)
        :   data(data)
        {}

        bool operator () (std::size_t a, std::size_t b) {
            return data[a] < data[b];
        }
    };

    index.reserve(data.size());
    for(size_t i = 0; i < data.size(); ++i) {
        index.push_back(i);
    }
    Less less(data);
    std::sort(index.begin(), index.end(), less);
}

int main(){

    Data d0 { 1, 0, 4, 2, 5, 3 };
    Data d1 { 5, 2, 3, 0, 4, 1 };

    if(d0.size() == d1.size()) {
        Index i0;
        Index i1;
        init(i0, d0);
        init(i1, d1);
        for(std::size_t i = 0; i < d0.size(); ++i) {
            std::cout << d0[i0[i]] << " == " << d1[i1[i]] << std::endl;
            if(d0[i0[i]] != d1[i1[i]]) {
                std::cout << "Not equal" << std::endl;
                return 1;
            }
        }
    }
    std::cout << "Equal" << std::endl;
    return 0;
}