C++14 の transparent comparator について

あらまし

std::map<std::string, int> table; のようなコンテナがあったとして、table.find("hoge") で要素を検索した場合、std::string の一時オブジェクトが作られてしまい、無駄が生じるという問題がある。
C++14 以降ではこの問題への解決策が用意されており、std::map<std::string, int, std::less<>> table; とすると一時オブジェクトが作成されなくなる。
動作例

誰もが初見では面食らうであろうこの std::less<> がどのように機能するのか、また、これに対応したコンテナを自作するにはどうするのか、という話が以下になる。

Transparent Comparator

std::less の定義を見ると以下のようになっている。

template <class T = void>
struct less {
    constexpr bool operator()(const T& l, const T& r) const {
        return l < r;
    }
};

T のデフォルトパラメータが void であることから、std::less<> は std::less<void> であることがわかる。
では std::less<void> はどうなってるのかというと、以下のような特殊化が用意されている。

template <>
struct less<void> {
    template <class T1, class T2>
    constexpr auto operator()(T1&& l, T2&& r) const {
        return l < r;
    }

    using is_transparent = int;
};

std::less<std::string> の場合、operator() の引数はどちらも const std::string& になるため、table.find("hoge") とすると文字列リテラルは暗黙の変換により std::string の一時オブジェクトになる。
一方、std::less<void> はどちらの引数も任意の型を受け付けるようになっている。つまり、table.find("hoge") で std::string と const char* の文字列リテラルが直接 operator< で比較される。std::string と const char* は operator< が用意されているので、一時オブジェクトを挟むことなく比較ができるというわけだ。
この std::less<void> のような、どんな型でも受け付ける comparator は、transparent comparator などと呼ばれているそうだ。

コンテナ側の対応

comparator がどんな型でも受け付けるようになったのはいいが、コンテナ側も対応しないとそれを活かせない。しかも、互換性の都合から旧来の less<std::string> のような場合と less<void> の場合両方に対応する必要がある。
less<void> には using is_transparent = int; という型定義があるが、これはコンテナ側での判別のために用意されている。例えば、std::set の lower_bound() は大雑把に以下のような実装になっている。

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set
{
// ...

    iterator lower_bound(const Key& k)
    {
        return std::lower_bound(begin(), end(), k, Compare());
    }

    template <class K, class C = Compare, class = typename C::is_transparent>
    iterator lower_bound(const K& k)
    {
        return std::lower_bound(begin(), end(), k, C());
    }

// ...
};

comparator に is_transparent が定義されている場合、下のどんな型の k でも受け付ける版 lower_bound() が選択される。そうでない場合、旧来の Key 型のみを受け付ける lower_bound() が選択される。

当然これは lower_bound() に限った話ではなくて、upper_bound(), equal_range(), find() といった検索系のメンバ関数は同じように transparent comparator 対応版が用意されている。それぞれに const 版もあるので、合計 4 つのバージョンが存在している。
後付けゆえに仕方がない冗長さだが、std::set や std::map 互換のコンテナを自分で実装する場合、同じように 4 バージョンの lower_bound() などを実装するのが望ましいだろう。

なお、std::map の operator[] は transparent comparator に対応していないようなので注意が必要である。table["hoge"] の場合は依然として一時オブジェクトが生成される。

実装例

本記事の知見は flat_set を実装する過程で得た。
(flat set は要素がメモリ上で連続した std::set ライクなコンテナ。sorted vector とも呼ばれる)