Using emplace with algorithms such as std::fill

Question

I have used vector::emplace_back in order to avoid constructing temporal objects while filling a vector. Here you have a simplified version:

class Foo {
public:
    Foo(int i, double d) : i_(i), d_(d) {}
    /* ... */
};

std::vector<Foo> v;
v.reserve(10);
for (int i = 0; i < 10; i++)
    v.emplace_back(1, 1.0);

But I wanted to use std::fill_n instead:

v.reserve(10);
std::fill_n(std::back_inserter(v), 10, Foo(1, 1.0));

In this way, temporal copies will be created, though. I do not know how to use emplace in this situation. I guess I would need something like std::back_emplacer, but I could not find such a thing. Is that part of C++11, but not implemented in GCC yet? If it is not part of C++11, is there any other way to do that?

Answer 1

It's common to use tuples to ease the pass a variadic number of items (in this case, parameters to forward to emplace_back), with a little technique to unpack the tuple back. As such it is possible to write a back_emplacer utility by requiring the user to make use of the tuple factory functions (one of std::make_tuple, std::tie, std::forward_as_tuple) where it make sense:

#include <type_traits>
#include <tuple>

// Reusable utilites

template<typename T>
using RemoveReference = typename std::remove_reference<T>::type;
template<typename T>
using Bare = typename std::remove_cv<RemoveReference<T>>::type;

template<typename Out, typename In>
using WithValueCategoryOf = typename std::conditional<
    std::is_lvalue_reference<In>::value
    ,  typename std::add_lvalue_reference<Out>::type
    , typename std::conditional<
        std::is_rvalue_reference<Out>::value
        , typename std::add_rvalue_reference<Out>::type
        , Out
    >::type
>::type;

template<int N, typename Tuple>
using TupleElement = WithValueCategoryOf<
    typename std::tuple_element<N, RemoveReference<Tuple>>::type
    , Tuple
>;  

// Utilities to unpack a tuple
template<int... N>
struct indices {
    using next = indices<N..., sizeof...(N)>;
};

template<int N>
struct build_indices {
    using type = typename build_indices<N - 1>::type::next;
};
template<>
struct build_indices<0> {
    using type = indices<>;
};

template<typename Tuple>
constexpr
typename build_indices<std::tuple_size<Bare<Tuple>>::value>::type
make_indices() { return {}; }

template<typename Container>
class back_emplace_iterator {
public:
    explicit back_emplace_iterator(Container& container)
        : container(&container)
    {}  

    template<
        typename Tuple
        // It's important that a member like operator= be constrained
        // in this case the constraint is delegated to emplace,
        // where it can more easily be expressed (by expanding the tuple)   
        , typename = decltype( emplace(std::declval<Tuple>(), make_indices<Tuple>()) )
    >
    back_emplace_iterator& operator=(Tuple&& tuple)
    {
        emplace(*container, std::forward<Tuple>(tuple), make_indices<Tuple>());

        return *this;
    }

    template<
        typename Tuple
        , int... Indices  
        , typename std::enable_if<
            std::is_constructible<
                typename Container::value_type
                , TupleElement<Indices, Tuple>...
            >::value
            , int
        >::type...
    >
    void emplace(Tuple&& tuple, indices<Indices...>)
    {
        using std::get;
        container->emplace_back(get<Indices>(std::forward<Tuple>(tuple))...);
    }

    // Mimic interface of std::back_insert_iterator
    back_emplace_iterator& operator*() { return *this; }
    back_emplace_iterator& operator++() { return *this; }
    back_emplace_iterator operator++(int) { return *this; }

private:
    Container* container;  
};

template<typename Container>
back_emplace_iterator<Container> back_emplacer(Container& c)
{ return back_emplace_iterator<Container> { c }; }

A demonstration of the code is available. In your case you'd want to call std::fill_n(back_emplacer(v), 10, std::forward_as_tuple(1, 1.0)); (std::make_tuple is also acceptable). You'd also want the usual iterator stuff to make the feature complete -- I recommend Boost.Iterators for that.

I must really stress however that such a utility doesn't bring much when used with std::fill_n. In your case it would save the construction of the temporary Foo, in favour of a tuple of references (a tuple of values if you were to use std::make_tuple). I leave it to the reader to find some other algorithm where back_emplacer would be useful.

Answer 2

You are right that there is no back_emplacer in the standard. You could perfectly write one yourself, but what for ?

When you call emplace_back, you have to provide the arguments for the constructor (any constructor): vec.emplace_back(1, 2) for example. However, you cannot arbitrarily pass tuples of arguments in C++, so the back_emplacer would be limited to unary constructor.

In the case of fill_n, you provide an argument that will be copied, and then both back_inserter and back_emplacer would call the same copy constructor with the same argument.

Note that there is the generate and generate_n algorithms to build new elements. But likewise any temporary copy will probably be elided.

Therefore I think the need for a back_emplacer is rather light, mostly because of the language non-support of multiple return values.

EDIT

If you look at the comments below you will realize that using a combination std::forward_as_tuple and std::is_constructible it could be possible to write a back_emplacer mechanism. Thanks to Luc Danton for the breakthrough.

Answer 3

There won't be any "temporal copies" made. There will be exactly one temporary, the one you passed to fill_n. And it will be copied into each value.

And even if there was a back_emplacer, what would you call it with? The emplace familiy of functions take constructor parameters; fill_n takes an object to copy into the iterator.

Answer 4

I've seen @LucDanton's answer above (https://stackoverflow.com/a/12131700/1032917) and I still cannot see the point of making the code overly complicated (apart from the fact it was written back in 2012, but even given that...). Anyway, I find the following code as functional as Luc's:

template <typename Container>
class back_emplace_iterator
{
public:
    explicit back_emplace_iterator(Container & container)
        : container(std::addressof(container))
    {}

    template <typename... Args>
    back_emplace_iterator & operator=(Args &&... args)
    {
        static_assert(std::is_constructible_v<typename Container::value_type, Args...>, "should be constructible");

        assert(container);
        container->emplace_back(std::forward<Args>(args)...);

        return *this;
    }

    // Mimic interface of std::back_insert_iterator
    back_emplace_iterator & operator*()
    {
        return *this;
    }
    back_emplace_iterator & operator++()
    {
        return *this;
    }
    back_emplace_iterator operator++(int)
    {
        return *this;
    }

private:
    Container * container;
};

template <typename Container>
back_emplace_iterator<Container> back_emplacer(Container & c)
{
    return back_emplace_iterator<Container>{c};
}

And with CTAD in C++17, you can even get rid of back_emplacer and write back_emplace_iterator(my_container) without explicitly giving the template arguments.

Answer 5

I recently submitted an emplace_iterator class and related utility function to the folly library. I believe it solves the original question and supports automatic unzipping of std::tuple arguments passed to operator=.

https://github.com/facebook/folly/blob/master/folly/Iterator.h

class Widget { Widget(int, int); };

std::vector<Widget> makeWidgets(const std::vector<int>& in) {
  std::vector<Widget> out;
  std::transform(
      in.begin(),
      in.end(),
      folly::back_emplacer(out),
      [](int i) { return folly::make_emplace_args(i, i); });
  return out;
}

folly::make_emplace_args is analogous to std::make_tuple but results in perfect forwarding of its arguments to the Widget constructor. (std::make_tuple and similar may result in additional copies and does not preserve lvalue vs rvalue typedness.) In this specific example, using std::make_tuple would have the same effect though.

Answer 6

class Foo {
public:
  Foo(int i, double d) : i_(i), d_(d) {}
};

std::vector<Foo> v;
v.reserve(10);
std::generate_n(std::back_inserter(v), 10, [&]()->Foo{ return {1, 1.0}; });

RVO allows the return value of a function to be elided directly into where it is going to be stored.

While logically a temporary is created, in actual fact no temporary is created. And you have access to all variables in the surrounding scope to decide how to create the element, not just constants, if you want them.