[c++] テンプレートクラスに対するstd::hashの特殊化

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
purin52002
記事: 235
登録日時: 7年前
連絡を取る:

[c++] テンプレートクラスに対するstd::hashの特殊化

#1

投稿記事 by purin52002 » 7年前

お世話になっております。
今回はhashの特殊化方法について質問があります。

例えば自作クラスに対してhashを特殊化する場合は

コード:

class MyClass//自作クラス
{
public:
    int x;
};

template<>
struct std::hash<MyClass>
{
    size_t operator()(const MyClass &obj)
    {
        rerturn obj.x;
    }
};
このように特殊化できると思います。

ここで自作クラスがテンプレートクラスだった場合はどのように書けばよいのでしょうか?
特に自作クラスが2つ以上の型を扱う場合について教えてもらいたいです。

コード:

template<typename T,typename U>
class MyClass//自作クラス
{
public:
    T x;
    U y;
};

template<typename T,typename U>//テンプレート引数が多いためエラー
struct std::hash<MyClass<T,U>>
{
    size_t operator()(const MyClass<T,U> &obj)
    {
        rerturn (size_t)obj.x;
    }
};

template<>
struct std::hash<MyClass<T,U>>//T,Uが定義されていないためエラー
{
    size_t operator()(const MyClass<T,U> &obj)
    {
        rerturn (size_t)obj.x;
    }
};
具体的に現状の説明をしますと、
pair<T,U>(T、Uはテンプレート引数)をキーとしてgoogleのsparse_hash_mapを使おうと思っています。
そこでpair<T,U>に対するhash関数を作成しようと思いましたがhashの特殊化ができずに困っております^^;
オフトピック

コード:

//こんなコードにしたい
namespace std
{
    template<>
    struct hash<pair<T,U>>
    {
        size_t operator(const pair<T,U> &obj)
        {
            const size_t C=997;
            return C*hash<T>(obj.first)+hash<U>(obj.second);
        }
    };
}
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

Math

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#2

投稿記事 by Math » 7年前

本来であれば、C++11 で標準に使用できるようになった便利な連想配列クラス は hash_map のようなクラス名になるべきであったが、そのような名前のライブラリが数種公開されていたので、 それらとの衝突を避けるために[ unordered_map ]という名前になった。
それで勘違いされていると思います。
「連想配列クラス」とは検索可能なキーと、キーに対応する値の組(ペア)を要素とするコンテナクラスで、 保持している要素から、キーを指定して値を高速に取り出せるクラスのことです。

例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。 名前から年齢への写像(mapping.)のようなものなので map というクラス名を持ちます。
unordered_map とよく似たクラスとして、std::map というものもあります。 map は 二分木 を使っているために、キーから要素を取り出す処理時間が O(log N) で、そこそこ高速である。
それに対し、unordered_map クラスは O(1) で、さらに高速である。これは、unordered_map が ハッシュテーブル で実装されているからです。
ただし、unordered_map はその名前の通り、要素を順序付けできないという欠点があるので、 順序付けが必須の場合は map を使うことになります。
「参考」
unordered_map は C++標準ライブラリに含まれており、「#include <unordered_map>」を記述することで利用可能になる。

名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。
#include <unordered_map> // ヘッダファイルインクルード
int main()
{
std::unordered_map<std::string, int> mp; // ローカル変数として、mp を生成
.....
}

#include <unordered_map> // ヘッダファイルインクルード
using namespace std; // 名前空間指定
int main()
{
unordered_map<string, int> mp; // ローカル変数として、mp を生成
.....
}


宣言・初期化

単純な宣言

std::unordered_map オブジェクトを生成するには「std::unordered_map<キー型, 値型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する連想配列を識別するための名前のことだ。変数名と言ってもよい。 unordered_map はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。

unordered_map が vector や list 等の通常コンテナクラスと異なるのは、コンテナに入る要素の型を2つ指定するところだ。
最初の型はキーとなるものの型で、string や int 型などいろいろな型を指定できる。 ただし、どんな型でも指定できるかというとそうではなく、ノードのハッシュ値を計算可能でないといけない。
数値(整数、浮動小数点数)、ポインタ、std::string はハッシュ関数が予め定義されているので、そのまま使用することが出来る。
std::unordered_map<double, int> mp; // 浮動小数点数 → 整数の連想配列


vector 等はそのままではキーの型として指定できないが、テンプレートパラメータの3番目にハッシュ関数オブジェクトを指定してやれば大丈夫だ。

下記は、vector<int> 用のハッシュ関数オブジェクトの定義例だ。
class HashVI { // ハッシュ関数オブジェクト
public:
size_t operator()(const vector<int> &x) const {
const int C = 997; // 素数
size_t t = 0;
for (int i = 0; i != x.size(); ++i) {
t = t * C + x;
}
return t;
}
};

std::unordered_map<vector<int>, int> mp1; // ビルドエラー
std::unordered_map<vector<int>, int, HashVI> mp2; // ビルドOK


値型の方には特に条件は無い。どんな型・クラスでもたいてい使える。

下記は、string 型をキーとし、int 型を値とする連想配列 mp を宣言している例だ。
std::unordered_map<std::string, int> mp; // string → int の連想配列 mp の宣言


このようにして宣言したオブジェクトの要素数は 0、つまり空だ。要素を追加する方法は次の章で説明する。

< > は何だ?と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。 深入りはせず、現在のところはキーと値の型をこういう書き方で指定すると無条件で覚えてほしい。

http://qiita.com/sokutou-metsu/items/60 ... 4ff023ec72

アバター
tk-xleader
記事: 158
登録日時: 13年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#3

投稿記事 by tk-xleader » 7年前

もしかしてpairはstd::pairでしょうか?
仮にstd::pairだとすると、std名前空間で特殊化できるのはユーザー定義型依存型に限定されるので、それは未定義の動作を引き起こします(少なくとも、C++14の時点で、ユーザー定義型に依存さえしていれば、部分特殊化は許されるようになってはいますが)。

その上で、std::hashに対する部分特殊化の方法ですが、普通にstd名前空間内で部分特殊化をすれば大丈夫です。

コード:

template<typename T,typename U>
class MyClass{
};

namespace std{
	template<typename T,typename U>
	struct hash<MyClass<T,U>>{
		std::size_t operator()(const MyClass<T,U>&){
			return 0; // ここは本質じゃないので省略。
		}
	};
}
オフトピック
追記:

コード:

template<typename T,typename U>
struct std::hash<MyClass<T,U>>{
	std::size_t operator()(const MyClass<T,U>&){
		return 0;
	}
};
上記のような書式は、C++11で新しく導入された文法ですので、コンパイラのバージョンによっては対応できていないかもしれません。

アバター
purin52002
記事: 235
登録日時: 7年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#4

投稿記事 by purin52002 » 7年前

Mathさん
お早い回答ありがとうございます。
いただいた回答は私の想像していたものと少し違いましたがおかげでいいアイデアが浮かびました。^^

tk-xleaderさん
回答ありがとうございます。
おかげで何とか解決できたと思います。

私が実際に書いていたコードなんですが、

コード:

template<typename S,typename A>
class QLClass
{
public:
    using SA=std::pair<S,A>;
    using Q=double;
protected:
    google::sparse_hash_map<SA,Q,hash<SA>,eqstr> q_table;
};

template<typename S,typename A>
struct std::hash<QLClass<S,A>::SA>
{
    size_t operator()(const QLClass<S,A>::SA &sa){return 0;}
};
というものでした。

これだとhashのテンプレート引数が多すぎると怒られたのですが、

コード:

template<typename S,typename A>
struct std::hash<std::pair<S,U>>
{
としたところ怒られなくなりました。

なぜ怒られなくなったのかはわかりませんがとりあえず怒られなくなったので解決ということにしたいと思います。

解決にはしましたが、上のコードでなぜ怒られたのか、なぜ怒られなくなったのかをわかりやすく説明していただけると幸いです。^^;
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^


アバター
tk-xleader
記事: 158
登録日時: 13年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#6

投稿記事 by tk-xleader » 7年前

コード:

template<typename S,typename A>
struct std::hash<typename QLClass<S,A>::SA>
{
    size_t operator()(const typename QLClass<S,A>::SA &sa){return 0;}
};
SAはテンプレート引数に依存する型なので、型名であることを明示するためにtypenameを付ける必要があります。
オフトピック
std::hashに対してstd::pair<T,U>についての特殊化を用意するのは、規格上未定義な動作をするコードとなります。それはQLClass内でusingで別名を定義して、その別名からやった場合も同様です。

sleep

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#7

投稿記事 by sleep » 7年前

purin52002 さんが書きました:解決にはしましたが、上のコードでなぜ怒られたのか、なぜ怒られなくなったのかをわかりやすく説明していただけると幸いです。^^;

コード:

//17.4.3.1 Reserved names によれば、std名前空間で定義されている型に対する特殊化または部分特殊化は,
//宣言が外部リンケージを持つユーザ定義の名前に依存しつつ、特殊化がtemplateの要求を満たしていれば問題ない、とのことなので、
//条件を満たしていれば、ユーザー定義の型を #include <functional> より前に定義することで可となる。
template<typename S, typename A>
class QLClass
{
public:
    //templateの暗黙のインスタンス化
    //typedef、using、ポインタは、クラスの完全な型を必要としない不完全型なのでtemplateの暗黙のインスタンス化は発生しません。
    //インスタンス化が不要な不完全型のtemplateメンバが実体化されないのは、規格上の仕様です。
	using SA = std::pair<S, A>;
	using Q = double;
protected:
	google::sparse_hash_map<SA, Q, hash<SA>, eqstr> q_table;
};


#include <functional>


//class templateの部分的特殊化
//不完全型である非型実引数の型(QLClass<S, A>::SA)は、部分的特殊化のテンプレート仮引数(typename S, typename A)に依存してはならない、という規格上の仕様です。

//Error
template<typename S, typename A>
struct std::hash<typename QLClass<S, A>::SA>
{
	size_t operator()(const typename QLClass<S, A>::SA &sa) { return 0; }
};

//OK
template<typename S, typename A>
struct std::hash<QLClass<S, A>>
{
	size_t operator()(const QLClass<S, A> &sa) { return 0; }
};

//OK
template<typename S, typename A>
struct std::hash<std::pair<S, A>>
{
	size_t operator()(const std::pair<S, A> &sa) { return 0; }
};

sleep

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#8

投稿記事 by sleep » 7年前

sleep さんが書きました: ユーザー定義の型を #include <functional> より前に定義することで可となる。
これは現状ではもう関係ないですね。
一部のコンパイラ依存だった過去の話なので忘れてください。

アバター
purin52002
記事: 235
登録日時: 7年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#9

投稿記事 by purin52002 » 7年前

おお!なんかガチ勢の方がたくさん来てくださってて恐縮です^^;

Mathさん
classを使わずにstructを使うのは元のstd::hashがstructだからです。
classもstructも処理速度は変わらない(と思う)ので、まあどっちでもいいかな~、と^^;
僕は[struct=publicメンバしか持たないclass]という認識だったのですが、もし違うようでしたらご教授ください。<(_ _)>

tk-xleaderさん
typenameをつければよかったんですね。早速実装してみます!
と思いきや、、、sleepさんはtypenameつけてもerrorが出るとおっしゃっていますね^^;
とりあえずやるだけやってみます。

ところでofftopicでの内容なんですが、
コンパイルでは怒られないけど、実行するとエラーが出るということでしょうか?

sleepさん
たくさんコメントを付け加えていただきありがとうございます。
なにぶん未熟なもので5回ぐらい読み直して半分ぐらい理解しました。(たぶん^^;)

要はテンプレートクラスはコンパイル時に定義されるから、
QLClass<S,A>::SAで特殊化しようとしても「その型なんですか?」みたいなことになってるっていうことでしょうか?
違ってたら申し訳ないんですけどもう一度わかりやすく教えていただけると幸いです。^^;
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

Math

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#10

投稿記事 by Math » 7年前


 その通りですが、今の場合[struct=値型のclass]という認識だったのです。^^;
>値型の方には特に条件は無い。どんな型・クラスでもたいてい使える。

「C#では構造体とクラスは非常に似通った機能ですが、この2者を区別する一番大きなポイントが、値型か参照型かです。 構造体(struct キーワードを使って定義した型)は値型に、 クラス(class キーワードを使って定義した型)は参照型になります。」
https://msdn.microsoft.com/ja-jp/library/cc406735.aspxの最後にC++の場合の説明があります。

アバター
purin52002
記事: 235
登録日時: 7年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#11

投稿記事 by purin52002 » 7年前

Mathさん
なるほど、C#だと若干違うのですね。
C#はほとんど何も勉強していないのでよくわからないのですが、
classをnewを使ってインスタンスするっていうことは知ってます(どやぁ

。。。知ってる言葉を適当に並べただけです^^;

windowsフォームがc++に比べて作りやすいと聞いたことがあるのでいつかは手を出してみたい言語のひとつです^^
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

Math

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#12

投稿記事 by Math » 7年前

C#とJavaは2大言語といわれます。(C#はJavaを真似ていていまはPCでは抜き去っています)C#はC++とさほど変わらないです。#という字は++++に分解できます。C#とは(C++)++という事です。
C#はC++に比べ「超簡単」なので勉強しなくてもC/C++の初歩が分かれば使えますよ。VisualBasicはもっと簡単で早い話”C++の初歩が分かったらデタラメに書いても動く”のでVBをおぼえてC#に読み替えれば”楽”に覚えれます。私はExcelのVBAでプログラムを覚え(これまた簡単:プログラム自動生成を利用。資料豊富。現役で使えるバリバリの言語。最近WindowsAPIを利用する本もでた。)->VBー>C#ー>・・・いまC/C++です。
プログラムの基本はVBとさほど変わらないのでVBがいいとは思うのですが..大きな声で言うと語弊があるので...

http://dixq.net/forum/viewtopic.php?f=3&t=18870

sleep

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#13

投稿記事 by sleep » 7年前

purin52002 さんが書きました: 要はテンプレートクラスはコンパイル時に定義されるから、
QLClass<S,A>::SAで特殊化しようとしても「その型なんですか?」みたいなことになってるっていうことでしょうか?
部分特殊化の実引数でSA(Qの場合も同様)の型が必要となり、templateの定義時に実体化しようとしてます。
通常、typenameの付いている型は、明示的実体化などtemplateのインスタンス化時に実体化されますが、
templateの定義時に実体化が発生してしまっているため、テンプレート仮引数のS、Aの型が不明なので実体化できず失敗しています。

一応触れておきますが、
規格にある非型(non-type)というのは、通常、型ではなく値を指します。
部分特殊化の実引数で指定されたテンプレート仮引数に依存した不完全型についても、使用することで(非型とは少し状況が異なりますが)依存関係による問題が発生するので、おそらく明確な意味では仕様として未定義ではあると思いますが、部分特殊化の仕様としては「部分的特殊化のテンプレート仮引数に依存してはならない」が状況として一番近く該当すると思い、今回載せています。

アバター
tk-xleader
記事: 158
登録日時: 13年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#14

投稿記事 by tk-xleader » 7年前

purin52002 さんが書きました:typenameをつければよかったんですね。早速実装してみます!
と思いきや、、、sleepさんはtypenameつけてもerrorが出るとおっしゃっていますね^^;
よくよく考えればtemplate引数をテンプレートクラスの内部型で推論させることは不可能でした。ごめんなさい。
purin52002 さんが書きました:ところでofftopicでの内容なんですが、
コンパイルでは怒られないけど、実行するとエラーが出るということでしょうか?
エラーが出るかどうかすらわかりませんが、少なくともC++の規格上何らの保証もない(何が起こっても文句が言えない)ということです。限られた環境でのみコンパイルと実行ができればよいということであれば問題でもないとも言えますが。

アバター
purin52002
記事: 235
登録日時: 7年前
連絡を取る:

Re: [c++] テンプレートクラスに対するstd::hashの特殊化

#15

投稿記事 by purin52002 » 7年前

sleepさん
大変丁寧なご回答ありがとうございます。おかげでまた一つテンプレートに対する知識が増えました^^
C言語の山場がポインタだとしたらC++の山場はテンプレートですね^^;
constexprとtemplateをつかいこなせるようになれば「脱☆C++初心者」といったところでしょうか^^;

tk-xleaderさん
現在の環境では問題なく動いていますし、
プログラムがある程度完成してからちまちま修正していこうと思います。
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

閉鎖

“C言語何でも質問掲示板” へ戻る