Help us understand the problem. What is going on with this article?

unorderd_setやunorderd_mapのキーに任意のクラスを渡す

More than 1 year has passed since last update.

unorderd_setやunorderd_mapのキーに自作クラスを渡す方法です。
set,mapはこちら

mapでは不等号が必要でしたが、unorderd_mapでは等号とハッシュ関数が必要です。
等号はoperator==で良いのですが、ハッシュ関数の与え方がstd::unorderd_mapとboost::unorderd_mapでは違うようです。

クラスに同値、ハッシュをもたせる(std版)

まずはstd::unorderd_map版です。
std名前空間にテンプレートの特殊化を使ってhashという名前で定義します。

#include <unordered_map>

class Point{
public:
    int x, y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
    bool operator==(const Point &left) const {return this->y == left.y;}
};

namespace std{
    template<>
    class hash<Point>{
        public:
        size_t operator () ( const Point &p ) const{ return p.y;}
    };
}

int  main(){
    typedef std::unordered_map<Point, int> PointMap;
    PointMap pmap;
    pmap.insert(PointMap::value_type(Point(0,0), 0));

    return 0;
}

クラスに同値、ハッシュをもたせる(boost版)

続いて、boost::unorderd_map版です。
こちらはhash_valueという名前の関数を自作クラスと同じ名前空間に定義します。
今回の場合だとPointがグローバル名前空間なので、hash_valueもグローバル名前空間に定義しています。

#include <boost/unordered_map.hpp>
#include <unordered_map>

class Point{
public:
    int x, y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
    bool operator==(const Point &left) const {return this->y == left.y;}

//  こう書くのもありかも
//  friend size_t hash_value(Point const& p) { return p.y; }
};

size_t hash_value(Point const& p) {
    return p.y;
}

int  main(){
    typedef boost::unordered_map<Point, int> PointMap;
    PointMap pmap;
    pmap.insert(PointMap::value_type(Point(0,0), 0));

    return 0;
}

テンプレートの引数で指定する

テンプレートに関数オブジェクトを渡す方法です。
ハッシュ関数、イコール関数の順序で渡すことだけ注意すれば難しくありません。
こちらはstd::unordered_mapもboost::unordered_mapも同じ方法です。

#include <unordered_map>
#include <boost/unordered_map.hpp>

class Point{
public:
    int x, y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
};

struct PointHashY{
    size_t operator()(const Point &p) const{return p.y;}
};

struct PointEqualY{
    bool operator()(const Point &left, const Point &right)const{return left.y == right.y;}
};

int  main(){
    typedef std::unordered_map<Point, int, PointHashY, PointEqualY> PointMap;

//  boost::unordered_mapでも同じ指定方法
//  typedef boost::unordered_map<Point, int, PointHashY, PointEqualY> PointMap;

    PointMap pmap;
    pmap.insert(PointMap::value_type(Point(0,0), 0));

    return 0;
}

コンストラクタで指定する

コンストラクタの引数で指定する方法です。
unorderd_mapの場合、第一引数が最初に確保しておくサイズなので、それにだけ注意します。

#include <unordered_map>
#include <boost/unordered_map.hpp>

class Point{
public:
    int x, y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
};

int  main(){
    typedef std::unordered_map<Point, int, size_t (*)(const Point&), bool(*)(const Point&,const Point&)> PointMap;

//  boost::unordered_mapでも同じ指定方法
//  typedef boost::unordered_map<Point, int, size_t (*)(const Point&), bool(*)(const Point&,const Point&)> PointMap;

    PointMap pmap(0, [](const Point&p)->size_t{return p.y;}, [](const Point&l,const Point&r){return l.y == r.y;});

//  decltypeを使った版
//  auto h = [](const Point&p)->size_t{return p.y;};
//  auto eq = [](const Point&l,const Point&r){return l.y == r.y;};
//  typedef std::unordered_map<Point, int, decltype(h), decltype(eq)> PointMap;
//  PointMap pmap(0, h, eq);

    pmap.insert(PointMap::value_type(Point(0,0), 0));

    return 0;
}

ハッシュ関数の作り方

ハッシュ関数ですが、boostにハッシュを作る便利なものがあるのでこれを使うといいでしょう。
hash_valueはintやstringはもちろん、配列、vector、tuple、mapなどにも対応しています。

#include <boost/functional/hash.hpp>

size_t hash_value(const Point &p){
    using boost::hash_value;
    using boost::hash_combine;

    size_t seed = 0;
    hash_combine(seed, hash_value(p.x));
    hash_combine(seed, hash_value(p.y));
    return seed;
}
izmktr
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした