2164. What are the semantics of vector.emplace(vector.begin(), vector.back())?

Section: 23.3.11.5 [vector.modifiers], 23.2 [container.requirements] Status: C++20 Submitter: Howard Hinnant Opened: 2012-07-07 Last modified: 2021-02-25

Priority: 2

View all other issues in [vector.modifiers].

View all issues with C++20 status.

Discussion:

Nikolay Ivchenkov recently brought the following example on the std-discussion newsgroup, asking whether the following program well-defined: 

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v;
  v.reserve(4);
  v = { 1, 2, 3 };
  v.emplace(v.begin(), v.back());
  for (int x : v)
    std::cout << x << std::endl;
}

Nikolay Ivchenkov:

I think that an implementation of vector's 'emplace' should initialize an intermediate object with v.back() before any shifts take place, then perform all necessary shifts and finally replace the value pointed to by v.begin() with the value of the intermediate object. So, I would expect the following output: 

3
1
2
3

GNU C++ 4.7.1 and GNU C++ 4.8.0 produce other results: 

2
1
2
3

Howard Hinnant:

I believe Nikolay is correct that vector should initialize an intermediate object with v.back() before any shifts take place. As Nikolay pointed out in another email, this appears to be the only way to satisfy the strong exception guarantee when an exception is not thrown by T's copy constructor, move constructor, copy assignment operator, or move assignment operator as specified by 23.3.11.5 [vector.modifiers]/p1. I.e. if the emplace construction throws, the vector must remain unaltered.

That leads to an implementation that tolerates objects bound to the function parameter pack of the emplace member function may be elements or sub-objects of elements of the container.

My position is that the standard is correct as written, but needs a clarification in this area. Self-referencing emplace should be legal and give the result Nikolay expects. The proposed resolution of LWG 760 is not correct.

[2015-02 Cologne]

LWG agrees with the analysis including the assessment of LWG 760 and would appreciate a concrete wording proposal.

[2015-04-07 dyp comments]

The Standard currently does not require that creation of such intermediate objects is legal. 23.2.4 [sequence.reqmts] Table 100 — "Sequence container requirements" currently specifies:

Table 100 — Sequence container requirements
Expression Return type Assertion/note
pre-/post-condition
…
a.emplace(p, args); iterator Requires: T is EmplaceConstructible into X from args. For vector and deque, T is also MoveInsertable into X and MoveAssignable. […]
…

The EmplaceConstructible concept is defined via allocator_traits<A>::construct in 23.2.2 [container.requirements.general] p15.5 That's surprising to me since the related concepts use the suffix Insertable if they refer to the allocator. An additional requirement such as std::is_constructible<T, Args...> is necessary to allow creation of intermediate objects.

The creation of intermediate objects also affects other functions, such as vector.insert. Since aliasing the vector is only allowed for the single-element forms of insert and emplace (see 526), the range-forms are not affected. Similarly, aliasing is not allowed for the rvalue-reference overload. See also LWG 2266.

There might be a problem with a requirement of std::is_constructible<T, Args...> related to the issues described in LWG 2461. For example, a scoped allocator adapter passes additional arguments to the constructor of the value type. This is currently not done in recent implementations of libstdc++ and libc++ when creating the intermediate objects, they simply create the intermediate object by perfectly forwarding the arguments. If such an intermediate object is then moved to its final destination in the vector, a change of the allocator instance might be required — potentially leading to an expensive copy. One can also imagine worse problems, such as run-time errors (allocators not comparing equal at run-time) or compile-time errors (if the value type cannot be created without the additional arguments). I have not looked in detail into this issue, but I'd be reluctant adding a requirement such as std::is_constructible<T, Args...> without further investigation.

It should be noted that the creation of intermediate objects currently is inconsistent in libstdc++ vs libc++. For example, libstdc++ creates an intermediate object for vector.insert, but not vector.emplace, whereas libc++ does the exact opposite in this respect.

A live demo of the inconsistent creation of intermediate objects can be found here.

[2015-10, Kona Saturday afternoon]

HH: If it were easy, it'd have wording. Over the decades I have flipped 180 degrees on this. My current position is that it should work even if the element is in the same container.

TK: What's the implentation status? JW: Broken in GCC. STL: Broken in MSVS. Users complain about this every year.

MC: 526 says push_back has to work.

HH: I think you have to make a copy of the element anyway for reasons of exception safety. [Discussion of exception guarantees]

STL: vector has strong exception guarantees. Could we not just provide the Basic guarantee here.

HH: It would terrify me to relax that guarantee. It'd be an ugly, imperceptible runtime error.

HH: I agree if we had a clean slate that strong exception safety is costing us here, and we shouldn't provide it if it costs us.

STL: I have a mail here, "how can vector provide the strong guarantee when inserting in the middle".

HH: The crucial point is that you only get the strong guarantee if the exception is thrown by something other than the copy and move operations that are used to make the hole.

STL: I think we need to clean up the wording. But it does mandate currently that the self-emplacement must work, because nothings says that you can't do it. TK clarifies that a) self-emplacement must work, and b) you get the strong guarantee only if the operations for making the hole don't throw, otherwise basic. HH agrees. STL wants this to be clear in the Standard.

STL: Should it work for deque, too? HH: Yes.

HH: I will attempt wording for this.

TK: Maybe mail this to the reflector, and maybe someone has a good idea?

JW: I will definitely not come up with anything better, but I can critique wording.

Moved to Open; Howard to provide wording, with feedback from Jonathan.

[2017-01-25, Howard suggests wording]

[2018-1-26 issues processing telecon]

Status to 'Tentatively Ready' after adding a period to Howard's wording.

[2018-3-17 Adopted in Jacksonville]

Proposed resolution:

This wording is relative to N4713.

  1. Modify in 23.2.4 [sequence.reqmts] Table 87 — "Sequence container requirements" as indicated:

    Table 87 — Sequence container requirements (in addition to container)
    Expression Return type Assertion/note
    pre-/post-condition
    […]
    a.emplace(p, args) iterator Requires: T is EmplaceConstructible into X
    from args. For vector and deque, T is also
    MoveInsertable into X and MoveAssignable.
    Effects: Inserts an object of type T
    constructed with
    std::forward<Args>(args)... before p.
    [Note: args may directly or indirectly refer to a value
    in a. — end note]