Back to page

− Links

 Print 

技術系備忘録​/C++​/std.set map系の比較関数の新機能 :: シンクリッジ

xpwiki:技術系備忘録/C++/std.set map系の比較関数の新機能

どういうタイトルがよいかすごく悩みましたが諦めて、結局よくわからないタイトルになりました。
タイトル無くてもいいかなくらいに思ったのですが、とりあえず先に進ませて下さい。




C++ には std::map があります。すごく便利です。
がしかし実際の設計で少々悩むケースもあるかなーと思います。例えば・・・。




本。っていう情報があります。
本のタイトルや値段、ISBN(書籍ID的なコード)などなどを持ちます。

struct CBook
{
	std::string		title;
	unsigned int	price;
	std::string		isbn;
	std::string		description;
	・
	・
};

こういうクラスを作ったとします。
で、たくさんある本の中から ISBN で検索する必要がある場合、

std::map<std::string,CBook>	mapIsbnToBook;

こんな感じで、ISBN 文字列をキーにした map を作りたくなると思います。




もちろんこれでOKなんですが庶民感情としては、
値(CBook)の中にある isbn と、map のキーは同じものなのに別々に持たすっていうのは冗長だから一か所に出来ないかな・・・と思ってしまいます。

そこで思いつくのは以下みたいなコード

struct CIsbnLess
{
	bool operator()(const CBook &a,const CBook &b)const{
		return a.isbn < b.isbn;
	}
};

std::set<CBook,CIsbnLess> setBooks;

こんな感じにすれば CBook::isbn がキーを兼ねるので、余計な情報を持たずに済みます。

がしかし、このやり方だと検索するときが厄介です。
やりたいことは以下のように

bool exist = setBooks.find("1234567") != setBooks.end();

ISBN 文字列で検索(find)したいのですが、現実には以下のように

CBook key;
key.isbn = "1234567";
bool exist = setBooks.find(key) != setBooks.end();

find の引数にはキーの型(CBook)で渡さなきゃならず、さすがに使い勝手悪すぎです。
がしかし、文字列での find はどう頑張っても出来ないので途方に暮れてしまう訳です。






そこで少し視点を変えて、std::set ではなく std::vector を使ってみようと以下のようなコードを試す訳です。

struct CIsbnLess
{
	bool operator()(const CBook &a,const CBook &b)const{
		return a.isbn < b.isbn;
	}
	bool operator()(const std::string &a,const CBook &b)const{
		return a < b.isbn;
	}
	bool operator()(const CBook &a,const std::string &b)const{
		return a.isbn < b;
	}
};

std::vector<CBook> books;
	// ・・・
std::sort(books.begin(), books.end(), CIsbnLess());
	// ・・・
bool exist = std::binary_search( books.begin(), books.end(), "1234567", CIsbnLess() );	// "1234567" を検索

これはこれでOKな気がします。
が、欲を言い出すと少々不満が出てしまいます。

というのは、この情報を使う側の立場になったときに、
books の std::vector<CBook> っていう型は、std::set と比べて、
・ISBN でソート済のリストであるということが読み取れない。
・ソートキー(ISBN)が重複してないとは読み取れず、重複してない保証がないので、ダブってる場合の考慮が必要かな?と思ってしまう。

っていうあたりが主な理由でちょっと合わないかなという感じです。
やっぱり折角の C++ なので型定義で出来るだけ意図を表したいので・・・困りました・・。






しかし!C++ の進化っぷりはスゴイです。実は C++14 で set::set/map 系で以下のようなコードが書けるようになってました。
(最近知りました。猛省。そしてこの記事で一番言いたいところです)

struct CIsbnLess
{
	typedef void is_transparent;		// ←コレが重要
	bool operator()(const CBook &a,const CBook &b)const{
		return a.isbn < b.isbn;
	}
	bool operator()(const std::string &a,const CBook &b)const{
		return a < b.isbn;
	}
	bool operator()(const CBook &a,const std::string &b)const{
		return a.isbn < b;
	}
};

std::set<CBook,CIsbnLess> setBooks;
	// ・・・
bool exist = setBooks.find("1234567") != setBooks.end();	// 可能!

これはすごく便利です!

裏技っぽい印象を受けてしまいますが C++14 では is_transparent を書くことでイケるようになります。
こちらのサイト[1] に記載がありますので参考にしてみてください。いつも参考にしているサイトです。ありがとうございます。そして C++ の仕様決めに携わってる方々にも感謝です。


というわけでコレで解決です!
今後も使えるシーンではバリバリ使っていこうと思いました。
ありがとうございました!








と、したいのですが、以下少々愚痴を・・。

上記コードを使った場合、例えば本の金額を変更したい場合、以下のコードはエラーになります。

std::set<CBook,CIsbnLess> setBooks;
	// ・・・
auto i = setBooks.find("1234567");
if( i != setBooks.end() ){
	i->price = 500;		// エラー
}

std::set/map の仕様でキーは const 扱いになります。
set/map のキーは変更されたらイカンので const 扱いにしますっていうごもっともな理由なのですが、このケースでこの縛りは結構キツイです。

もちろん const_cast しちゃえば変更出来てしまいますが、C++ 委員会に盾突くといいますか、天に唾するようで少々気が引けます・・。

そこで、正攻法な解の一つとしてはポインタにすることだと思います。

using std::shared_ptr;

struct CIsbnLess
{
	typedef void is_transparent;
	bool operator()(const shared_ptr<CBook> &a,const shared_ptr<CBook> &b)const{
		return a->isbn < b->isbn;
	}
	bool operator()(const std::string &a,const shared_ptr<CBook> &b)const{
		return a < b->isbn;
	}
	bool operator()(const shared_ptr<CBook> &a,const std::string &b)const{
		return a->isbn < b;
	}
};
std::set<shared_ptr<CBook>,CIsbnLess> setBooks;
auto i = setBooks.find("1234567");
if( i != setBooks.end() ){
	(*i)->price = 500;		// OK
}

これで一応解決できます。
がしかし、ポインタにすると別のとこで困ることが・・・例えば、

// 書店から本一覧を取得
const std::set<std::shared_ptr<CBook>,CIsbnLess> &setBooks = bookShop.GetBooks();

と、こんな風に、書店側からすれば読み取り専用の情報として提供したいんですが、以下のように

for( auto &i : setBooks ){
    i->price = 0;		// OK
}

変更出来てしまいます。アウチ。
もちろん cast して返しちゃうのもアリかと思うんですが、やっぱり少々気が引けます・・。

もう一つの解としては、変更したい箇所を愚直に insert し直す方法もあります。今回の例程度ならアリかも・・・



個人的希望としては std::set/map のキーを 非const にする方法があればいいんですが・・・・こればっかりは如何ともしがたいです。




というわけで結論。

std::map<std::string,CBook>	mapIsbnToBook;

この例ではコレが無難かもということで結局一番最初に戻りました。
ありがとうございました!








とまぁ、そもそもこんな事で悩むこと自体が間違っているのかもしれないんですが、ちょっと面白いネタかなと思って読み物風にまとめてみました。
ありがとうございました。


Last-modified: 2019-02-18 (Mon) 00:04:53 (JST) (292d) by takatsuka