Return-Path: 
 <stdcxx-dev-return-5404-apmail-incubator-stdcxx-dev-archive=incubator.apache.org@incubator.apache.org>
Delivered-To: apmail-incubator-stdcxx-dev-archive@www.apache.org
Received: (qmail 84358 invoked from network); 9 Oct 2007 16:58:15 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2)
  by minotaur.apache.org with SMTP; 9 Oct 2007 16:58:15 -0000
Received: (qmail 36384 invoked by uid 500); 9 Oct 2007 16:53:11 -0000
Delivered-To: apmail-incubator-stdcxx-dev-archive@incubator.apache.org
Received: (qmail 36365 invoked by uid 500); 9 Oct 2007 16:53:11 -0000
Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:stdcxx-dev-help@incubator.apache.org>
List-Unsubscribe: <mailto:stdcxx-dev-unsubscribe@incubator.apache.org>
List-Post: <mailto:stdcxx-dev@incubator.apache.org>
List-Id: <stdcxx-dev.incubator.apache.org>
Reply-To: stdcxx-dev@incubator.apache.org
Delivered-To: mailing list stdcxx-dev@incubator.apache.org
Received: (qmail 36350 invoked by uid 99); 9 Oct 2007 16:53:11 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 09 Oct 2007 09:53:11 -0700
X-ASF-Spam-Status: No, hits=-100.0 required=10.0
	tests=ALL_TRUSTED
X-Spam-Check-By: apache.org
Received: from [140.211.11.4] (HELO brutus.apache.org) (140.211.11.4)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 09 Oct 2007 16:53:11 +0000
Received: from brutus (localhost [127.0.0.1])
	by brutus.apache.org (Postfix) with ESMTP id 8B24E714240
	for <stdcxx-dev@incubator.apache.org>; Tue,  9 Oct 2007 09:52:51 -0700 (PDT)
Message-ID: <4813743.1191948771566.JavaMail.jira@brutus>
Date: Tue, 9 Oct 2007 09:52:51 -0700 (PDT)
From: "Farid Zaripov (JIRA)" <jira@apache.org>
To: stdcxx-dev@incubator.apache.org
Subject: [jira] Updated: (STDCXX-495) bug in vector::insert(iterator, const
 T&) inserting end()
In-Reply-To: <969506.1185238651027.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
X-Virus-Checked: Checked by ClamAV on apache.org


     [ https://issues.apache.org/jira/browse/STDCXX-495?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Farid Zaripov updated STDCXX-495:
---------------------------------

    Attachment:     (was: vector.cc.diff)

> 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: Farid Zaripov
>             Fix For: 4.2.1
>
>
> 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 <sebor@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 <Boris.Gubenko@hp.com>
> Reply-To: Boris Gubenko <Boris.Gubenko@hp.com>
> Organization: Hewlett-Packard Co.
> To: Dennis Handly <dhandly@cup.hp.com>, Martin Sebor <sebor@roguewave.com>
> CC: Boris Gubenko <Boris.Gubenko@hp.com>
> References: <200504011133.DAA22828@hpcll183.cup.hp.com>
> <42518AF4.1040309@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" <sebor@roguewave.com>
> To: "Dennis Handly" <dhandly@cup.hp.com>
> Cc: <Boris.Gubenko@hp.com>; <acxx@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 <dhandly@cup.hp.com>
> To: Boris.Gubenko@hp.com, dhandly@cup.hp.com, sebor@roguewave.com
> >From: "Boris Gubenko" <Boris.Gubenko@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 <sebor@roguewave.com>
> To: Dennis Handly <dhandly@cup.hp.com>
> CC: Boris.Gubenko@hp.com
> References: <200504080806.BAA02921@hpcll183.cup.hp.com>
> Dennis Handly wrote:
> >>From: "Boris Gubenko" <Boris.Gubenko@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 <dhandly@cup.hp.com>
> To: dhandly@cup.hp.com, sebor@roguewave.com
> CC: Boris.Gubenko@hp.com
> >From: Martin Sebor <sebor@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 <sebor@roguewave.com>
> To: Dennis Handly <dhandly@cup.hp.com>
> CC: Boris.Gubenko@hp.com
> References: <200504111840.LAA06964@hpcll183.cup.hp.com>
> Dennis Handly wrote:
> >>From: Martin Sebor <sebor@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 <dhandly@cup.hp.com>
> To: dhandly@cup.hp.com, sebor@roguewave.com
> CC: Boris.Gubenko@hp.com, al.simons@hp.com
> >From: Martin Sebor <sebor@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 <sebor@roguewave.com>
> To: Boris Gubenko <Boris.Gubenko@hp.com>
> CC: Dennis Handly <dhandly@cup.hp.com>
> References: <200504011133.DAA22828@hpcll183.cup.hp.com>
> <42518AF4.1040309@roguewave.com>
> <016c01c53bc2$56a8bb80$29001c10@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.