5

In generic code I was trying to tell an output iterator (in practice a std::back_inserter_iterator to move a range of elements. To my surprise it looked as if elements were moved in a move-to-back_inserter operation.

#include<algorithm> // move
#include<iterator> // back_inserter
#include<vector>
int main(){
    std::vector<std::vector<double> > v(10, std::vector<double>(100));
    std::vector<std::vector<double> > w;

    assert( not v[0].empty() and w.size() == 0 );
    std::copy(v.begin(), v.end(), std::back_inserter(w));
    assert( not v[0].empty() and w.size() == 10 );

    std::move(v.begin(), v.end(), std::back_inserter(w));
    assert( v[0].empty() and w.size() == 20 ); // were v elements moved to w?
}

However I don't think it is possible that elements of v were really moved to w, because after all back_inserter will do a push_back which implies a copy to w.

It seems more likely that in the std::move case, v elements were moved to a temporary and only then copied into w.

Is that correct? Is there a std::back_inserter really moving somehow?

Is there already a variant of std::back_inserter that takes advantage of move/emplace? Something like an std::back_emplacer?

JFMR
  • 23,265
  • 4
  • 52
  • 76
alfC
  • 14,261
  • 4
  • 67
  • 118

3 Answers3

3

std::back_inserter() is a convenience function template for creating an std::back_insert_iterator object.

The class std::back_insert_iterator has already operator= overloaded for taking rvalue reference types, i.e.:

back_insert_iterator<Container>& operator=(typename Container::value_type&& value);

Therefore, std::back_insert_iterator is already prepared to take advantage of move semantics.

JFMR
  • 23,265
  • 4
  • 52
  • 76
  • I missed both that `back_inserter_iterator` has `operator=(T&&)` and that `push_back` also has a `T&&`. – alfC Jan 22 '19 at 08:42
3

If std::back_insert_iterator does nothing but calling push_back on the container it's being constructed with, the question can be answered looking at the std::vector::push_back overload set:

void push_back(const T& value);
void push_back(T&& value);

So, here we obviously have an overload for rvalue references. Wouldn't it be weird, if the corresponding std::back_insert_iterator copies its argument when invoked with an rvalue reference? And indeed, we again have a very similar overload set:

// 1
back_insert_iterator<Container>&
    operator=(typename Container::const_reference value);
back_insert_iterator<Container>&
    operator=(const typename Container::value_type& value);

// 2
back_insert_iterator<Container>&
    operator=(typename Container::value_type&& value);

with the additional comment that

  1. Results in container->push_back(value)
  2. Results in container->push_back(std::move(value))

Coming back to your original question

Is there a std::back_inserter really moving somehow?

Yes, the iterator this function creates does take advantage of rvalue reference arguments.

Is there already a variant of std::back_inserter that takes advantage of move/emplace?

No, but it can be implemented. See this answer.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
lubgr
  • 37,368
  • 3
  • 66
  • 117
  • I missed that, I was convinced that `push_back` only had a `const T&` overload. That added to the fact that `back_inserter_iterator` has `::operator=(T&&)` makes a `back_emplacer` much less necessary. – alfC Jan 22 '19 at 08:41
  • @alfC I guess you are getting confused with emplace vs move. Move of the contents - so avoiding a copy and delete - is the much simpler feature to implement, and you can pretty much assume it is everywhere in the stl. With emplace, you provide the arguments necessary to construct the object, and call a special xxx_emplace() method to have the object constructed directly into the container space. This can, of course, be a move constructor, but that is generally not necessary to emplace if all you want to do is move. – Gem Taylor Jan 22 '19 at 14:40
  • @GemTaylor yes, but if you are talking about emplace with a single argument of value type. Then push_back(move(t)) is no worst or better than emplace_back(move(t)). Is it? – alfC Jan 22 '19 at 16:00
  • @alfC No it shouldn't be much different, assuming your object implements move semantics efficiently, and the core object itself is not so big that copying those simple members is not expensive. For example, moving a string means copying at least 24 bytes of the string object itself. Emplace avoids those 24 bytes: nothing compared to allocating a new string, copying the contents, and deleting the old string, but not zero. – Gem Taylor Jan 22 '19 at 16:42
  • To be clear, emplace_back of a char* into a vector of string will save this small additional copy and clear of the 24byte string object itself vs. push_back of the same char* - of course the string has to be copied once to dynamic memory in both cases, which is a much more expensive operation. But compare this to c++98, when push_back of char* would create a temporary string, then dup the dynamic content, then delete the first dynamic instance. – Gem Taylor Jan 23 '19 at 10:46
1

Is there already a variant of std::back_inserter that takes advantage of move/emplace? Something like an std::back_emplacer?

There is back_emplacer described here: https://stackoverflow.com/a/12131700/7471760

But it is not part of std.

See also: Why no emplacement iterators in C++11 or C++14?

ferdymercury
  • 698
  • 4
  • 15