stdcxx-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Travis Vitek (JIRA)" <j...@apache.org>
Subject [jira] Commented: (STDCXX-495) bug in vector::insert(iterator, const T&) inserting end()
Date Fri, 20 Jun 2008 22:45:45 GMT

    [ https://issues.apache.org/jira/browse/STDCXX-495?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12606926#action_12606926
] 

Travis Vitek commented on STDCXX-495:
-------------------------------------

The patch causes test {{23.vector.allocator.cpp}} to fail. I actually believe that the test
is broken because the allocator requirements [lib.allocator.requirements, table 32 and p4]
quite clearly say

{quote}
4 Implementations of containers described in this International Standard are permitted to
assume that their Allocator template parameter meets the following two additional requirements
beyond those in Table 32.

  -- All instances of a given allocator type are required to be interchangeable and always
compare equal to each other.
  -- The typedef members pointer, const_pointer, size_type, and difference_type are required
to be T*, T const*, size_t and ptrdiff_t, respectively.

5 Implementors are encouraged to supply libraries that encapsulate more general memory models
and that support non-equal instances. In such implementations, any requirements imposed on
allocators by containers beyond those requirements that appear in Table 32, and the semantics
of containers and algorithms when allocator instances compare non-equal, are implementation-defined.
{quote}

I'm not sure I fully understand what paragraph 5 means wrt the second requirement in paragraph
4. Perhaps we should add {{template <class T> T* __rw_address(T&)}} that allows
us to get the address of of an object even if that object defines unary {{operator&}}.


> 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 <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.


Mime
View raw message