Why can't I emplace multiple elements in a sequence?

Question

C++11 has introduced emplace function to construct an element in-place inside a sequence. This is complementary to insert which either copies or moves elements.

However, out of several overloads of insert, only the single element insert version,

i.e.

iterator insert( const_iterator p, T const& x);
iterator insert( const_iterator p, T&& x );

has an emplace version,

template< class... Args > 
iterator emplace(const_iterator p, Args&&... x);

Is there any reason, not to allow construction of n elements in-place using emplace?

While a overload like,

template< class... Args > 
iterator emplace(const_iterator p,size_type n,Args&&... x);

just like the corresponding insert

iterator insert(const_iterator p,size_type n,const_reference x);

may conflict with the other overload, taking the constructor arguments as a tuple, or using some special tag like in_place_t likely to disambiguate them.

EDIT The proposed function emplace_n for vector may have behaviour like the one given below

template<class... Args>
iterator emplace_n(const_iterator p,size_type n,Args&&... x)
{
    size_type const offset = p - begin();
    if(capacity() < size()+n)
    {
        vector<T> v;
        v.reserve(size()+n);
        v.assign(make_move_iterator(begin(),make_move_iterator(end());
        swap(*this,v);
    }
    auto const sz = size();
    for(auto c = 0; c != n ; ++c)
    {
        emplace_back(x...); //can do forward only if n == 1
    }
    rotate(begin()+offset,begin()+sz,end());
    return iterator{begin() + offset};
}

The usual answer is either 'because no one suggested it to the Committee' or 'because they considered it not useful enough'; you could search for proposals to see which of those might be true. — underscore_d, Nov 15 '18 at 19:37
It's 2019 and I'm still wondering where this function is! It's sad how many people jump to find problems without even reading the question; it's clear from the given answers they have no idea what this question is about. But I think it would be a great feature. — Apollys supports Monica, Mar 07 '19 at 21:59

Simple · Answer 1 · 2014-03-07T11:37:38.947

2

The problem is that there is no easy way to determine when the arguments for one element end and the arguments for the next begin. You can pass the arguments via tuples though like for pair's piecewise constructor, and end up with a helper function like this:

template<int... Is>
struct index_seq { };

template<int N, int... Is>
struct make_index_seq : make_index_seq<N - 1, N - 1, Is...> { };

template<int... Is>
struct make_index_seq<0, Is...> : index_seq<Is...> { };

template<class Cont, class Tup, int... Is>
void emplace_back_impl(Cont& c, Tup&& tup, index_seq<Is...>)
{
    using std::get;
    c.emplace_back(get<Is>(std::forward<Tup>(tup))...);
}

template<class Cont, class... Tups>
void emplace_multiple(Cont& c, Tups&&... tups)
{
    int const unpack[]{
        0, ((emplace_back_impl)(c, std::forward<Tups>(tups),
                                make_index_seq<
                                    std::tuple_size<typename std::remove_reference<Tups>::type>{}
                                >()), 0)...
    };
    static_cast<void>(unpack);
}

Then you can use the emplace_multiple function to emplace multiple elements:

std::vector<std::string> xs;
emplace_multiple(xs, std::make_tuple("Hello, world!"), std::make_tuple(10, 'a'));

Note that this uses emplace_back. Using emplace plus an iterator to mark the insertion position is dangerous if you haven't reserved enough space in advance. This is because emplace and emplace_back can invalidate iterators (at least for vectors), and then the function doesn't know how to get a new iterator to the position you intended.

Demo here.

edited Mar 07 '14 at 11:37

answered Mar 07 '14 at 11:20

Simple

13,992
2
47
47

This solution proposes a wrapper over `emplace_back`, and not the same as equivalent of an `emplace` version of `iterator insert(const_iterator p,size_type n,T const& x)`, which can in-place construct `n` objects of same value at a location specified. – abir Mar 07 '14 at 11:46
@abir I discussed why `emplace` is a dangerous idea and your question used a different signature to the one you just wrote. Yours is no different to `insert` in that there are no performance gains. edit: unless `T` isn't the element type, then I understand. – Simple Mar 07 '14 at 11:53
I do not understand why will it be dangerous, or what it has to do with iterator invalidation! What all it is supposed to do, in-place construct `n` copies of `T` (yes, `T` is the element type) given the constructor arguments. (in contrast to copy construction for an equivalent `insert`). And of course it may/may not choose to move the arguments themselves for construction of `T` for `n == 1` as an optimization. – abir Mar 07 '14 at 12:01
@abir as I mentioned, emplace can invalid iterators because it has to allocate memory, then the iterator can't be used safely as a position anymore. – Simple Mar 07 '14 at 12:03
Yes, it can, and most likely it will. That is true for `insert`, `push_back`, `emplace_back` etc also. But I still failed to see the problem with iterator invalidation. Also, I had not asked anything for multiple `emplace_back`, neither with different construction arguments as your answer shows. Perhaps the question failed to communicate the intent. Will I update the question with a sketch of behavior I am looking for? Appreciate the help. – abir Mar 07 '14 at 12:16
@abir take vector for example. When it has to allocate new memory because of an emplace, it has to move the elements from the old storage to the new storage. This means any iterators you currently have point to old storage, where there is no longer anything there. This is iterator invalidation; the iterator you pass in isn't valid anymore if the vector had to resize. This means you can't pass the iterator to emplace anymore to mark an insertion position. Do you just want to `emplace` multiple copies with the same arguments? – Simple Mar 07 '14 at 12:19
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/49236/discussion-between-abir-and-simple) – abir Mar 07 '14 at 12:40
This is a good indication of where to start implementing a generalised 'multiple emplace', as people finding this question through the title will be looking for, rather than the 'n copies of same emplaced element', which (a) can be implemented as a simplification of this and (b) isn't very interesting IMO given that the 1 extra copy from the non-emplace versions becomes increasingly insignificant as the number of elements increases - and, in fact, it might even be cheaper to copy a passed element N-1 times than to construct it from scratch from arguments! It all depends on the type & its ctors – underscore_d Nov 15 '18 at 19:38
but I think nowadays it needs an update. (a) C++14 added `std::make_index_sequence` _et al._, which gets rid of a lot of the prelude here. We can do even better & get rid of most of the noise in C++17: (a) its fold expressions obviate all the ugly stuff with arrays or `initializer_list`s, comma operators, and `void` casts as we can now just write `(doSomethingOverPack(), ...)`; and (b) it should be possible (though I didn't yet try this bit...) to get rid of all the manual `index_sequence` and `get()`tery by just using its `(std::apply(&std::vector::emplace_back, vec, tuple), ...)`. – underscore_d Nov 15 '18 at 19:49

score 1 · Answer 2 · edited May 23 '17 at 10:30

1

let's call the proposed function emplace_n, to somehow emplace n elements at a given position. For emplace it is clear that all arguments (except the iterator) have to be forwarded to construct the one element that has to be emplaced. Now think about only "emplacing" two elements at that position:

vector<X> vx;
vector<X>::const_iterator it = ... ;

vx.emplace_2(it, a1, a2, a3, a4, a5);

Now, which of the arguments shall be used to construct the first, which to construct the second element? There are several combinations that the library cannot easily distinguish. Equivalent "single emplacements" might be:

auto it2 = vx.emplace_2(it);
vx.emplace(it2, a1, a2, a3, a4, a5);

//or
auto it2 = vx.emplace_2(it, a1);
vx.emplace(it2, a2, a3, a4, a5);

//or
auto it2 = vx.emplace_2(it, a1, a2);
vx.emplace(it2, a3, a4, a5);

etc. you get the point. For n>2 it gets even more complicated.

This is the reason why there is no simple "emplacement" for multiple elements. You can however use some kind of emplacer-iterator together with a std::transform or similar algorithm for a hand-directed version pf multiple-emplace.

edited May 23 '17 at 10:30

Community

1
1

answered Mar 07 '14 at 11:51

Arne Mertz

24,171
3
51
90

This is not exactly `emplace` equivalent of `insert(const_iterator p,size_type n,T const& x)`. It is supposed to construct `n` equal objects in-place(and not copy construct) , given the constructor arguments. To elaborate, i added an implementation to clarify intended behaviour. – abir Mar 07 '14 at 13:29
1

Ok, from the example I see that you want to "emplace" n objects constructed the same way (you did not mention the `insert(p,n,x)` before). I don't see the difference to one simple `reserve` an n `emplace(x, args...)` calls, except that an exception in one of the constructor calls would leave you with `m – Arne Mertz Mar 07 '14 at 13:57
It is true for sequence like `vector` to implement `insert(p,n,x)` in terms of `reserve`,`push_back` and `rotate`. It is also likely to be possible for linked sequences like `forward_list` & `list` with multiple `insert` with single elements. However for sequences like `deque` which has no `reserve` facility, there is no way to preallocate space for `n` objects, and equivalent performance can not be ensured (I guess vector insert has only basic exception safety, so inserting less than n elements due to exception should not be an issue) – abir Mar 07 '14 at 20:13

Why can't I emplace multiple elements in a sequence?

2 Answers2