[STDCXX-495] bug in vector::insert(iterator, const T&) inserting end()

• Type: Bug
• Status: Reopened
• Priority: Major
• Resolution: Unresolved
• Affects Version/s: 4.1.2, 4.1.3
• Fix Version/s: 4.3.0
• Component/s: 23. Containers
• Patch Info: Patch Available
• Severity: Incorrect Behavior
• Assignee: Unassigned
• Reporter: Martin Sebor
• Created: 24/Jul/07 00:57
• Updated: 11/Jul/09 00:06

Description

Copied from Rogue Wave Bugzilla: http://bugzilla.cvo.roguewave.com/show_bug.cgi?id=1527

***Created By: sebor @ Nov 16, 2004 05:35:14 PM***
> ----Original Message----
> From: Boris Gubenko [e-mail]
> Sent: Monday, November 15, 2004 5:22 PM
> To: Rogue Wave OEM Suppo
> Subject: a problem in vector::insert(iterator position, const T& x)
>
>
> x.cxx below illustrates what appears to be a problem in the
> implementation of
>
> iterator insert(iterator position, const T& x);
>
> function from 23.2.4.3 - vector modifiers [lib.vector.modifiers] in the
> Rogue Wave standard C++ library.
>
> The program populates vector<int> with two integers – 1 and 2 – and
> calls v.insert(v.begin(), v.back()); to insert last element of the
> container at the front.
>
> With Rogue Wave library, the container becomes: 1, 1, 2. With all other
> libraries I could get my hands on – Dinkumware, gnu libstdc++ and
> STLport – the container becomes: 2, 1, 2 and this is the result I'd
> expect.
>
> The problem exists in both rw stdlib v2.0 which is the version of RW
> library we ship on our Alpha platforms Tru64 and AlphaVMS and in rw
> stdlib v3.0 which is the version of RW library we ship on iVMS (OpenVMS
> on Itanium).
>
> In both v2.0 and v3.0, the problem is in underlying insert_aux()
> function which does not save value of its second argument passed by
> reference before calling copy_backward() which reshuffles the container.
> This is how I fixed it in rw stdlib v3.0 (the fix in rw stdlib v2.0 is,
> basically, the same):
>
> template <class _TypeT, class _Allocator>
> void vector<_TypeT,_Allocator>::_C_insert_aux ( iterator __it,
> const_reference __x) {
> ...
> _CATCH (...)

{ > _RWSTD_VALUE_ALLOC(_C_value_alloc_type, destroy(__old_end)); > --_C_finish; > _RETHROW; > }

> #if defined(_DECCXX) && !defined(_DECFIXCXXL1883)
> const value_type __tmp = __x;
> #endif
> copy_backward (_it, _C_make_iter (_old_end - difference_type
> (1)) ,
> _C_make_iter (__old_end));
> #if defined(_DECCXX) && !defined(_DECFIXCXXL1883)
> *__it = __tmp;
> #else
> *__it = __x;
> #endif
> }
>
> Do you agree with the fix? Is there a better way of fixing this problem?
>
> Thanks,
> Boris Gubenko
> Compaq/HP C++ team
>
> x.cxx
> -----
> #include <vector>
> #include <iostream>
>
> using namespace std;
>
> void display_vector(const vector<int>& v)

{ > vector<int>::const_iterator it; > for(it = v.begin(); it != v.end(); ++it) > cout << *it << endl; > }

>
> main()

{ > vector<int> v; > v.push_back(1); > v.push_back(2); > cout << "before:" << endl; > display_vector(v); > v.insert(v.begin(), v.back()); > cout << "after:" << endl; > display_vector(v); > }

>

***Modified By: sebor @ Apr 11, 2005 02:54:47 PM***
Confirmed.

***Modified By: sebor @ Apr 11, 2005 05:15:17 PM***
-------- Original Message --------
Subject: Re: a problem in vector::insert(iterator position, const T& x)
Date: Tue, 16 Nov 2004 17:52:08 -0700
From: Martin Sebor <[e-mail]>
To: [e-mail]
CC: [e-mail]

Hi Boris,

I was going to respond that the behavior of the call to insert in
your test case was undefined (since the container modifies the object
referred to by the function argument). But a search of the archive of
the committee's mailing list turned up an old thread discussing this
issue (c++std-lib-8609). The conclusion of the discussion was that
this kind of single-element insertions should "work" while range
insertions are not required to. The committee clarified the text
for range insertions but left the specification of the single-element
overload of insert unchanged on the premise that the standard is clear
enough. I've filed PR #30574 to have this fixed in our implementation
of the library. Your proposed fix for this problem looks reasonable.

Martin

------- Additional Comments From [e-mail] 2005-04-11 16:23:56 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Thu, 7 Apr 2005 18:37:07 -0400
From: Boris Gubenko <[e-mail]>
Reply-To: Boris Gubenko <[e-mail]>
Organization: Hewlett-Packard Co.
To: Dennis Handly <[e-mail]>, Martin Sebor <[e-mail]>
CC: Boris Gubenko <[e-mail]>
References: <[e-mail]>
<[e-mail]>

I put a fix in the libraries we use on Tru64 and VMS.
Thanks.

This problem reminded me of the problem in
vector::insert(iterator, const_reference) that we
fixed last year for Tru64 and VMS platforms. I see,
that the library on HP-UX still has this problem.

Here is the test case and the result on HP-UX with and
without the fix:

x.cpp

---

#include <vector>
#include <iostream>

using namespace std;

void display_vector(const vector<int>& v) {
vector<int>::const_iterator it;
for(it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
}

int main()

{ vector<int> v; v.push_back(1); v.push_back(2); cout << "before:" << endl; display_vector(v); v.insert(v.begin(), v.back()); cout << "after:" << endl; display_vector(v); return 0; } granite> aCC -V aCC: HP aC++/ANSI C B3910B A.05.50 [May 15 2003] granite> aCC -I. x.cpp && a.out before: 1 2 after: 1 1 2 granite> aCC -I. -D__DECFIXCXXL1883 x.cpp && a.out before: 1 2 after: 2 1 2 granite> Here is the fix in <vector.cc> guarded with __DECFIXCXXL1883 macro (1883 is the number in cxxl_internal bug tracking system where we track issues related to C++ libraries on Tru64 and VMS): template <class _TypeT, class _Allocator> void vector<_TypeT,_Allocator>::_C_insert_aux ( iterator __position, const_reference __x) { ... _RETHROW; }

#ifdef __DECFIXCXXL1883
const value_type __tmp = __x;
#endif
copy_backward(_position, _C_make_iter(_old_end - 1) ,
_C_make_iter(__old_end));
#ifdef __DECFIXCXXL1883
*__position = __tmp;
#else
*__position = __x;
#endif
}
else {
// more memory needed
...

This is the same fix we applied to rw stdlib v2.0 and v3.0.

Dennis, if Martin agrees with this fix for HP-UX, you can
apply it and add the program above to the test system (this is,
actually, our library test cxxl_1883). I can do it myself if you
want me to, but only after April, 18th. I'm on vacation tomorrow,
next week I'll be in class and Monday, April, 18th is Boston
Marathon.

Boris

----- Original Message -----
From: "Martin Sebor" <[e-mail]>
To: "Dennis Handly" <[e-mail]>
Cc: <[e-mail]>; <[e-mail]>
Sent: Monday, April 04, 2005 2:44 PM
Subject: Re: vector<bool>::insert, off by one

> Dennis Handly wrote:
>> We've gotten a but report on CR JAGaf50801:
>> RW vector<bool>::insert returns a bad entry at the end
>>
>> It seems that both the -AA and -AP versions have this bug. And also
>> 3.1.0. I don't know about 4.0? Boris?
>
> We have PR #30331 that you reported last July (Re: Peren 6.3
> and vector<bool>::insert) that looks like it might be the same
> thing. The bug has the test case below. It's still on my list
> of things to do (along with the rest of vector<bool>).
>
> #include <cassert>
> #include <vector>
>
> int main ()
> {
> const bool a[] =

{ false, false, true, true }

;
>
> std::vector<bool> v (a, a + 3);
>
> const std::vector<bool>::iterator it = v.end () - 1;
>
> v.insert (it, true);
>
> const std::vector<bool> res (a, a + 4);
>
> assert (v == res);
> }
>
> ...
>> (I'm not sure if the insert N times is also broken?)
>
> It looks like it might be but to know for sure I'll have to finish
> the vector<bool> test that I've been working on.
>
>>
>> My solution is to remove the "- difference_type (1)" and ignore the
>> scary "avoid dereferencing end ()".
>> I.e. end() better be valid because we are going to store into it.
>>
>> So do I make sense??
>
> I think so, although shouldn't the destination range end at
> (end() + 1), like this:
>
> template <class _Allocator>
> void vector<bool,_Allocator >::
> _C_insert (iterator __it, bool __x)
> {
> _RWSTD_ASSERT_RANGE (begin (), __it);
>
> if (size () < capacity ())

{ > > const iterator __end = _C_end; > > _STD::copy_backward (__it, __end, ++_C_end); > > *__it = __x; > }

> else
> {
> ...
>
> Martin

------- Additional Comments From [e-mail] 2005-04-11 16:25:07 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Fri, 8 Apr 2005 01:06:57 -0700 (PDT)
From: Dennis Handly <[e-mail]>
To: [e-mail], [e-mail], [e-mail]

>From: "Boris Gubenko" <[e-mail]>
>This problem reminded me of the problem in vector::insert(iterator,
>const_reference) that we fixed last year for Tru64 and VMS platforms.

I thought you were talking about vector<bool> and that can't have that
problem unless vector<bool> is just vector of a bool. I.e. the
bool bit would have to be copied to a temp for the const bool&.

>Here is the test case and the result on HP-UX with and without the fix:
> v.insert(v.begin(), v.back());

This is illegal by 23.2.4.3(1):
Notes: 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.

This reference is after the insertion point. I assume we can use this
rule while we are inside the vector::insert.

>This is the same fix we applied to rw stdlib v2.0 and v3.0.

I'm not sure you needed to do this.

>if Martin agrees with this fix for HP-UX, you can apply it
Boris

------- Additional Comments From [e-mail] 2005-04-11 16:25:39 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Sun, 10 Apr 2005 14:56:50 -0600
From: Martin Sebor <[e-mail]>
To: Dennis Handly <[e-mail]>
CC: [e-mail]
References: <[e-mail]>

Dennis Handly wrote:
>>From: "Boris Gubenko" <[e-mail]>
>>This problem reminded me of the problem in vector::insert(iterator,
>>const_reference) that we fixed last year for Tru64 and VMS platforms.
>
>
> I thought you were talking about vector<bool> and that can't have that
> problem unless vector<bool> is just vector of a bool. I.e. the
> bool bit would have to be copied to a temp for the const bool&.
>
>
>>Here is the test case and the result on HP-UX with and without the fix:
>> v.insert(v.begin(), v.back());
>
>
> This is illegal by 23.2.4.3(1):
> Notes: 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.
>
> This reference is after the insertion point. I assume we can use this
> rule while we are inside the vector::insert.

There was a discussion on this subject on the reflector a few
years ago. Matt Austern gave a good summary (attached) with
a ton of cross-references to previous discussions. The gist
of his email is that single-element insertions must be able
to deal with an argument that references an element in the
sequence.

>
>
>>This is the same fix we applied to rw stdlib v2.0 and v3.0.
>
>
> I'm not sure you needed to do this.
>
>
>>if Martin agrees with this fix for HP-UX, you can apply it
>
> Boris
>
> Martin: Has there been an interpretation on passing an
iterator/reference
> into the vector into insert()?
>
> Is this a correctness issue? Or a QoI issue?

I'm afraid it's both I.e., the standard requires that it
work but a quality implementation should eliminate the extra
copy if possible.

>
> I would assume we can't copy the const ref parm because then Perennial
> would claim we are calling the copy constructor too many times.

I don't think this is detectable. There can pretty much always
be an extra copy or two, as long as the big-Oh complexity
requirements are met.

>
> And if the vector type was a 1 Mb class, wouldn't want to do that.

We may not have a choice.

Martin

------- Additional Comments From [e-mail] 2005-04-11 16:26:02 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Mon, 11 Apr 2005 11:40:00 -0700 (PDT)
From: Dennis Handly <[e-mail]>
To: [e-mail], [e-mail]
CC: [e-mail]

>From: Martin Sebor <[e-mail]>
>There was a discussion on this subject on the reflector a few
>years ago. Matt Austern gave a good summary (attached) with
>a ton of cross-references to previous discussions. The gist
>of his email is that single-element insertions must be able
>to deal with an argument that references an element in the sequence.

The reason it is a bad idea is that the user knows the size and expense
of making a copy. The template function doesn't.

>but a quality implementation should eliminate the extra copy if possible.
Martin

How, take the address and see if in range?

------- Additional Comments From [e-mail] 2005-04-11 16:26:43 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Mon, 11 Apr 2005 12:51:33 -0600
From: Martin Sebor <[e-mail]>
To: Dennis Handly <[e-mail]>
CC: [e-mail]
References: <[e-mail]>

Dennis Handly wrote:
>>From: Martin Sebor <[e-mail]>
>>There was a discussion on this subject on the reflector a few
>>years ago. Matt Austern gave a good summary (attached) with
>>a ton of cross-references to previous discussions. The gist
>>of his email is that single-element insertions must be able
>>to deal with an argument that references an element in the sequence.
>
>
> The reason it is a bad idea is that the user knows the size and expense
> of making a copy. The template function doesn't.
>
>
>>but a quality implementation should eliminate the extra copy if
possible.
>
> Martin
>
> How, take the address and see if in range?

That's what I was thinking of, yes. For something like a simple
integer it could mean quite a bit of overhead, but for non-POD
objects it might be a significant optimization. Compiler type
traits would help here. Are you working on/thinking about
implementing something like it yet? (They're already in the
TR and several of the are not implementable without at least
some help from the compiler.)

Martin

------- Additional Comments From [e-mail] 2005-04-11 16:27:12 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Mon, 11 Apr 2005 12:45:07 -0700 (PDT)
From: Dennis Handly <[e-mail]>
To: [e-mail], [e-mail]
CC: [e-mail], [e-mail]

>From: Martin Sebor <[e-mail]>
>Compiler type traits would help here. Are you working on/thinking about
>implementing something like it yet? (They're already in the TR and
>several of the are not implementable without at least some help from the
>compiler.)

I assume they will be done for aCC6 when EDG does them.

------- Additional Comments From [e-mail] 2005-04-11 16:27:58 ----

-------- Original Message --------
Subject: Re: vector<bool>::insert, off by one
Date: Mon, 11 Apr 2005 17:10:46 -0600
From: Martin Sebor <[e-mail]>
To: Boris Gubenko <[e-mail]>
CC: Dennis Handly <[e-mail]>
References: <[e-mail]>
<[e-mail]>
<016c01c53bc2$56a8bb80$[e-mail]>

Boris Gubenko wrote:
...
>
> Dennis, if Martin agrees with this fix for HP-UX, you can
> apply it and add the program above to the test system (this is,
> actually, our library test cxxl_1883). I can do it myself if you
> want me to, but only after April, 18th. I'm on vacation tomorrow,
> next week I'll be in class and Monday, April, 18th is Boston
> Marathon.

For some reason I was having trouble finding this in our bug tracking
database. I finally found it after I came across my response to you
(attached). The fix you propose still looks reasonable to me (with
the performance caveat mentioned by Dennis). I still haven't decided
on the best fix for our sources so the issue (PR #30574) remains open.

Martin