stdcxx-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Sebor (JIRA)" <j...@apache.org>
Subject [jira] Issue Comment Edited: (STDCXX-690) [LWG #198] std::reverse_iterator::operator*() invalidates cached values
Date Tue, 20 May 2008 18:35:56 GMT

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

sebor edited comment on STDCXX-690 at 5/20/08 11:34 AM:
---------------------------------------------------------------

I think the issue is bogus and should be reverted. See my post below for details:

-------- Original Message --------
Subject: Re: effects of reverse_iterator::operator*() and operator->()
Date: Tue, 08 Jan 2008 13:47:15 -0700
From: Martin Sebor <sebor@roguewave.com>
Reply-To: c++std-lib@accu.org
Organization: Rogue Wave Software, Inc.
To: undisclosed-recipients:;
References: <478295EB.8000604@roguewave.com> <CA364800-468C-4644-8820-98E2CA5E91CA@twcny.rr.com>
<4782B952.9070601@roguewave.com> <4782C0CB.3070309@suse.de>

To: C++ libraries mailing list
Message c++std-lib-19976

I think there's a fundamental problem with issue 198. It acknowledges
that the standard "assumes that pointers and references obtained from
an iterator are still valid after iterator destruction or change"
while at the same time trying to improve reverse_iterator to make it
work with iterators that violate this assumption by caching the last
dereferenced value and invalidating it after a change to the iterator.

The solution of assigning the value of current to a member variable
with the intent of preserving the last value the iterator might have
cached, will in all likelihood overwrite the previously cached value,
and thus effectively invalidate references to elements previously
read from the sequence. I.e., the solution doesn't guarantee that
references to objects obtained from a reverse_iterator remain valid
until throughout the lifetime of the iterator since incrementing or
decrementing the iterator might still invalidate references obtained
from it.

Since apparently no implementation has adopted the resolution of
issue 198 yet and the solution doesn't go far enough I suggest we
revert to the original text and document this as a limitation of
reverse_iterators.

Martin

A test case that demonstrates the problem is below.

{noformat}
#include <cassert>
#include <iterator>

struct Iterator: std::iterator<std::random_access_iterator_tag, int>
{
    int *cur;
    int cache;

    Iterator (int *p = 0): cur (p) { }
    ~Iterator () { cache = ~cache; }

    reference operator*() { return cache; }

    Iterator& operator++() { cache = *++cur; return *this; }
    Iterator& operator--() { cache = *--cur; return *this; }
};


int main ()
{
    int a[] = { 1, 2, 3 };
    Iterator it (a + sizeof a / sizeof *a);

    std::reverse_iterator<Iterator> rit (it);

    const int &ref = *rit;
    const int val = ref;

    ++rit; *rit;
    assert (val == ref);   // holds with LWG #198 implemented

    ++rit; *rit;
    assert (val == ref);   // fails even with LWG #198
}
{noformat}

      was (Author: sebor):
    I think the issue is bogus and should be reverted. See my post below for details:

-------- Original Message --------
Subject: Re: effects of reverse_iterator::operator*() and operator->()
Date: Tue, 08 Jan 2008 13:47:15 -0700
From: Martin Sebor <sebor@roguewave.com>
Reply-To: c++std-lib@accu.org
Organization: Rogue Wave Software, Inc.
To: undisclosed-recipients:;
References: <478295EB.8000604@roguewave.com> <CA364800-468C-4644-8820-98E2CA5E91CA@twcny.rr.com>
<4782B952.9070601@roguewave.com> <4782C0CB.3070309@suse.de>

To: C++ libraries mailing list
Message c++std-lib-19976

I think there's a fundamental problem with issue 198. It acknowledges
that the standard "assumes that pointers and references obtained from
an iterator are still valid after iterator destruction or change"
while at the same time trying to improve reverse_iterator to make it
work with iterators that violate this assumption by caching the last
dereferenced value and invalidating it after a change to the iterator.

The solution of assigning the value of current to a member variable
with the intent of preserving the last value the iterator might have
cached, will in all likelihood overwrite the previously cached value,
and thus effectively invalidate references to elements previously
read from the sequence. I.e., the solution doesn't guarantee that
references to objects obtained from a reverse_iterator remain valid
until throughout the lifetime of the iterator since incrementing or
decrementing the iterator might still invalidate references obtained
from it.

Since apparently no implementation has adopted the resolution of
issue 198 yet and the solution doesn't go far enough I suggest we
revert to the original text and document this as a limitation of
reverse_iterators.

Martin

A test case that demonstrates the problem is below.

#include <cassert>
#include <iterator>

struct Iterator: std::iterator<std::random_access_iterator_tag, int>
{
    int *cur;
    int cache;

    Iterator (int *p = 0): cur (p) { }
    ~Iterator () { cache = ~cache; }

    reference operator*() { return cache; }

    Iterator& operator++() { cache = *++cur; return *this; }
    Iterator& operator--() { cache = *--cur; return *this; }
};


int main ()
{
    int a[] = { 1, 2, 3 };
    Iterator it (a + sizeof a / sizeof *a);

    std::reverse_iterator<Iterator> rit (it);

    const int &ref = *rit;
    const int val = ref;

    ++rit; *rit;
    assert (val == ref);   // holds with LWG #198 implemented

    ++rit; *rit;
    assert (val == ref);   // fails even with LWG #198
}

  
> [LWG #198] std::reverse_iterator::operator*() invalidates cached values
> -----------------------------------------------------------------------
>
>                 Key: STDCXX-690
>                 URL: https://issues.apache.org/jira/browse/STDCXX-690
>             Project: C++ Standard Library
>          Issue Type: Bug
>          Components: 24. Iterators
>    Affects Versions: 4.1.2, 4.1.3, 4.1.4, 4.2.0
>            Reporter: Martin Sebor
>            Priority: Minor
>
> According to LWG issue 198 (http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#198),
the implementation of reverse_iterator::operator*() should cache the "base" iterator to prevent
dangling references to values cached by it. The test case below demonstrates the problem caused
by not doing so:
> $ cat t.cpp && make t && ./t
> #include <cassert>
> #include <iterator>
> struct Iterator: std::iterator<std::random_access_iterator_tag, int>
> {
>     int *cur;
>     int cache;
>     Iterator (int *p = 0): cur (p) { }
>     ~Iterator () { cache = ~cache; }
>     reference operator*() { return cache; }
>     Iterator& operator++() { cache = *++cur; return *this; }
>     Iterator& operator--() { cache = *--cur; return *this; }
> };
> int main ()
> {
>     int a[] = { 1, 2, 3 };
>     Iterator it (a + sizeof a / sizeof *a);
>     std::reverse_iterator<Iterator> rit (it);
>     const int &ref = *rit;
>     const int val = ref;
>     ++rit;
>     assert (val == ref);
> }
> gcc -c -I/home/sebor/stdcxx/include/ansi -D_RWSTDDEBUG   -pthread -I/home/sebor/stdcxx/include
-I/build/sebor/stdcxx-gcc-4.1.2-15D/include -I/home/sebor/stdcxx/examples/include  -pedantic
-nostdinc++ -g   -W -Wall -Wcast-qual -Winline -Wshadow -Wwrite-strings -Wno-long-long -Wcast-align
  t.cpp
> gcc t.o -o t -pthread  -L/build/sebor/stdcxx-gcc-4.1.2-15D/lib  -Wl,-R/build/sebor/stdcxx-gcc-4.1.2-15D/lib
-lstd15D -lsupc++ -lm 
> t: t.cpp:29: int main(): Assertion `val == ref' failed.
> Aborted

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