Is it safe to push_back an element from the same vector?

Question

vector<int> v;
v.push_back(1);
v.push_back(v[0]);

If the second push_back causes a reallocation, the reference to the first integer in the vector will no longer be valid. So this isn't safe?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

This makes it safe?

Erbium

There's a bug in Visual Studio 2010: #10218723 – Hyaloid

A note: There is currently a discussion in the standard proposals forum. As part of it, someone gave an example implementation of push_back. Another poster noted a bug in it, that it didn't properly handle the case you describe. Nobody else, as far as I can tell, argued that this was not a bug. Not saying that's conclusive proof, just an observation. – Cento

I'm sorry but I don't know which answer to accept as there is still controversy over the correct answer. – Erbium

@BenjaminLindley: I think that "bug" was a matter of robustness working with real-world code, and not conformance. – Seven

Similar case: #11512010 – Seven

I was asked to comment on this question by the 5th comment under: https://mcmap.net/q/168488/-force-a-compile-time-error-if-std-move-will-result-in-an-unintended-copy. I'm doing so by upvoting every answer that currently says: yes, it is safe to push_back an element from the same vector. – Billiards

@HowardHinnant: Are you then saying that every Requires: clause and precondition in the entire Standard applies only when the function is called, and breaking them before the function returns is allowed unless it runs afoul of some other rule? Because that's the only way the Standard has been interpreted to allow this. – Seven

@BenVoigt: I'm saying that if this were not allowed, there would have to be a Requires prohibiting it. For example see Table 100 - Sequence container requirements, a.insert(p,i,j), pre: i and j are not iterators into a. Also see [res.on.arguments]/p1/b3 that effectively says that if you do v.push_back(move(v[0])); then it is not guaranteed to work. If you move something, the std::lib is allowed to assume what you moved is truly a prvalue. But I know of no restrictions concerning v.push_back(v[0]);. Additionally I'm aware that all std::lib implementors work hard to make this work. – Billiards

@Howard: So you're saying that although the Standard requires passing a valid reference to push_back, it's ok to pass one that you know is subject to imminent invalidation? With that limited view of the functions Requires aka preconditions, I could break most if not all algorithms described in the Standard. – Seven

@BenVoigt: <shrug> If you disagree with what the standard says, or even if you agree with the standard, but do not think it says it clearly enough, this is always an option for you: cplusplus.github.io/LWG/lwg-active.html#submit_issue I've taken this option myself more times than I can remember. Sometimes successfully, sometimes not. If you want to debate what the standard says, or what it should say, SO is not an effective forum. Our conversation has no normative meaning. But you can have a chance at a normative impact by following the link above. – Billiards

@BenVoigt Are you sure you could? There's quite a few rules in the Algorithms library about what your functions are allowed to do. – Avner

@Sebastian, yeah pretty sure. I'll have to work up an example after work and see whether you can name any rule it violates. – Seven

@BenVoigt Requires: is a pre-condition, not an invariant. – Kashmir

@OlivierD: There are two different definitions to the word invariant also. One is a fact that is always true when a certain line of code is reached. A precondition certainly qualifies as this type of invariant. Another is fact that holds from the end of the constructor until the beginning of destruction, possibly with exceptions while a lock is held. That second definition doesn't really apply to function arguments (other than constructor arguments which are stored for the lifetime of the object, for example with data members of reference type). – Seven

@BenVoigt A pre-condition does not qualify as an invariant. An invariant on the other hand is also a pre-condition. That being said, an invariant can be for any sub-program, whether a class, module, method, function, loop, or simple block of code. In regards to the C++ specifications, I believe Requires: means pre-condition, and not invariant. The pre-condition only needs to hold immediately prior to the execution of the sub-program. – Kashmir

@OlivierD: Is a "loop invariant" an invariant? Yes, a precondition is an invariant -- for at minimum a trivial (empty) basic block at the beginning of the function. – Seven

Could someone explain to me why the first example in the question would be unsafe? I'm a bit of a newbie, and I'm having trouble why it could possibly be unsafe. Thanks! – Kayleen

@Polaris878 If push_back causes the vector to reach its capacity, the vector will allocate a new bigger buffer, copy over the old data, and then delete the old buffer. Then it will insert the new element. The problem is, the new element is a reference to data in the old buffer which has just been deleted. Unless push_back makes a copy of the value before deleting, it will be a bad reference. – Erbium

Answer 1

It looks like http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 addressed this problem (or something very similar to it) as a potential defect in the standard:

1) Parameters taken by const reference can be changed during execution of the function

Examples:

Given std::vector v:

v.insert(v.begin(), v[2]);

v[2] can be changed by moving elements of vector

The proposed resolution was that this was not a defect:

vector::insert(iter, value) is required to work because the standard doesn't give permission for it not to work.

Wakerife

I find permission in 17.6.4.9: "If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined." If reallocation occurs, then all iterators and references to elements are invalidated, meaning the parameter reference passed to the function is invalid as well. – Seven

I think the point is that the implementation is responsible for doing the reallocation. It is incumbent upon it to ensure the behaviour is defined if the input is initially defined. Since the specs clearly specify that push_back makes a copy, implementations must, at the expense of execution time perhaps, cache or copy all values before de-allocating. Since in this particular question there is no external references left, it doesn't matter if iterators and references are invalidated. – Kashmir

@NeilKirk I think this should be the authorative answer, it is also mentioned by Stephan T. Lavavej on Reddit using essentially the same arguments. – Markman

v.insert(v.begin(), v[2]); cannot trigger a reallocation. So how does this answer the question? – Potty

@ThomasMcLeod: yes it can obviously trigger a reallocation. You are expanding the vector's size by inserting a new element. – Tepid

Answer 2

Yes, it's safe, and standard library implementations jump through hoops to make it so.

I believe implementers trace this requirement back to 23.2/11 somehow, but I can't figure out how, and I can't find something more concrete either. The best I can find is this article:

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

Inspection of libc++'s and libstdc++'s implementations shows that they are also safe.

Avner

Some backing would really help here. – Morass

Still looking. I know it's there, just have to find it. – Avner

That is interesting, I must admit I had never considered the case but indeed it seems quite difficult to achieve. Does it also holds for vec.insert(vec.end(), vec.begin(), vec.end()); ? – Tournai

@MatthieuM. No: Table 100 says: "pre: i and j are not iterators into a". – Avner

I'm upvoting now as this is my recollection as well, but a reference is needed. – Ens

@MatthieuM.: vec.insert(vec.end(), vec.begin(), vec.end()); is never safe, because iterators at and after the insertion point are always invalidated, even if there is no reallocation, and vec.end() is such an iterator. – Seven

Is 23.2/11 in the version you're using "Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container." ? But vector.push_back DOES otherwise specify. "Causes reallocation if the new size is greater than the old capacity." and (at reserve) "Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence." – Seven

Answer 3

The standard guarantees even your first example to be safe. Quoting C++11

[sequence.reqmts]

3 In Tables 100 and 101 ... X denotes a sequence container class, a denotes a value of X containing elements of type T, ... t denotes an lvalue or a const rvalue of X::value_type

16 Table 101 ...

Expression a.push_back(t) Return type void Operational semantics Appends a copy of t. Requires: T shall be CopyInsertable into X. Container basic_string, deque, list, vector

So even though it's not exactly trivial, the implementation must guarantee it will not invalidate the reference when doing the push_back.

Impaction

Huh? How does any of that say anything about passing a reference which the call makes invalid? – Seven

I don't see how this guarantees this to be safe. – Rosaniline

@upvoters: Please do not upvote an answer which contains Standardese unless you understand the Standardese! – Seven

I'm confused. How does this show that the copy must be made before the container is resized? – Wakerife

@jrok: I think "Appends a copy of t" means the push_back behaves as if the argument is passed by value. I'm not sure though. – Rationalize

@Nawaz: Not if the global preconditions are violated, and the global preconditions are that you pass only valid references... – Seven

@BenVoigt It "Appends a copy of t". How can this invalidate t? At the time you pass the reference, it is valid. – Impaction

@Angew: It absolutely does invalidate t, the only question is whether before or after making the copy. Your last sentence is certainly wrong. – Seven

@BenVoigt Since t meets the listed preconditions the described behavior is guaranteed. An implementation is not permitted to invalidate a precondition and then use that as an excuse not to behave as specified. – Ens

@bames53: You the developer are passing a reference which you know will not be valid for the duration of the call -- you have violated the precondition. – Seven

@BenVoigt The client is not obligated to maintain the precondition throughout the call; only to ensure that it is met at the initiation of the call. – Ens

@barnes: I disagree. For example, are you claiming that std::for_each is required to work even if the functor invalidates the end iterator for the range? How would it even discover the new valid end iterator? You must ensure the preconditions are met throughout the call. – Seven

@BenVoigt: I think it would be really really bad for the vector if I were to interpret the text the way you do. – Rationalize

@Nawaz: I think there are many other member functions and algorithms that have no choice but to follow my interpretation. – Seven

@BenVoigt That's a good point but I believe there's that the functor passed to for_each is required not to invalidate the iterators. I can't come up with a reference for for_each, but I see on some algorithms text like "op and binary_op shall not invalidate iterators or subranges". – Ens

@BenVoigt There's also accumulate and inner_product, partial_sum, and adjacent_difference. – Ens

@Ens Basically, I'd say it's most algorithms which take a functor and are not listed under "Non-modifying sequence operations." Perhaps somebody forgot to formalise the heading as a requirement? – Impaction

@Angew: "non-modifying" has nothing to do with it, that refers to whether the algorithm itself will modify the sequence. None of the algorithms is going to work right if its callback functor modifies the sequence being iterated in a way that invalidates iterators. – Seven

@bames: Ahh yes, the wording was sufficiently different that I didn't find those with search. – Seven

@BenVoigt I sort of know, but then again, e.g. the functor of std::for_each() is allowed to modify the sequence's elements. – Impaction

@Angew: Yes, it can modify elements, but not the sequence structure, since that would violate the global precondition that the iterators passed to for_each have to be valid (for the duration of the call). (Well, some containers would permit some structural modifications and still guarantee that iterators and references remain valid) – Seven

@BenVoigt: Ahh, I just came across this session by Sean Parent at channel9. See the implementation of commit() at 19:11. He has written x.push_back(x.back());. Now I see there is someone who interpreted the text the way I did. – Rationalize

@Nawaz: You're expecting Channel9 sessions to demonstrate portable code? – Seven

@BenVoigt: I'm just wondering if Sean Parent is wrong too and nobody seems to see the problem in his demo. – Rationalize

@Nawaz: That code DOES work on Visual C++. Does he claim it works on any other compiler/library? He'd only be wrong if he made a claim about portability. – Seven

Another answer has pointed to a library defect report on this and the committee judged it as not a defect, saying it's already specified that this is safe. So I'd say their understanding of 'precondition' matches the conventional one; that meeting preconditions at the initiation of the call is sufficient for fulfilling preconditions. Requirements on functors to avoid invalidation during an the execution is an independent requirement. If there's a defect then it's that the spec neglects to state that the for_each functor must not invalidate ranges. @BenVoigt – Ens

@bames: That way lies insanity. The Requires: documentation is a precondition, but it's not only a precondition. It is stronger. Or do you consider it a defect that the Standard neglects to say that copy constructors must not invalidate iterators and neglects to say that move constructors must not invalidate iterators and neglects to say that allocator calls must not invalidate iterators and that iterator increment functions must not invalidate iterators. That's going to be very messy very fast. No, the Requires: clauses have to apply to the entire duration of the call. – Seven

@BenVoigt in the case of those algorithms that state that functors must not invalidate the range, it seems they already do specify that the copy, move, etc. operation not invalidate; they don't limit their prohibition on invalidation to operator(). But wether that's a defect or not, the committee has been clear about the proper interpretation of the requirements on insert, ensuring that this use is well defined and portable. – Ens

@bames: I don't mean binary_op's copy/move/whatever, I mean for the element type. If you read the requires: as "at the time of call only", I can find loopholes everywhere. – Seven

@BenVoigt Then sure, let those be rigorously specified. I don't think it would be messy either since it could be a few paragraphs that apply to all the algorithms, similar to the way they specify that you have to pass valid ranges in the first place (C++11 24.2.1/7, last sentence). – Ens

@bames: I think it should be explicitly specified yes, but I think it should be a global rule that preconditions must be maintained for the entire duration of the call, with a few local exceptions. – Seven

@BenVoigt What benefit would that have except to make it no longer guaranteed that this call is safe? I prefer that 'preconditions' remain strictly preconditions and that any other requirements, such as that user's code called by the algorithm not invalidate ranges, be specified independently. It can be done simply and in a global place like the thing about iterator ranges being valid. – Ens

@bames: Allow passing a reference into same vector as a special case, here in push_back and insert. But the fact that requirements are expected to stay valid for the duration of the entire call is a very general principle. And no, there's no way to generally specify the requirement of not invalidating, because it is specific to the parameters of each algorithm. – Seven

@BenVoigt You haven't shown any benefit to making this change. "requirements are expected to stay valid for the duration of the entire call is a very general principle" That's not a precondition: "a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification." – Ens

@bames: The Standard is full of requirements on callers, which the term precondition does not adequately described (these requirements are preconditions and more) – Seven

@BenVoigt The standard specifically says that the 'Requirements' listed are preconditions: 17.5.14/3 – Ens

@bames: They are preconditions, because they need to hold before the call. But it doesn't say they are only required to hold at entry, nor can it mean that. Look at the next paragraph -- it describes equivalent-to semantics, and maps preconditions of functions invoked in the middle and end of the equivalent-to code to preconditions of the overall call, even though they need to hold when that invocation occurs, not merely when the parent is entered. Obviously, they aren't using the word preconditions in the way you want them to be. – Seven

@BenVoigt "But it doesn't say they are only required to hold at entry" That's exactly what it says and that's what the committee has reiterated in the response to library issue 526. "Look at the next paragraph" vector::push_back and vector::insert don't have 'Effects:' clauses and aren't specified as being 'Equivalent to' some code sequence, so 17.5.1.4/4 doesn't apply. – Ens

@bames: So the meaning of Requires: and preconditions includes the duration of the function for clauses that have equivalent code, but not for other clauses? – Seven

@BenVoigt No, the preconditions of a function are always only required to be met when the function is called. The preconditions of functions called in the equivalent code are not preconditions of the function. For example: Say functions A and B have no preconditions and function C has precondition x. Now say A is defined to be equivalent to B(); C();. x does not become a precondition of A(). If that precondition does not hold then it still may be okay to call A() as long as B() establishes precondition x for C(). – Ens

Additionally, say B has postcondition y; y does not become a postcondtion of A(), since C() might cause y to no longer be true. So it's not true that 17.5.1.4/4 "maps preconditions of functions invoked in the middle and end of the equivalent-to code to preconditions of the overall call." That's not what 17.5.1.4/4 is saying. – Ens

@bames: But if x is a precondition of C() and B() has no effect on it, then how is described in A()'s contract? – Seven

Not as a precondition, because being a precondition would mean it doesn't matter whether B() has an effect on it or not. @BenVoigt – Ens

@bames: But you're using the definition of "precondition" as used in functional programming. There's a second, broader meaning, which is the part of a function's contract which is provided by its caller. The function fulfilling its part of the contract and providing guarantees on behavior, side effects, and results, is preconditioned on the caller fulfilling its contract. The precondition come first in a logical sense, not necessarily a temporal sense. – Seven

@BenVoigt I'm using the term in the sense intended by the people that wrote the standard, not to mention that it is also the sense commonly used in programming (and not just functional programming. See Eiffel, for example, or just Wikipedia.) – Ens

@Ens With all due respect, how can you assert that you're using the term as intended by the standards committee? Have you talked to them directly? – Peak

@MarkB Because it is the commonly used sense and if the committee weren't using it this way then that would mean that the spec does give implementers latitude to produce UB in this case: the library working group's response to issue 526 is that this "is required to work because the standard doesn't give permission for it not to work," which implies that they are indeed using the common sense of 'precondition'. – Ens

@Ben Voigt: I think you have brought up a very interesting point. Maybe you should ask a new question at SO, "What is the exact meaning of a precondition in the C++ standard?". – Shufu

Answer 4

It is not obvious that the first example is safe, because the simplest implementation of push_back would be to first reallocate the vector, if needed, and then copy the reference.

But at least it seems to be safe with Visual Studio 2010. Its implementation of push_back does special handling of the case when you push back an element in the vector. The code is structured as follows:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }

Epigram

That's not a problem here, because the reference is now created after the reallocation and invalidation of references. – Seven

Wait, are you talking about the first or second snippet? – Seven

@Ben Voigt: I'm talking about the first snippet. – Shufu

I would like to know if the specification requires this to be safe. – Rationalize

According to the Standard it is not required to be safe. It is possible, however, to implement it in a safe manner. – Seven

@BenVoigt I'd say it is required to be safe (see my answer). – Impaction

@Angew: Your quote says nothing of the sort. It is a precondition that you only pass valid references... – Seven

@BenVoigt At the time you pass the reference, it is valid. – Impaction

@Angew: That isn't sufficient. You need to pass a reference that stays valid for the duration of the call, and this one doesn't. – Seven

I'm trying hard to understand the connection between your statement "The first snippet is not obviously safe" and the code you posted. – Rationalize

@Nawaz: Se my revised answer. – Shufu

Answer 5

This isn't a guarantee from the standard, but as another data point, v.push_back(v[0]) is safe for LLVM's libc++.

libc++'s std::vector::push_back calls __push_back_slow_path when it needs to reallocate memory:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}

Wakerife

The copy not only has to be made before deallocating the existing storage, but before moving from the existing elements. I suppose the moving of existing elements is done in __swap_out_circular_buffer, in which case this implementation is indeed safe. – Seven

@BenVoigt: good point, and you are indeed correct that the moving happens inside __swap_out_circular_buffer. (I've added some comments to note that.) – Wakerife

Answer 6

The first version is definitely NOT safe:

Operations on iterators obtained by calling a standard library container or string member function may access the underlying container, but shall not modify it. [ Note: In particular, container operations that invalidate iterators conflict with operations on iterators associated with that container. — end note ]

from section 17.6.5.9

---

Note that this is the section on data races, which people normally think of in conjunction with threading... but the actual definition involves "happens before" relationships, and I don't see any ordering relationship between the multiple side-effects of push_back in play here, namely the reference invalidation seems not to be defined as ordered with respect to copy-constructing the new tail element.

Seven

It should be understood that's a note, not a rule, so it's explaining a consequence of the foregoing rule... and the consequences are identical for references. – Seven

The result of v[0] is not an iterator, likewise, push_back() does not take an iterator. So, from a language lawyer perspective, your argument is void. Sorry. I know, that most iterators are pointers, and the point of invalidating an iterator, is pretty much the same as for references, but the part of the standard that you cite, is irrelevant to the situation at hand. – Invagination

-1. It is completely irrelevant quote and doesn't answer it anyway. The committee says x.push_back(x[0]) is SAFE. – Rationalize

Answer 7

Here is a nice visualisation that the last element is created in the buffer before reallocation occur.

https://godbolt.org/z/jrYPdzWaq

Gunshot

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Petr

Answer 8

It is completely safe.

In your second example you have

v.reserve(v.size() + 1);

which is not needed because if vector goes out of its size, it will imply the reserve.

Vector is responsible for this stuff, not you.

Conductor

Answer 9

Both are safe since push_back will copy the value, not the reference. If you are storing pointers, that is still safe as far as the vector is concerned, but just know that you'll have two elements of your vector pointing to the same data.

Section 23.2.1 General Container Requirements

16

• a.push_back(t) Appends a copy of t. Requires: T shall be CopyInsertable into X.
• a.push_back(rv) Appends a copy of rv. Requires: T shall be MoveInsertable into X.

Implementations of push_back must therefore ensure that a copy of v[0] is inserted. By counter example, assuming an implementation that would reallocate before copying, it would not assuredly append a copy of v[0] and as such violate the specs.

Kashmir

push_back will however also resize the vector, and in a naive implementation this will invalidate the reference before copying occurs. So unless you can back this up by a citation from the standard, I’ll consider it wrong. – Indefinable

By "this", do you mean the first or the second example? push_back will copy the value into the vector; but (as far as I can see) that might happen after reallocation, at which point the reference it's trying to copy from is no longer valid. – Phalanx

push_back receives its argument by reference. – Ens

Think about this for a second: you have a push_back operation that causes your vector to need resizing. Do you resize and delete your buffer before adding the push_back value, or do you resize, copy all the data including the push_back, and then delete the old buffer? – Kashmir

@OlivierD: Either way, the object (which is passed as argument) doesn't exist anymore once you resize the vector. The reallocation, copy and deletion happen in a different function which doesn't know anything about push_back and its argument. – Rationalize

@OlivierD: It would have to (1) allocate new space (2) copy the new element (3) move-construct the existing elements (4) destroy the moved-from elements (5) free the old storage -- in THAT order -- to make the first version work. – Seven

@BenVoigt: Just as a note, that is exactly what libc++ does. – Refuse

Your interpretation of the Standard quote is totally off. The restrictions on a CopyInsertable type in no way restrict the actions of a function that uses a CopyInsertable type. – Seven

@MikeSeymour Good point. I've modified my answer to be more specific. – Kashmir

@BenVoigt why else would a container require that a type be CopyInsertable if it's going to completely ignore that property anyway? – Kashmir

@OlivierD: You are making no sense. CopyInsertable is a guarantee that your type makes to the container, not a guarantee that the container makes to you. For example, consider the vector constructor that takes a pattern and a count... it's going to copy that pattern many times, so it requires the pattern to be CopyInsertable and not disappear after the first copy. – Seven

@OlivierD: It sounds as if you're now arguing that because the argument is CopyInsertable, that push_back isn't allowed to invalidate iterators and references at all, even after it makes its copy? That's clearly not a reasonable interpretation. – Seven

@BenVoigt I'm not talking about invalidating iterators and references. I'm saying that after push_back(v[0]), the value of v[0] should be as it was before said push_back. – Kashmir

@OlivierD: You're talking about the expression v[0], and not the object(s) to which it refers? Now you're really stretching any possible meaning of CopyInsertable. – Seven

@BenVoigt The value of v[0] is by definition the object to which it refers. In no way does my statement imply that the reference of v[0] be unchanged. – Kashmir

let us continue this discussion in chat – Seven

Answer 10

From 23.3.6.5/1: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Since we're inserting at the end, no references will be invalidated if the vector isn't resized. So if the vector's capacity() > size() then it's guaranteed to work, otherwise it's guaranteed to be undefined behavior.

Peak

I believe that the specification actually guarantees this to work in either case. I'm waiting on a reference though. – Ens

There is no mention of iterators or iterator safety in the question. – Kashmir

@Kashmir the iterator part is superfluous here: I'm interested in the references portion of the quote. – Peak

It's actually guaranteed to be safe (see my answer, semantics of push_back). – Impaction