読者です 読者をやめる 読者になる 読者になる

C++14 連想コンテナの異種混合比較ルックアップ

C++

N3657 Adding heterogeneous comparison lookup to associative containers (rev 4)


なんだか意味のよくわからないタイトルですが、C++14では、連想コンテナでの不要なコピーをなくすための機能追加が行われます(Unordered連想コンテナは含みません)。
以下のようなコードを書いた場合、

std::set<std::string> s = /* ... */;
s.find("key");

find()関数の内部では、"key"のためにstd::stringの一時的なオブジェクトを作り、内部のキーと一時的なstd::stringオブジェクトとの比較を行います。これは本来不要な一時オブジェクトです。


これは、2つの原因があります。
ひとつは、find()関数のインタフェースです。これは以下のようになっています。

iterator find(const key_type& x); 

key_typeはここではキーの型std::stringです。このインタフェースのため、"key"が渡されるとstd::stringの一時オブジェクトが生成されてしまいます。
この問題に対処するため、mapmultimapsetmultisetの以下の関数に、メンバ関数テンプレート版が追加されます。

  • find()
  • count()
  • lower_bound()
  • upper_bound()
  • equal_range()

find()の場合は、以下のバージョンが追加されます。

template<typename K>
iterator find(const K& x);

template<typename K>
const_iterator find(const K& x) const;

もう一つの原因は、比較関数オブジェクトです。たとえば、連想コンテナのデフォルトの比較関数オブジェクトであるstd::lessは、この場合std::less<std::string>になるので、以下の関数呼び出し演算子を持ちます。

bool operator()(const std::string& a, const std::string& b) const;

このインタフェースもまた、一時オブジェクトが作られる原因になります。

2項演算関数オブジェクトをよりジェネリックに」で追加されたstd::less<void>は、関数呼び出し演算子ジェネリック版を持っています。そのため、find()メンバ関数のテンプレート化に加えて、このジェネリック版を使えば、問題は解決します。

std::set<std::string, std::less<>> s = /* ... */;
s.find("key");

互換性維持のため、既存の動作は変えないほうがいいだろう、とのことで、今回は2項関数オブジェクトのジェネリック版を使いましょう、という結論になります。


詳細仕様として、std::less<void>std::greater<void>のような2項関数オブジェクトのvoid版(ジェネリック版)には、is_transparentというメンバ型が追加されます。

template <>
struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
      -> decltype(std::forward<T>(t) < std::forward<U>(u));

    typedef unspecified is_transparent; // 追加
};

is_transparentメンバ型を持つ2項関数オブジェクトを連想コンテナに指定した場合にのみ、find()系関数のジェネリック版を使用できます。


と、このように混みいった変更がありますが、結論としては、
「一時オブジェクトが問題になる場合は、std::set<Key, std::less<>>std::map<Key, Value, std::less<>>を使おう」
となります。