std::set::lower_boundでkeyと異なる型の値を渡す

less<>を使えばよい。

問題

(名, 姓)のpairがたくさんあってset< pair< string,string> >に格納されている。

(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>と文字列リテラルを比較するための仕組みらしいが、このように使ってもいいものかどうか。