From 719b2df9d1996283acaac1d13476bcbc7da42154 Mon Sep 17 00:00:00 2001 From: Philipp Unterbrunner Date: Fri, 26 May 2017 22:54:46 -0700 Subject: [PATCH] Added folly::hint_emplace_iterator to folly/Iterator.h Summary: In contrast to Container::insert(), for any STL container class, Container::emplace() does not have an overload that takes a Container::iterator as its first parameter. (The reason is to prevent ambiguity with respect to target class constructor parameters.) Instead, container classes have a separate emplace_hint() function. Because of this separation, folly::emplace_iterator would fail to perform hinted emplacement in constructs where std::insert_iterator would perform hinted insertion. This diff adds a new class, folly::hint_emplace_iterator(), and corresponding convenience function, folly::hint_emplacer(), which calls Container::emplace_hint() rather than Container::emplace(). It would have been trivial to copy&paste the existing folly::emplace_iterator class and simply replace the emplace() call with emplace_hint(), but I did not like the large amount of code repetition. So I decided to do some refactoring and move the emplace()/emplace_hint()/emplace_front()/emplace_back() calls into separate trait classes, and replace emplace_iterator()/hint_emplace_iterator()/front_emplace_iterator()/back_emplace_iterator() with suitable type aliases. Reviewed By: yfeldblum Differential Revision: D5097860 fbshipit-source-id: c0b733131a0d0d21fc0a8b08ad655142c6a41c19 --- folly/Iterator.h | 266 ++++++++++++++++++++---------------- folly/test/IteratorTest.cpp | 57 ++++++++ 2 files changed, 206 insertions(+), 117 deletions(-) diff --git a/folly/Iterator.h b/folly/Iterator.h index 54d1dbae..c4fe9c1c 100644 --- a/folly/Iterator.h +++ b/folly/Iterator.h @@ -150,19 +150,79 @@ decltype(auto) get_emplace_arg(const Args& args) noexcept { namespace detail { /** - * Common typedefs and methods for folly::emplace_iterator, - * folly::front_emplace_iterator, and folly::back_emplace_iterator. Implements - * everything except the actual emplace function call. + * Emplace implementation class for folly::emplace_iterator. */ -template +template +struct Emplace { + Emplace(Container& c, typename Container::iterator i) + : container(std::addressof(c)), iter(std::move(i)) {} + template + void emplace(Args&&... args) { + iter = container->emplace(iter, std::forward(args)...); + ++iter; + } + Container* container; + typename Container::iterator iter; +}; + +/** + * Emplace implementation class for folly::hint_emplace_iterator. + */ +template +struct EmplaceHint { + EmplaceHint(Container& c, typename Container::iterator i) + : container(std::addressof(c)), iter(std::move(i)) {} + template + void emplace(Args&&... args) { + iter = container->emplace_hint(iter, std::forward(args)...); + ++iter; + } + Container* container; + typename Container::iterator iter; +}; + +/** + * Emplace implementation class for folly::front_emplace_iterator. + */ +template +struct EmplaceFront { + explicit EmplaceFront(Container& c) : container(std::addressof(c)) {} + template + void emplace(Args&&... args) { + container->emplace_front(std::forward(args)...); + } + Container* container; +}; + +/** + * Emplace implementation class for folly::back_emplace_iterator. + */ +template +struct EmplaceBack { + explicit EmplaceBack(Container& c) : container(std::addressof(c)) {} + template + void emplace(Args&&... args) { + container->emplace_back(std::forward(args)...); + } + Container* container; +}; + +/** + * Generic base class and implementation of all emplace iterator classes. + * + * Uses the curiously recurring template pattern (CRTP) to cast `this*` to + * `Derived*`; i.e., to implement covariant return types in a generic manner. + */ +template class emplace_iterator_base; /** * Partial specialization of emplace_iterator_base with implicit unpacking * disabled. */ -template -class emplace_iterator_base { +template +class emplace_iterator_base + : protected EmplaceImpl /* protected implementation inheritance */ { public: // Iterator traits. using iterator_category = std::output_iterator_tag; @@ -170,10 +230,10 @@ class emplace_iterator_base { using difference_type = void; using pointer = void; using reference = void; - using container_type = Container; + using container_type = + std::remove_reference_t; - explicit emplace_iterator_base(Container& container) - : container(std::addressof(container)) {} + using EmplaceImpl::EmplaceImpl; /** * Canonical output operator. Forwards single argument straight to container's @@ -181,7 +241,8 @@ class emplace_iterator_base { */ template Derived& operator=(T&& arg) { - return static_cast(this)->emplace(std::forward(arg)); + this->emplace(std::forward(arg)); + return static_cast(*this); } /** @@ -222,23 +283,21 @@ class emplace_iterator_base { emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default; protected: - using Class = emplace_iterator_base; - template Derived& unpackAndEmplace(Args& args, std::index_sequence) { - return static_cast(this)->emplace(get_emplace_arg(args)...); + this->emplace(get_emplace_arg(args)...); + return static_cast(*this); } template Derived& unpackAndEmplace(const Args& args, std::index_sequence) { - return static_cast(this)->emplace(get_emplace_arg(args)...); + this->emplace(get_emplace_arg(args)...); + return static_cast(*this); } template Derived& unpackAndEmplace(Args&& args, std::index_sequence) { - return static_cast(this)->emplace( - get_emplace_arg(std::move(args))...); + this->emplace(get_emplace_arg(std::move(args))...); + return static_cast(*this); } - - Container* container; }; /** @@ -246,14 +305,17 @@ class emplace_iterator_base { * enabled. * * Uses inheritance rather than SFINAE. operator= requires a single argument, - * which makes it impossible to use std::enable_if or similar. + * which makes it very tricky to use std::enable_if or similar. */ -template -class emplace_iterator_base - : public emplace_iterator_base { +template +class emplace_iterator_base + : public emplace_iterator_base { + private: + using Base = emplace_iterator_base; + public: - using emplace_iterator_base::emplace_iterator_base; - using emplace_iterator_base::operator=; + using Base::Base; + using Base::operator=; /** * Special output operator for arguments packed into a std::pair. Unpacks @@ -299,122 +361,76 @@ class emplace_iterator_base emplace_iterator_base& operator=(const emplace_iterator_base&) = default; emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default; }; -} // folly::detail /** - * Behaves just like std::insert_iterator except that it calls emplace() - * instead of insert(). Uses perfect forwarding. + * Concrete instantiation of emplace_iterator_base. All emplace iterator + * classes; folly::emplace_iterator, folly::hint_emplace_iterator, + * folly::front_emplace_iterator, and folly::back_emplace_iterator; are just + * type aliases of this class. + * + * It is not possible to alias emplace_iterator_base directly, because type + * aliases cannot be used for CRTP. */ -template -class emplace_iterator : public detail::emplace_iterator_base< - emplace_iterator, - Container, - implicit_unpack> { +template < + template class EmplaceImplT, + typename Container, + bool implicit_unpack> +class emplace_iterator_impl + : public emplace_iterator_base< + emplace_iterator_impl, + EmplaceImplT, + implicit_unpack> { private: - using Base = detail::emplace_iterator_base< - emplace_iterator, - Container, + using Base = emplace_iterator_base< + emplace_iterator_impl, + EmplaceImplT, implicit_unpack>; public: - emplace_iterator(Container& container, typename Container::iterator i) - : Base(container), iter(std::move(i)) {} - + using Base::Base; using Base::operator=; // We need all of these explicit defaults because the custom operator= // overloads disable implicit generation of these functions. - emplace_iterator(const emplace_iterator&) = default; - emplace_iterator(emplace_iterator&&) noexcept = default; - emplace_iterator& operator=(emplace_iterator&) = default; - emplace_iterator& operator=(const emplace_iterator&) = default; - emplace_iterator& operator=(emplace_iterator&&) noexcept = default; - - protected: - typename Container::iterator iter; - - private: - friend typename Base::Class; - template - emplace_iterator& emplace(Args&&... args) { - iter = this->container->emplace(iter, std::forward(args)...); - ++iter; - return *this; - } + emplace_iterator_impl(const emplace_iterator_impl&) = default; + emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default; + emplace_iterator_impl& operator=(emplace_iterator_impl&) = default; + emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default; + emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default; }; +} // folly::detail /** - * Behaves just like std::front_insert_iterator except that it calls - * emplace_front() instead of insert_front(). Uses perfect forwarding. + * Behaves just like std::insert_iterator except that it calls emplace() + * instead of insert(). Uses perfect forwarding. */ template -class front_emplace_iterator : public detail::emplace_iterator_base< - front_emplace_iterator, - Container, - implicit_unpack> { - private: - using Base = detail::emplace_iterator_base< - front_emplace_iterator, - Container, - implicit_unpack>; - - public: - using Base::Base; - using Base::operator=; +using emplace_iterator = + detail::emplace_iterator_impl; - // We need all of these explicit defaults because the custom operator= - // overloads disable implicit generation of these functions. - front_emplace_iterator(const front_emplace_iterator&) = default; - front_emplace_iterator(front_emplace_iterator&&) noexcept = default; - front_emplace_iterator& operator=(front_emplace_iterator&) = default; - front_emplace_iterator& operator=(const front_emplace_iterator&) = default; - front_emplace_iterator& operator=(front_emplace_iterator&&) noexcept = - default; +/** + * Behaves just like std::insert_iterator except that it calls emplace_hint() + * instead of insert(). Uses perfect forwarding. + */ +template +using hint_emplace_iterator = detail:: + emplace_iterator_impl; - private: - friend typename Base::Class; - template - front_emplace_iterator& emplace(Args&&... args) { - this->container->emplace_front(std::forward(args)...); - return *this; - } -}; +/** + * Behaves just like std::front_insert_iterator except that it calls + * emplace_front() instead of insert(). Uses perfect forwarding. + */ +template +using front_emplace_iterator = detail:: + emplace_iterator_impl; /** * Behaves just like std::back_insert_iterator except that it calls - * emplace_back() instead of insert_back(). Uses perfect forwarding. + * emplace_back() instead of insert(). Uses perfect forwarding. */ template -class back_emplace_iterator : public detail::emplace_iterator_base< - back_emplace_iterator, - Container, - implicit_unpack> { - private: - using Base = detail::emplace_iterator_base< - back_emplace_iterator, - Container, - implicit_unpack>; - - public: - using Base::Base; - using Base::operator=; - - // We need all of these explicit defaults because the custom operator= - // overloads disable implicit generation of these functions. - back_emplace_iterator(const back_emplace_iterator&) = default; - back_emplace_iterator(back_emplace_iterator&&) noexcept = default; - back_emplace_iterator& operator=(back_emplace_iterator&) = default; - back_emplace_iterator& operator=(const back_emplace_iterator&) = default; - back_emplace_iterator& operator=(back_emplace_iterator&&) noexcept = default; - - private: - friend typename Base::Class; - template - back_emplace_iterator& emplace(Args&&... args) { - this->container->emplace_back(std::forward(args)...); - return *this; - } -}; +using back_emplace_iterator = detail:: + emplace_iterator_impl; /** * Convenience function to construct a folly::emplace_iterator, analogous to @@ -432,6 +448,22 @@ emplace_iterator emplacer( return emplace_iterator(c, std::move(i)); } +/** + * Convenience function to construct a folly::hint_emplace_iterator, analogous + * to std::inserter(). + * + * Setting implicit_unpack to false will disable implicit unpacking of + * single std::pair and std::tuple arguments to the iterator's operator=. That + * may be desirable in case of constructors that expect a std::pair or + * std::tuple argument. + */ +template +hint_emplace_iterator hint_emplacer( + Container& c, + typename Container::iterator i) { + return hint_emplace_iterator(c, std::move(i)); +} + /** * Convenience function to construct a folly::front_emplace_iterator, analogous * to std::front_inserter(). diff --git a/folly/test/IteratorTest.cpp b/folly/test/IteratorTest.cpp index 815e9ebd..0be32bf9 100644 --- a/folly/test/IteratorTest.cpp +++ b/folly/test/IteratorTest.cpp @@ -19,9 +19,12 @@ #include #include #include +#include +#include #include #include #include +#include #include #include @@ -219,6 +222,60 @@ TEST(EmplaceIterator, BackEmplacerTest) { } } +/** + * Basic tests for folly::hint_emplace_iterator. + */ +TEST(EmplaceIterator, HintEmplacerTest) { + { + init_counters(); + std::map m; + auto it = hint_emplacer(m, m.end()); + it = make_emplace_args( + std::piecewise_construct, + std::forward_as_tuple(0), + std::forward_as_tuple(0)); + it = make_emplace_args( + std::piecewise_construct, + std::forward_as_tuple(1), + std::forward_as_tuple(0, 0)); + it = make_emplace_args( + std::piecewise_construct, + std::forward_as_tuple(2), + std::forward_as_tuple(Object{})); + ASSERT_EQ(m.size(), 3); + EXPECT_EQ(gDefaultCtrCnt, 1); + EXPECT_EQ(gCopyCtrCnt, 0); + EXPECT_EQ(gMoveCtrCnt, 1); + EXPECT_EQ(gExplicitCtrCnt, 1); + EXPECT_EQ(gMultiargCtrCnt, 1); + EXPECT_EQ(gCopyOpCnt, 0); + EXPECT_EQ(gMoveOpCnt, 0); + EXPECT_EQ(gConvertOpCnt, 0); + } + { + struct O { + explicit O(int i) : i(i) {} + bool operator<(const O& other) const { + return i < other.i; + } + bool operator==(const O& other) const { + return i == other.i; + } + int i; + }; + std::vector v1 = {0, 1, 2, 3, 4}; + std::vector v2 = {0, 2, 4}; + std::set diff; + std::set_difference( + v1.begin(), + v1.end(), + v2.begin(), + v2.end(), + hint_emplacer(diff, diff.end())); + ASSERT_EQ(diff, std::set({O(1), O(3)})); + } +} + /** * Test std::copy() with explicit conversion. This would not compile with a * std::back_insert_iterator, because the constructor of Object that takes a -- 2.34.1