134
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?

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • There's a bug in Visual Studio 2010: http://stackoverflow.com/questions/10218223/how-to-insert-a-duplicate-element-into-a-vector – Mark Ransom Sep 13 '13 at 15:05
  • 4
    A note: There is currently a discussion in the standard proposals forum. As part of it, someone gave an [example implementation of `push_back`](https://groups.google.com/a/isocpp.org/d/msg/std-proposals/5BnNHEr07QM/-rZp1mYJTvAJ). Another poster [noted a bug in it](https://groups.google.com/a/isocpp.org/d/msg/std-proposals/5BnNHEr07QM/i8lb7fqKSWkJ), 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. – Benjamin Lindley Sep 13 '13 at 15:33
  • 9
    I'm sorry but I don't know which answer to accept as there is still controversy over the correct answer. – Neil Kirk Sep 13 '13 at 15:35
  • @BenjaminLindley: I think that "bug" was a matter of robustness working with real-world code, and not conformance. – Ben Voigt Sep 13 '13 at 15:48
  • Similar case: http://stackoverflow.com/questions/11511510/wrong-results-when-appending-vector-to-itself-using-copy-and-back-inserter/11511598#11511598 – Ben Voigt Sep 13 '13 at 19:45
  • 4
    I was asked to comment on this question by the 5th comment under: http://stackoverflow.com/a/18647445/576911. I'm doing so by upvoting every answer that currently says: yes, it is safe to push_back an element from the same vector. – Howard Hinnant Sep 14 '13 at 03:11
  • @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. – Ben Voigt Sep 15 '13 at 00:51
  • 1
    @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. – Howard Hinnant Sep 15 '13 at 02:15
  • @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. – Ben Voigt Sep 15 '13 at 02:43
  • 2
    @BenVoigt: 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: http://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. – Howard Hinnant Sep 15 '13 at 03:02
  • @BenVoigt Are you sure you could? There's quite a few rules in the Algorithms library about what your functions are allowed to do. – Sebastian Redl Sep 16 '13 at 12:56
  • @Sebastian, yeah pretty sure. I'll have to work up an example after work and see whether you can name any rule it violates. – Ben Voigt Sep 16 '13 at 13:40
  • @BenVoigt `Requires:` is a pre-condition, not an invariant. – OlivierD Sep 16 '13 at 21:40
  • @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). – Ben Voigt Sep 16 '13 at 23:37
  • @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. – OlivierD Sep 17 '13 at 19:26
  • @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. – Ben Voigt Sep 17 '13 at 20:08
  • 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! – DigitalZebra Sep 18 '13 at 20:09
  • 2
    @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. – Neil Kirk Sep 19 '13 at 09:27

9 Answers9

36

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.

Nate Kohl
  • 35,264
  • 10
  • 43
  • 55
  • 1
    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. – Ben Voigt Sep 15 '13 at 00:54
  • 5
    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. – OlivierD Sep 16 '13 at 21:36
  • 3
    @NeilKirk I think this should be the authorative answer, it is also mentioned by Stephan T. Lavavej [on Reddit](http://www.reddit.com/r/cpp/comments/vog1p/a_commonly_unknown_stdvector_pitfall/) using essentially the same arguments. – TemplateRex Sep 20 '13 at 12:50
  • `v.insert(v.begin(), v[2]);` cannot trigger a reallocation. So how does this answer the question? – ThomasMcLeod Mar 03 '17 at 16:20
  • 4
    @ThomasMcLeod: yes it can obviously trigger a reallocation. You are expanding the vector's size by inserting a new element. – Violet Giraffe Jul 23 '19 at 12:11
23

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.

Sebastian Redl
  • 69,373
  • 8
  • 123
  • 157
  • 9
    Some backing would really help here. – chris Sep 13 '13 at 14:32
  • Still looking. I know it's there, just have to find it. – Sebastian Redl Sep 13 '13 at 14:32
  • 3
    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());` ? – Matthieu M. Sep 13 '13 at 14:32
  • 2
    @MatthieuM. No: Table 100 says: "pre: i and j are not iterators into a". – Sebastian Redl Sep 13 '13 at 14:34
  • 2
    I'm upvoting now as this is my recollection as well, but a reference is needed. – bames53 Sep 13 '13 at 14:55
  • 1
    @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. – Ben Voigt Sep 13 '13 at 15:01
  • 4
    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." – Ben Voigt Sep 13 '13 at 19:07
13

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.

Angew is no longer proud of SO
  • 167,307
  • 17
  • 350
  • 455
  • 1
    Huh? How does any of that say anything about passing a reference which the call makes invalid? – Ben Voigt Sep 13 '13 at 15:02
  • 9
    I don't see how this guarantees this to be safe. – jrok Sep 13 '13 at 15:03
  • @upvoters: Please do not upvote an answer which contains Standardese unless you understand the Standardese! – Ben Voigt Sep 13 '13 at 15:04
  • 1
    I'm confused. How does this show that the copy must be made before the container is resized? – Nate Kohl Sep 13 '13 at 15:04
  • 2
    @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. – Nawaz Sep 13 '13 at 15:04
  • 1
    @Nawaz: Not if the global preconditions are violated, and the global preconditions are that you pass only valid references... – Ben Voigt Sep 13 '13 at 15:05
  • @BenVoigt It "Appends a copy of `t`". How can this invalidate `t`? At the time you pass the reference, it is valid. – Angew is no longer proud of SO Sep 13 '13 at 15:05
  • 6
    @Angew: It absolutely does invalidate `t`, the only question is whether before or after making the copy. Your last sentence is certainly wrong. – Ben Voigt Sep 13 '13 at 15:06
  • 5
    @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. – bames53 Sep 13 '13 at 15:06
  • @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. – Ben Voigt Sep 13 '13 at 15:07
  • 9
    @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. – bames53 Sep 13 '13 at 15:08
  • 5
    @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. – Ben Voigt Sep 13 '13 at 15:09
  • @BenVoigt: I think it would be really really bad for the vector if I were to interpret the text the way you do. – Nawaz Sep 13 '13 at 15:10
  • 4
    @Nawaz: I think there are many other member functions and algorithms that have no choice but to follow my interpretation. – Ben Voigt Sep 13 '13 at 15:10
  • 6
    @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". – bames53 Sep 13 '13 at 15:25
  • @BenVoigt There's also `accumulate` and `inner_product`, `partial_sum`, and `adjacent_difference`. – bames53 Sep 13 '13 at 15:39
  • @bames53 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? – Angew is no longer proud of SO Sep 13 '13 at 15:42
  • @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. – Ben Voigt Sep 13 '13 at 15:45
  • @bames: Ahh yes, the wording was sufficiently different that I didn't find those with search. – Ben Voigt Sep 13 '13 at 15:46
  • @BenVoigt I sort of know, but then again, e.g. the functor of `std::for_each()` is allowed to modify the sequence's elements. – Angew is no longer proud of SO Sep 13 '13 at 15:49
  • 1
    @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) – Ben Voigt Sep 13 '13 at 15:52
  • @BenVoigt: Ahh, I just came across [this session](http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil) 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. – Nawaz Sep 13 '13 at 16:02
  • 2
    @Nawaz: You're expecting Channel9 sessions to demonstrate portable code? – Ben Voigt Sep 13 '13 at 16:13
  • 1
    @BenVoigt: I'm just wondering if Sean Parent is wrong too and nobody seems to see the problem in his demo. – Nawaz Sep 13 '13 at 16:13
  • 2
    @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. – Ben Voigt Sep 13 '13 at 16:20
  • 1
    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 – bames53 Sep 14 '13 at 06:31
  • 1
    @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. – Ben Voigt Sep 14 '13 at 07:21
  • @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. – bames53 Sep 14 '13 at 07:31
  • 1
    @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*. – Ben Voigt Sep 14 '13 at 15:19
  • @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). – bames53 Sep 14 '13 at 18:48
  • @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. – Ben Voigt Sep 14 '13 at 19:05
  • 2
    @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. – bames53 Sep 14 '13 at 19:38
  • @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. – Ben Voigt Sep 15 '13 at 00:44
  • 2
    @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](http://en.wikipedia.org/wiki/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." – bames53 Sep 15 '13 at 02:03
  • @bames: The Standard is full of requirements on callers, which the term *precondition* does not adequately described (these requirements are preconditions and more) – Ben Voigt Sep 15 '13 at 02:07
  • 3
    @BenVoigt The standard specifically says that the 'Requirements' listed are preconditions: 17.5.14/3 – bames53 Sep 15 '13 at 02:11
  • @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. – Ben Voigt Sep 15 '13 at 02:40
  • 2
    @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. – bames53 Sep 15 '13 at 03:04
  • @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? – Ben Voigt Sep 15 '13 at 03:47
  • 2
    @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(). – bames53 Sep 15 '13 at 09:40
  • 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. – bames53 Sep 15 '13 at 09:52
  • @bames: But if x is a precondition of `C()` and `B()` has no effect on it, then how is described in `A()`'s contract? – Ben Voigt Sep 15 '13 at 16:06
  • 2
    Not as a precondition, because being a precondition would mean it doesn't matter whether B() has an effect on it or not. @BenVoigt – bames53 Sep 15 '13 at 16:16
  • @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. – Ben Voigt Sep 15 '13 at 21:19
  • 2
    @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](http://en.wikipedia.org/wiki/Precondition).) – bames53 Sep 15 '13 at 21:51
  • @bames53 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? – Mark B Sep 16 '13 at 15:45
  • 3
    @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'. – bames53 Sep 16 '13 at 15:56
  • @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?". – Johan Råde Sep 16 '13 at 16:39
7

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
                    ...
        }
    }
Johan Råde
  • 20,480
  • 21
  • 73
  • 110
3

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.
}
Nate Kohl
  • 35,264
  • 10
  • 43
  • 55
  • 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. – Ben Voigt Sep 13 '13 at 17:47
  • @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.) – Nate Kohl Sep 13 '13 at 19:08
2

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.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • 2
    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. – Ben Voigt Sep 13 '13 at 15:30
  • 5
    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. – cmaster - reinstate monica Sep 13 '13 at 18:25
  • -1. It is completely irrelevant quote and doesn't answer it anyway. The committee says `x.push_back(x[0])` is SAFE. – Nawaz Sep 21 '13 at 19:04
0

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.

Zaffy
  • 16,801
  • 8
  • 50
  • 77
-1

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.

OlivierD
  • 362
  • 1
  • 10
  • 2
    `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. – Konrad Rudolph Sep 13 '13 at 14:50
  • 4
    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. – Mike Seymour Sep 13 '13 at 14:50
  • 1
    `push_back` receives its argument [by reference](http://en.cppreference.com/w/cpp/container/vector/push_back). – bames53 Sep 13 '13 at 14:53
  • 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? – OlivierD Sep 13 '13 at 14:54
  • @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. – Nawaz Sep 13 '13 at 14:56
  • 1
    @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. – Ben Voigt Sep 13 '13 at 14:59
  • @BenVoigt: Just as a note, that is exactly what libc++ does. – Bill Lynch Sep 13 '13 at 15:01
  • 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. – Ben Voigt Sep 13 '13 at 15:33
  • @MikeSeymour Good point. I've modified my answer to be more specific. – OlivierD Sep 13 '13 at 15:34
  • 1
    @BenVoigt why else would a container require that a type be CopyInsertable if it's going to completely ignore that property anyway? – OlivierD Sep 13 '13 at 15:57
  • @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. – Ben Voigt Sep 13 '13 at 16:02
  • @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. – Ben Voigt Sep 13 '13 at 16:03
  • @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. – OlivierD Sep 13 '13 at 16:07
  • @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`. – Ben Voigt Sep 13 '13 at 16:14
  • @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. – OlivierD Sep 13 '13 at 16:20
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/37352/discussion-between-ben-voigt-and-olivierd) – Ben Voigt Sep 13 '13 at 16:22
-2

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.

Mark B
  • 95,107
  • 10
  • 109
  • 188