distance operation (24.3.4)
[This message has been crossposted to boost developers list, it has been done on purpose, as it affects both communities] [Sorry if it comes up twice on Boost] I have detected that the standard declares "distance" template at 24.3.4, as taking two "InputIterator" as parameters. IMHO, the parameters shoudl be "const InputIterator" as they should not be changed by that function. In fact, the version I have seen of STLPORT does implement it like that ("const InputIterator") violating the standard, while DINKUMWARE respects the standard defintion. This has given me some problems when trying to use BOOST libraries with BDS 2006 (which comes with Dinkumware library). The function "size" in boost::iterator_range is declared "const", so that when it calls "std::distance", it will do so with "const IteratorT" parameters. With STLPORT, there will be no problem, as the undelying iterato_traits do not change. But in the case of DINKUMWARE, the underlying iterator_traits change. This is specially evident when IteratorT is [const] char *, which is a valid random access iterator. "size" will call "std::distance" with "[const] char * const" parameters, which are non-valid random iterators. I feel that DINKUMWARE is right in following the standard, but STLPORT is right in following common sense. I suggest making both points of view meet: a standard with common sense, that declares "distance" as operating over "const InputIterator". Best regards, Zara
I have detected that the standard declares "distance" template at 24.3.4, as taking two "InputIterator" as parameters.
IMHO, the parameters shoudl be "const InputIterator" as they should not be changed by that function. In fact, the version I have seen of STLPORT does implement it like that ("const InputIterator") violating the standard, while DINKUMWARE respects the standard defintion.
It makes no difference: the function distance takes it's parameters by value so the two forms: template <class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last); and template <class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator const first, InputIterator const last); are actually exactly the same function (the const declaration only affects the mutability of the arguments within the scope of the function, they have no effect on the function's type).
This has given me some problems when trying to use BOOST libraries with BDS 2006 (which comes with Dinkumware library).
The function "size" in boost::iterator_range is declared "const", so that when it calls "std::distance", it will do so with "const IteratorT" parameters. With STLPORT, there will be no problem, as the undelying iterato_traits do not change.
But in the case of DINKUMWARE, the underlying iterator_traits change. This is specially evident when IteratorT is [const] char *, which is a valid random access iterator. "size" will call "std::distance" with "[const] char * const" parameters, which are non-valid random iterators.
That's unfortunately a compiler bug: the compiler is deducing the template parameters for distance as "T const" rather than "T", I've worked around this in the past by explicitly casting away the constantness of the arguments to distance, but it's a pain to get right all over the place, just to keep one broken compiler happy.... John.
On Wed, 15 Mar 2006 14:12:07 -0000, "John Maddock" <john@johnmaddock.co.uk> wrote:
I have detected that the standard declares "distance" template at 24.3.4, as taking two "InputIterator" as parameters. <snip>
It makes no difference: the function distance takes it's parameters by value so the two forms:
template <class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);
and
template <class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator const first, InputIterator const last);
are actually exactly the same function (the const declaration only affects the mutability of the arguments within the scope of the function, they have no effect on the function's type).
<...>
That's unfortunately a compiler bug: the compiler is deducing the template parameters for distance as "T const" rather than "T", I've worked around this in the past by explicitly casting away the constantness of the arguments to distance, but it's a pain to get right all over the place, just to keep one broken compiler happy....
Is it really a bug? AFAIK, the compiler is ordered to apply template function "distance" on two members of the class. The function is const, so the members must be const, in this case its final type will be "const char * const". So the template deduced automatically will have the type "const char * const" as "InputIterator", which is not a valid input iterator, as it may not step forward or backward. The compiler must be broken anyway, because changing the distance call to the explicit distance<iterator>(...), where iterator is the type defined within the struct (and thus, it should be "const char *") will not work either. Zara
Is it really a bug? AFAIK, the compiler is ordered to apply template function "distance" on two members of the class. The function is const, so the members must be const, in this case its final type will be "const char * const". So the template deduced automatically will have the type "const char * const" as "InputIterator", which is not a valid input iterator, as it may not step forward or backward.
There is a rule in template type deduction that the final const gets dropped: Given: template <class T> foo(T z); Then: int i; const int j; foo(i); // calls foo<int> foo(j); // also calls foo<int> This is to ensure consistency with non-template function calls, and also makes sense once you realise that foo<int> and foo<const int> would have the same signature and type anyway. John.
Zara wrote:
This is specially evident when IteratorT is [const] char *, which is a valid random access iterator.
Why do you think const char * is a valid random access iterator? It is merely an input iterator, and one of the many motivations for improved iterator categories. (Basically, no const-iterator can ever be more than an input iterator, as bidirectional iterator refines both input *and* output iterator. All the more advanced iterators are refinements of bidirectional.) -- AlisdairM
On Wed, 15 Mar 2006 19:06:08 +0000 (UTC), "AlisdairM" <alisdair.meredith@uk.renaultf1.com> wrote:
Zara wrote:
This is specially evident when IteratorT is [const] char *, which is a valid random access iterator.
Why do you think const char * is a valid random access iterator?
Yes, you are right. char * is a valid random access iteartor, const char * is only an input iterator, I was writing too fast.
On Thu, 16 Mar 2006 06:29:43 +0100, Zara <yozara@terra.es> wrote:
On Wed, 15 Mar 2006 19:06:08 +0000 (UTC), "AlisdairM" <alisdair.meredith@uk.renaultf1.com> wrote:
Zara wrote:
This is specially evident when IteratorT is [const] char *, which is a valid random access iterator.
Why do you think const char * is a valid random access iterator?
Yes, you are right. char * is a valid random access iteartor, const char * is only an input iterator, I was writing too fast.
*output iterator*. I am ashamed, seems I am unable to write what I am thinking... Zara
----- Original Message ----- From: "AlisdairM" <alisdair.meredith@uk.renaultf1.com> To: <boost@lists.boost.org> Sent: Wednesday, March 15, 2006 2:06 PM Subject: Re: [boost] distance operation (24.3.4)
This is specially evident when IteratorT is [const] char *, which is a valid random access iterator.
Why do you think const char * is a valid random access iterator?
It is merely an input iterator, and one of the many motivations for improved iterator categories.
(Basically, no const-iterator can ever be more than an input iterator, as bidirectional iterator refines both input *and* output iterator. All the more advanced iterators are refinements of bidirectional.)
Maybe I misunderstood you. Could you care to explain why const char * is NOT a valid random access iterator. 24.3.1.2 clearly states otherwise. Thanks, Sean
Sean Huang wrote:
Maybe I misunderstood you. Could you care to explain why const char * is NOT a valid random access iterator. 24.3.1.2 clearly states otherwise.
const char * is not a random access iterator because it is not an output iterator, therfore not a forward iterator, therefore not a bidirectional iterator and therefore not a random access iterator - 24.1 The iterator categories are defined in 24.1, iterator traits is simply an aid to deducing that category for a given iterator. As it happens, you have found a defect in the standard, that itetarator_traits< const T * > reports the wrong category. Of course my preferred fix would be to find a better category definition so that 24.3.1.2 was correct <g> -- AlisdairM
const char * is not a random access iterator because it is not an output iterator, therfore not a forward iterator, therefore not a bidirectional iterator and therefore not a random access iterator - 24.1
The iterator categories are defined in 24.1, iterator traits is simply an aid to deducing that category for a given iterator. As it happens, you have found a defect in the standard, that itetarator_traits< const T * > reports the wrong category. Of course my preferred fix would be to find a better category definition so that 24.3.1.2 was correct <g>
Hold your horses here: surely const char* most certainly *is* a random access iterator, albeit an immutable one. I don't see anything in 24.1 that requires OutputIterator semantics for anything except, well output iterators :-) Waiting to be shot down in flames yours, John.
John Maddock wrote:
Hold your horses here: surely const char* most certainly is a random access iterator, albeit an immutable one. I don't see anything in 24.1 that requires OutputIterator semantics for anything except, well output iterators :-)
24.1p3: "Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified; Bidirectional iterators also satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified." However, it has since been pointed out to me I was ignoring 24.1p4: "Besides its category, a forward, bidirectional, or random access iterator can also be mutable or constant depending on whether the result of the expression *i behaves as a reference or as a reference to a constant." which seems to contradict the previous paragraph, but is more consistent with expected use through the rest of the library. I am now no longer sure what is/is-not a random access iterator according to C++03, but supect the intent is to support-but-not-require output-iterator. Hopefully we can clear this up once and for all in the next standard. -- AlisdairM
On 3/16/06, AlisdairM <alisdair.meredith@uk.renaultf1.com> wrote:
const char * is not a random access iterator because it is not an output iterator, therfore not a forward iterator, therefore not a bidirectional iterator and therefore not a random access iterator - 24.1
I think that is wrong. Forward iterators are not output iterators. See http://www.sgi.com/tech/stl/ForwardIterator.html The only expressions a forward iterator has to support are x++ and ++x. Also, http://www.sgi.com/tech/stl/RandomAccessIterator.html specifically says the iterator has to support assignment only if its type is mutable. For example, vector<T>::const_iterator is a random access iterator.
participants (5)
-
AlisdairM -
David Benbennick -
John Maddock -
Sean Huang -
Zara