6

次のコードをコンパイルすると、ハッシュに関連するエラーが表示されました。

int F_no_meaningA(unordered_set<vector<int>>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>> setVec; 
}

$ g++ --version
g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

$ g++ $1.cpp -o $1 -g -Wall -Weffc++ -pedantic -std=c++0x

/tmp/ccCQFQ4N.o: 関数内 `std::__detail::_Hash_code_base

, std::vector >, std::_Identity > >, std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code( std::vector > const&) const': /usr/include/c++/4.6/bits/hashtable_policy.h:753: std::hash<std::vector<int, std::allocator<int> > ::operator()(std::vector<int, std::allocator<int> >) const' /tmp/ccCQFQ4N.o: In function std::__detail::_Hash_code_base への未定義参照、std::vector >、std::_Identity > > , std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node >, false> const* , unsigned int) const': /usr/include/c++/4.6/bits/hashtable_policy.h:763: `std::hash > ::operator()(std::vector >) const' collect2: ld への未定義参照1 つの終了ステータスを返しました

そこで、以下の独自の Hash を導入して問題を解決します。

質問 1 > に対して独自のハッシュを提供する必要があるのはstd::unordered_setいつですか? に対して独自の等価関数を提供する必要があるのはいつstd::unordered_setですか?

struct HashVector : unary_function<vector<int>, vector<int>::size_type> {
  vector<int>::size_type operator()(const vector<int>& vec) const {
    vector<int>::size_type sum = 0;
    for(int i : vec) {
      sum = sum*37 + hash<int>()(i);
    }
    return sum;
  }
};

int F_no_meaningB(unordered_set<vector<int>, HashVector>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>, HashVector> setVec; 
}

警告: 基本クラス 'struct std::unary_function, unsigned int>' に非仮想デストラクタ [-Weffc++] があります

質問 2 > g++ が構造体 HashVector について上記の警告を表示するのはなぜですか?

ありがとうございました

4

2 に答える 2

6

独自のハッシュをいつ提供する必要がありstd::unordered_setますか?

標準ライブラリが提供するハッシュを持たない型を使用している場合。たとえば、vector<int>.

g++ が構造体 HashVector について上記の警告で不平を言うのはなぜですか?

-Weffc++仮想デストラクタを持たないクラスから継承するたびに、(やや熱心すぎる) 警告を要求していたからです。継承のほとんどの用途 (つまりポリモーフィズム) では、そうしたくないでしょう。ただし、この場合、継承はクラスにいくつかの定義を挿入するために使用されている (または、悪用されていると言う人もいるかもしれません) ため、警告は問題を示していません。

のようなクラスstd::unary_functionは推奨されていないため、最善の解決策はそれをまったく継承しないことです。

于 2013-07-17T16:42:55.090 に答える
5

std::unordered_set に独自のハッシュを提供する必要があるのはいつですか?

標準では、主にプリミティブ型に対して、限られた数の特殊化のみが必要です。これは、これらのプリミティブ型には、実装が提供できる合理的なデフォルトの「万能」ハッシュ関数があるためです。カスタム型やコンテナーなどのより複雑な型には、明白な、または妥当な既定のハッシュさえないため、独自のものを提供する必要があります。値の型がサポートされていない場合は、ハッシュ関数の実装を提供する必要があります。

また、独自のハッシュ関数を提供するもう 1 つの理由は、unordered_set. ハッシュ テーブルのパフォーマンスは、テーブルに格納されている値の分布に関してハッシュ関数がどの程度適切であるかに大きく左右されます。より完全な説明があります。標準のデフォルトは万能のソリューションです。つまり、簡単で便利ですが、ほとんどの場合最適ではありません。

g++ が構造体 HashVector について上記の警告で不平を言うのはなぜですか?

これは主に、従来のオブジェクト指向プログラミング (基本クラスを派生クラスへの動的なポリモーフィック インターフェイスとして使用) に関連する警告を適用することの問題です。そのようなコンテキストでは、デストラクタを仮想として定義しないことはかなり重大な間違いです (これにより、基本クラス インスタンス (たとえば、delete base_ptr;) からの派生クラスの正しい破棄が可能になります)。Mike が示唆するように、これは-Weffc++有効になっています (ほとんどの場合、初心者レベルの従来の OOP スタイルの警告メッセージが適用されます)。ただし、コードでは、継承はジェネリック プログラミングのコンテキストで使用され、継承は非常に異なる方法で使用されます (ほとんどの場合、いくつかの基本的なプロパティと特性をクラスに吹き込むため)。この場合、基本クラスに仮想デストラクタがなくても問題ありません。これは、動的にポリモーフィックな設定ではなく、静的にポリモーフィックな設定で使用することを意図しているためです。

std::unary_functionまた、最新の標準 (C++11) では (およびその親戚) が廃止されたことにも注意してください。これは、最新の標準 ( <type_traits>、decltypeおよび型推論) によって提供される型イントロスペクションの機能強化によるものです。

于 2013-07-17T16:57:36.997 に答える