[iterator] counting_iterator::reference should be value_type?
Hello, currently, counting_iterator<T>::reference is Incrementable const&. This makes reverse_iterator< counting_iterator<T> >::dereference return a reference to a temporary variable: typename super_t::reference dereference() const { return *boost::prior(this->base()); } IMO, the solution is to make counting_iterator return by value. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Jan 05 2009, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Hello,
currently, counting_iterator<T>::reference is Incrementable const&. This makes reverse_iterator< counting_iterator<T> >::dereference return a reference to a temporary variable:
typename super_t::reference dereference() const { return *boost::prior(this->base()); }
IMO, the solution is to make counting_iterator return by value.
But then it is no longer a C++03 random access iterator. Probably we need to make the reference type a parameter to counting_iterator. Could you please open a Trac ticket for this one? Thanks, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
currently, counting_iterator<T>::reference is Incrementable const&. This makes reverse_iterator< counting_iterator<T> >::dereference return a reference to a temporary variable:
typename super_t::reference dereference() const { return *boost::prior(this->base()); }
IMO, the solution is to make counting_iterator return by value.
But then it is no longer a C++03 random access iterator.
The same is true for a random_access_traversal transform_iterator with a functor returning by value. Why is this so bad?
Could you please open a Trac ticket for this one?
Done. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Jan 05 2009, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
currently, counting_iterator<T>::reference is Incrementable const&. This makes reverse_iterator< counting_iterator<T> >::dereference return a reference to a temporary variable:
typename super_t::reference dereference() const { return *boost::prior(this->base()); }
IMO, the solution is to make counting_iterator return by value.
But then it is no longer a C++03 random access iterator.
The same is true for a random_access_traversal transform_iterator with a functor returning by value. Why is this so bad?
It's not "so bad," it's just an unnecessary limitation. If you really need a random access counting iterator, you'd be out of luck. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
It's not "so bad," it's just an unnecessary limitation. If you really need a random access counting iterator, you'd be out of luck.
It seems to me that the standard should specify whether iterator::reference must outlive its iterator. Then the current counting_iterator is wrong. Or iterator::reference may die with its iterator, then reverse_iterator is wrong. If the C++ standard is quiet on this issue, maybe it should be clarified. -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Arno Schödl wrote:
It's not "so bad," it's just an unnecessary limitation. If you really need a random access counting iterator, you'd be out of luck.
It seems to me that the standard should specify whether iterator::reference must outlive its iterator. Then the current counting_iterator is wrong. Or iterator::reference may die with its iterator, then reverse_iterator is wrong. If the C++ standard is quiet on this issue, maybe it should be clarified.
It has been clarified for std::reverse_iterator, which should keep a valid iterator for the returned reference. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198 Bo Persson
on Tue Jan 06 2009, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
It's not "so bad," it's just an unnecessary limitation. If you really need a random access counting iterator, you'd be out of luck.
It seems to me that the standard should specify whether iterator::reference must outlive its iterator.
That's a separate issue. It doesn't.
Then the current counting_iterator is wrong.
Oh, then you mean that the standard should specify *that* iterator::reference must outlive the iterator. Then you should know that the standard did anticipate a similar issue: http://www.boost.org/doc/libs/1_37_0/libs/iterator/doc/facade-and-adaptor.ht... so it's probably intentional.
Or iterator::reference may die with its iterator, then reverse_iterator is wrong. If the C++ standard is quiet on this issue, maybe it should be clarified.
Go for it; write a paper! -- Dave Abrahams BoostPro Computing http://www.boostpro.com
It seems to me that the standard should specify whether iterator::reference must outlive its iterator. That's a separate issue. It doesn't.
I am confused. As far as I understand, Bo Persson just posted that this has been clarified: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198 So reference/pointer do not outlive their iterator, and in our case, boost::counting_iterator is correct and boost::reverse_iterator is wrong. Or what am I missing? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Tue Jan 06 2009, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
It seems to me that the standard should specify whether iterator::reference must outlive its iterator. That's a separate issue. It doesn't.
I am confused. As far as I understand, Bo Persson just posted that this has been clarified:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198
I see, yes, for the next standard.
So reference/pointer do not outlive their iterator, and in our case, boost::counting_iterator is correct and boost::reverse_iterator is wrong.
With respect to C++0x, that's correct. I wonder if this means we really are missing an important concept. It seems to me that the requirement to store a temporary iterator is a potentially high cost that can be avoided for most iterators, which have persistent referents. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Wed, Jan 7, 2009 at 12:46 AM, David Abrahams <dave@boostpro.com> wrote:
on Tue Jan 06 2009, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
It seems to me that the standard should specify whether iterator::reference must outlive its iterator. That's a separate issue. It doesn't.
I am confused. As far as I understand, Bo Persson just posted that this has been clarified:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198
I see, yes, for the next standard.
So reference/pointer do not outlive their iterator, and in our case, boost::counting_iterator is correct and boost::reverse_iterator is wrong.
With respect to C++0x, that's correct.
I wonder if this means we really are missing an important concept. It seems to me that the requirement to store a temporary iterator is a potentially high cost that can be avoided for most iterators, which have persistent referents.
I also wondered about this. Since this is often a problem when composing iterators, perhaps for the iterators we have control of we could have the reference type as a template parameter. This would be much like the iterator adaptor and facade code. Then perhaps it's possible to use a type generator to generate the appropriate result type based on the combination of iterators? I really haven't thought this through so I'm ready for the flaws and obvious errors to be pointed out! I hope this helps, but apologise if it ends up being just spam. Neil Groves
-- Dave Abrahams BoostPro Computing http://www.boostpro.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
With respect to C++0x, that's correct.
Probably no point implementing something that is incompatible with it.
I wonder if this means we really are missing an important concept. It seems to me that the requirement to store a temporary iterator is a potentially high cost that can be avoided for most iterators, which have persistent referents.
On the other hand, there are only few iterator users who care either way. On one side, there is reverse_iterator. On the other there is counting_iterator (but as far as performance is concerned, only those with fat value_types, counting_iterator<int> can return by value) and caching iterators. Among these, IMO, caching iterators are most relevant. Do you see more cases?
From http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198: "Andy Koenig pointed out that it is possible to rewrite reverse_iterator so that it no longer makes such an assumption." Do you know what he had in mind? I don't see a better solution than what you suggested, storing two iterators. Storing the iterator in decremented form does not work because of begin(). Applying the decrement on demand and storing an extra bool whether this has been done is ugly, does not save much for trivial pointer-sized iterators, and leads to inconsistent behavior for insertions/deletions on the underlying container depending on whether the reverse_iterator has been dereferenced or not.
I don't think introducing another trait is worthwhile unless we have more use cases than reverse_iterator. reverse_iterator::dereference is already slower due to the decrement, which is probably more relevant in practice than the memory, in particular when iterating over data structures such as trees. So for optimum performance, reverse_iterator is already not the way. -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
participants (4)
-
Arno Schödl -
Bo Persson -
David Abrahams -
Neil Groves