You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@stdcxx.apache.org by "Travis Vitek (JIRA)" <ji...@apache.org> on 2008/06/06 18:43:45 UTC
[jira] Assigned: (STDCXX-495) bug in vector::insert(iterator, const
T&) inserting end()
[ https://issues.apache.org/jira/browse/STDCXX-495?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Travis Vitek reassigned STDCXX-495:
-----------------------------------
Assignee: Travis Vitek
> bug in vector::insert(iterator, const T&) inserting end()
> ---------------------------------------------------------
>
> Key: STDCXX-495
> URL: https://issues.apache.org/jira/browse/STDCXX-495
> Project: C++ Standard Library
> Issue Type: Bug
> Components: 23. Containers
> Affects Versions: 4.1.2, 4.1.3
> Reporter: Martin Sebor
> Assignee: Travis Vitek
> Fix For: 4.3
>
> Attachments: 23.vector.modifiers.stdcxx-495.cpp, vector.cc.diff
>
>
> 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 [mailto:Boris.Gubenko@hp.com]
> > 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 <se...@roguewave.com>
> To: Boris.Gubenko@hp.com
> CC: oemsupport@roguewave.com
> 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 sebor@roguewave.com 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 <Bo...@hp.com>
> Reply-To: Boris Gubenko <Bo...@hp.com>
> Organization: Hewlett-Packard Co.
> To: Dennis Handly <dh...@cup.hp.com>, Martin Sebor <se...@roguewave.com>
> CC: Boris Gubenko <Bo...@hp.com>
> References: <20...@hpcll183.cup.hp.com>
> <42...@roguewave.com>
> 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" <se...@roguewave.com>
> To: "Dennis Handly" <dh...@cup.hp.com>
> Cc: <Bo...@hp.com>; <ac...@cup.hp.com>
> 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 sebor@roguewave.com 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 <dh...@cup.hp.com>
> To: Boris.Gubenko@hp.com, dhandly@cup.hp.com, sebor@roguewave.com
> >From: "Boris Gubenko" <Bo...@hp.com>
> >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 sebor@roguewave.com 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 <se...@roguewave.com>
> To: Dennis Handly <dh...@cup.hp.com>
> CC: Boris.Gubenko@hp.com
> References: <20...@hpcll183.cup.hp.com>
> Dennis Handly wrote:
> >>From: "Boris Gubenko" <Bo...@hp.com>
> >>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 sebor@roguewave.com 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 <dh...@cup.hp.com>
> To: dhandly@cup.hp.com, sebor@roguewave.com
> CC: Boris.Gubenko@hp.com
> >From: Martin Sebor <se...@roguewave.com>
> >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 sebor@roguewave.com 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 <se...@roguewave.com>
> To: Dennis Handly <dh...@cup.hp.com>
> CC: Boris.Gubenko@hp.com
> References: <20...@hpcll183.cup.hp.com>
> Dennis Handly wrote:
> >>From: Martin Sebor <se...@roguewave.com>
> >>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 sebor@roguewave.com 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 <dh...@cup.hp.com>
> To: dhandly@cup.hp.com, sebor@roguewave.com
> CC: Boris.Gubenko@hp.com, al.simons@hp.com
> >From: Martin Sebor <se...@roguewave.com>
> >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 sebor@roguewave.com 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 <se...@roguewave.com>
> To: Boris Gubenko <Bo...@hp.com>
> CC: Dennis Handly <dh...@cup.hp.com>
> References: <20...@hpcll183.cup.hp.com>
> <42...@roguewave.com>
> <01...@americas.hpqcorp.net>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.