less<>を使えばよい。
問題
(名, 姓)のpair
(Alice, Acer) (Anna, Cork) (Bella, Bread) (Bella, Field) (Cherry, Card)
名が一つ与えられたときに姓が辞書順最小の人を見つけたい。
例えばBellaが2人いるが、Bellaの姓の辞書順最小のBreadを見つけたい。
setのほかの機能も使いたいのでこれらをsetで行いたい。
解法1
Bellaの一人目を見つけたいのでset::lower_boundが使えそう。
stringは偶然にも最小値を持つデータ型である。
空文字列が最小値なのでmake_pair("Bella", "")でlower_boundすれば見つかる。
解法2
空文字列を使わない方法がある
リファレンスのlower_bound(set::lower_bound - cpprefjp C++日本語リファレンス)を見るとc++14からsetの要素の型とは異なる型で使えるらしい。
template <class K> iterator lower_bound(const K& x)
// ERROR namespace std { bool operator<(const pair<string, string> &x, const string &y) { return x.first < y; } }; int main() { set<pair<string, string> > se; se.lower_bound(string("Bella")); }
リファレンスの備考を見るとset::findを読めとある。findを読むとis_transparentが必要だとある。これはless< void>には定義されている。
つまりエラーの原因は比較関数がless< pair< string, string> >であること。
// GOOD namespace std { bool operator<(const pair<string, string> &x, const string &y) { return x.first < y; } }; int main() { set<pair<string, string>, less<> > se; se.lower_bound(string("Bella")); }
解法3
自分で構造体にis_transparentを定義してもよい。
// GOOD struct Cmp { bool operator()(const pair<string, string> &x, const pair<string, string> &y) const { return x < y; } bool operator()(const pair<string, string> &x, const string &y) const { return x.first < y; } typedef void is_transparent; }; int main() { set<pair<string, string>, Cmp> se; se.lower_bound(string("Bella")); }
感想
set< string>と文字列リテラルを比較するための仕組みらしいが、このように使ってもいいものかどうか。