これはよい考えですか？等価な比較が高速であるように、ベクトルからのポインタを合計するクラス

Question

私はこの場合、ポインタを含むいくつかのvectorのコレクションを持っています。ポインタの順序は特にありません。私はベクトルに同じポインタが含まれているかどうかをチェックする方法を考え出しています。

私はポインタを整数として解釈し、それらを合計するという考えを思いつきます。 2つのベクトルの和が同じ場合、含まれるポインタは同じでなければなりません。それは良い動作し、私は何の問題も見ていない。しかし、このアイデアが衝突して偽陽性を返す場合があります（実際に異なる場合、同じベクトルを報告する）。

私の質問は、この衝突を乗り切る方法がある場合ですか？

注：ベクトルの並べ替えはオプションではありません。

---

編集：私は多くのそのようなポインタのベクトルを持つことができました私のアプリケーションで 。そして今、そして1人がコレクションに参加しています（1000個のベクトルかもしれません）。これが起こると、他のベクトルが既に同じ要素をカバーしているかどうかを確認する必要があります。そうであれば、新人は捨てられる。どのポインタベクトルが既にコレクションに入っているかを把握するために、私は今ではstd::setを使用しています（私の実際のPtrHasherは、ここに示すより多くの演算子をサポートしています）。従って、一意性をチェックするために必要な操作は、1）すべてのポインタを線形的に合計し、2）一定時間内にセットをチェックする。

私のコメントで書いたように、私のアプリケーションでは、「何らかの」偽陽性（すでにカバーされていなくてもベクターを破棄）を処理できます。したがって、総和は私のために働く。私がこの質問をする理由は、誤検出を最小限に抑えるが、同じ性能を与える他の方法（またはより良い操作）が実際にある場合です。

以前の実装では、 "カバレッジチェック"のためにstd::setも使用されていましたが、パフォーマンスははるかに悪かったです。ここ

---

は私のコードである：

#include <iostream> 
#include <vector> 
#include <stdint.h> // std::uintptr_t 

using namespace std; 

template<typename T> 
class PtrHasher 
{ 
public: 
    PtrHasher(vector<T> v) : hash(0) { 
     for(const auto i : v) 
      add(i); 
    } 
    void add(T pointer) { 
     hash += reinterpret_cast<uintptr_t>(pointer); 
    } 
    bool operator ==(const PtrHasher<T>& other) const { 
     return hash == other.hash; 
    } 
private: 
    uintptr_t hash; 
}; 


int main() { 

    vector<int> values{0,1,2,3,4}; 
    vector<int*> ptr1{ &values.at(0), &values.at(2), &values.at(4) }; // points to 0,2,4 
    vector<int*> ptr2{ &values.at(4), &values.at(0), &values.at(2) }; // points to 4,0,2 i.e. same positions 
    vector<int*> ptr3{ &values.at(4), &values.at(3), &values.at(2) }; // points to 4,3,2 i.e. not quite the same position 

    PtrHasher<int*> hasher1(ptr1); 
    PtrHasher<int*> hasher2(ptr2); 
    PtrHasher<int*> hasher3(ptr3); 

    cout<< (hasher1==hasher2) <<endl; 
    cout<< (hasher1==hasher3) <<endl; 
    cout<< (hasher2==hasher3) <<endl; 

    return 0; 
} 

Answer 1

これは私が最終的に思いついたものです。ポインタを追加するのではなく、乱数エンジンをシードしてそのような数値を生成します。シードは常にポインタの値にリセットされるので、同じポインタは同じ乱数を生成しますが、ほぼ同じアドレスの隣のポインタは非常に異なる数を生成します。 これはまだ100％の保存ではありませんが、私の目的にとっては問題ありません。

/// Class for hashing ranges of pointers, such that they can be compared to a different hasher for containing (all) the same pointers, independent of their order. 
template<typename T> 
class PointerCollectionHash 
{ 
public: 
    /// Construct a hasher. 
    PointerCollectionHash() 
     : m_sum(0), 
      m_generator(0) 
    { 
     assert(std::is_pointer<T>::value && "ERROR: must be pointer type."); 
    } 

    /// Hashes each element within a range and adds it. last is the past-the-end item. 
    template<typename Iter> 
    void add(Iter first, Iter last) 
    { 
     for(; first!=last; std::advance(first, 1)) 
      add(*first); 
    } 

    /// Hashes a pointer and adds it. 
    void add(T pointer) 
    { 
     m_sum += hash(pointer); 
    } 

    /// Compares two hasher. Returns true if all their hashed pointers are equal, independent of order of hashing. 
    bool operator ==(const PointerCollectionHash<T>& other) const 
    { 
     return m_sum == other.m_sum; 
    } 

private: 
    /// Hashes a pointer. 
    std::uintptr_t hash(T pointer) 
    { 
     m_generator.seed(reinterpret_cast<std::uintptr_t>(pointer)); 
     return m_generator(); 
    } 

    /// Keeps the sum of the added pointers. 
    std::uintptr_t m_sum; 
    /// Use Mersenne Twister to obtain a "unique as possible"-hash for an given input. The Seed of the engine is set to the input and a number is generated. 
    std::mt19937_64 m_generator; 
}; 

Answer 2

和が同じであることができるにも二つのベクトルは異なるポインタを含む、例えば、ベクトルAは、{P1、P2}を含む、ベクトルBは、{P1が含ま+8、p2-8}。あなたが頼りにすることができる追加のプロパティがない場合、比較のためにベクトルからマップへの変換は解決策になるかもしれません。

bool compare(vector<int*> ptr1, vector<int*> ptr2) 
{ 
    map <int*, bool> mapForPtr1; 
    for each elememt in ptr1 
    { 
     mapForPtr1[element] = true; 
    } 

    for each element in ptr2 
    { 
     if (mapForPtr1[element] != true) 
      return false; 
    } 

    return true; 
} 

複雑さがNからLogNに少し上がります。しかし、一般的にソートするよりも少し速いです。