c++ - 自然な並べ替え順序のない 2 つの std::vector の違い

Question

2 つの の差を取得する効率的な方法を探していstd::vectorsます。それらに含まれるオブジェクトには、自然な順序はありません。私にできる最善のことは、平等をテストすることです。std::set_differenceこれはオプションを除外するようです。

ネストされた 2 つの反復子内のオブジェクトを比較するよりも良い解決策はありますか?

Answer 1

ベクトルのプロパティを利用できます。ベクトルには連続したメモリ割り当てがあります。つまり、ベクトルには1つの大きなメモリ空間が予約されています (通常は使用されるよりも大きい)。派手な最適化を行わなくても、メモリ空間を直接比較できます。

C++0x には data() メソッドがあり、そのメモリ空間の先頭に直接アクセスできます。また、 memcmpを使用して、ベクトル内のすべてのデータを比較できます。

std::vector<char> vector_1;
std::vector<char> vector_2;

// data in to vector_1
// data in to vector_2

if(!memcmp(vector1.data(),vector_2.data(),SIZE_OF_BUFFER_TO_COMPARE))
{
    std::cout <<< "equal vectors" << std::endl;
} 

Answer 2

目標は、可能な肯定的な一致をグループ化することにより、同等性テストの数を減らすことです。

私が考えることができる最善の方法は、最初のベクトルでハッシュマップを作成し、次にハッシュマップから 2 番目のベクトルのすべての要素を差し引くことです。これは、要素に対してまともなハッシュ関数を考え出す必要があることを意味します。

当然のことながら、ポインタを格納していて、等価述語がそれに基づいている場合、そのポインタの整数値に基づいてハッシュを作成することもできます。

良いハッシュ関数とは?を参照してください。.

コメントで述べたように、代替の可能性は、要素の特定の属性に順序付けを確立し、それを使用して同等の可能性を減らすことです。最初に両方のベクトルをソートする必要がある場合があります。