Is inserting an element of a std::vector into the

2019-04-18 08:39发布

问题:

Consider the following insert and emplace member functions of std::vector<T>:

template <class... Args> iterator emplace(const_iterator position, Args&&... args);
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);

What if one of them is invoked with a reference to an element of the vector itself as an argument? Normally, each of them invalidates references to all elements starting from position, which might include the argument, or if a reallocation happens, references to all elements, which definitely include it, but does this mean such an invocation is invalid or does the insertion (seem to) happen first?

Looking at some common implementations gives curious results:

  • libstdc++ copies the argument before moving any elements, but only in the const T& overloads of insert. It contains this comment:

    The order of the three operations is dictated by the C++0x case, where the moves could alter a new element belonging to the existing vector. This is an issue only for callers taking the element by const lvalue ref (see 23.1/13).

    But C++11 §23.1 is just a brief summary of the containers library, and even if we assume this refers to §23.2.1 (which used to be §23.1 in C++03), §23.2.1/13 only gives a definition of allocator-aware containers, which seems to have nothing to do with this. I’ve looked through chapter 23, but I haven’t found anything relevant anywhere.

  • libc++ creates a temporary before moving any elements in emplace, while in insert it moves elements first but converts the argument reference to a pointer and adjusts it to ensure it points to the original element—but again, it does all this only in the const T& overload.

  • Visual C++ creates a copy/temporary before moving any elements in all cases.

Did I miss the place where the standard defines this behaviour? Why do the three C++ libraries I looked at disagree with each other? Why does the libstdc++ comment say it’s only an issue for insert(const_iterator, const T&)? If the standard doesn’t require this to work, why do the libraries ever bother to make it work at all? (Surely this costs some copies and/or moves that could otherwise be avoided.) Finally, if I’m implementing a container that should resemble std::vector, should I make this work?

回答1:

To answer the second question first: the standard explicitly says that the standard library is allowed to assume that when passing something by rvalue reference, that rvalue reference is the only reference to that object. This means that it cannot legally be an element of the vector. The relevant part of C++11 17.6.4.9/1:

  • If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. ... [ Note: If a program casts an lvalue to an xvalue while passing that lvalue to a library function (e.g. by calling the function with the argument move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument was an lvalue. —end note ]

This leaves us just to handle the const T & case. And even though libstdc++ and libc++ differ in this case, their net result is the same—they will correctly copy from the object passed in. And the standard only prescribes behaviour, not implementation. As long as they achieve the correct behaviour, they're fine.