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の一時オブジェクトが生成されてしまいます。
この問題に対処するため、map、multimap、set、multisetの以下の関数に、メンバ関数テンプレート版が追加されます。
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<>>を使おう」
となります。
