//template stuff removed for legibility
size_type size(It first, It last);

This is needed is because subtracting 2 pointers returns a ptrdiff_t
and there is no requirement that PTRDIFF_MAX be >= SIZE_MAX, yet you're
allowed to create objects larger than PTRDIFF_MAX on this
implementation. The general standard conforming way of doing this
requires a loop but on many implementations, subtraction and casting to
a size_t works. For the non-pointer case, the implementor can do
something fancy like determining that the positive range of
distance_type will fit into a size_type and doing simple subtraction.

void increase(It &it, size_type n);

This is here to match the fact that a container's operator[] and at()
take a size_type and it's kind of lame that the iterator version can't
do this too.

(I don't necessarily care whether or not these function are allowed (or
required) to call distance/advance (or std:: qualified versions, I
forget if this issue has been resolved or not) to take advantage of
user specialization but a note should be mentioned about this)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Me wrote:
> //template stuff removed for legibility
> size_type size(It first, It last);

What's size_type?  Do you mean
std::iterator_traits<It>::difference_type?  If so, this is precisely
what std::distance does.

> This is needed is because subtracting 2 pointers returns a ptrdiff_t
> and there is no requirement that PTRDIFF_MAX be >= SIZE_MAX, yet you're
> allowed to create objects larger than PTRDIFF_MAX on this
> implementation.

That's the whole point in having a difference_type typedef instead of
hard coding ptrdiff_t.  Unfortunately there is a slight problem -- if I
have an iterator can legitimately iterate over more values than
ULONG_MAX, what do I make difference_type?  It has to be a signed
iteragal type [24.1/1], so I can't use some arbitrary precission
integer class.  Perhaps there is an argument that *this* should be
address, perhaps by introducing a SignedInteger concept and allowing
any type that models SignedInteger to be used as a difference_type?

> The general standard conforming way of doing this
> requires a loop but on many implementations, subtraction and casting to
> a size_t works. For the non-pointer case, the implementor can do
> something fancy like determining that the positive range of
> distance_type will fit into a size_type and doing simple subtraction.
>
> void increase(It &it, size_type n);

Again, how does this differ from std::advance?  By having both
arguments of std::advance use independent template paramaters, viz.,

  template <typename InputIterator, typename Distance>
  void advance( InputIterator& i, Distance n );

rather than

  template <typename InputIterator>
  void advance( InputIterator& i,
                typename std::iterator_traits<InputIterator>
                  ::difference_type n );

the argument is not (necessarily) converted to a difference_type, and
so an implementation could correctly handle large unsigned values that
would not convert correctly to a difference_type.  (I'm not clear
whether an implementation is *required* to do so, though.)

> This is here to match the fact that a container's operator[] and at()
> take a size_type and it's kind of lame that the iterator version can't
> do this too.

But the size_type of a container must be unsigned whereas the argument
to std::advance may be negative -- are you not proposing to include
this with increase?

If you're looking for additional functions along the lines of
std::advance / std::distance for TR2 (it's too late for TR1 now), I
would have thought that boost::next / boost::prior would be very strong
candidates.  Just because they're trivial doesn't mean they're not
worth standardising!  That's my two cents, anyway.

--
Richard Smith

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Me" <anti_spam_email2003@yahoo.com> wrote in message
news:1142051351.108410.142720@z34g2000cwc.googlegroups.com...
> //template stuff removed for legibility
> size_type size(It first, It last);
> void increase(It &it, size_type n);

One thing that would be useful would be
template <class Iterator>
Iterator midpoint(Iterator first, Iterator last);

This would return an Iterator mid such that mid is an element of [first,
last), and
distance(mid, last) equals either distance(first, mid) or distance(first,
mid) - 1. Many algorithms on ranges need to calculate the midpoint of the
range as a first step.  For instance, both mergesort and median-of-three
quicksort do.  And the best algorithm for calculating this is different
depending on whether Iterator is a forward iterator, a bidirectional
iterator, or a random-access iterator.

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

(this is a top post and an inline post)
One of the fundamental problems with C/C++ is this. Let there be 3
integer types D, S, and Z. And lets make n.max() mean
numeric_limits<n>::max() (except an integral constant expression).

let S be an unsigned type large enough to allocate objects
let D be a signed distance type used to calculate the distance
let Z be a an unsigned type where Z.max() >= S.max()

For pointers:
S = size_t
D = ptrdiff_t
Z = some non-existant type that represents the address space

For files (this is more ugly/half-specified/broken especially on the C
side):
S = streampos
D = streamoff
Z = some non-existant type that represents the largest file size the OS
(or whatever) supports
(QoI/up to the programmer if S != Z. Weird things can happen here
depending on the choices the implementor does)

Ideally we would require D.max() >= S.max() (but this probably isn't
ever going to happen). So the standard works around this in two main
places:

T x[N];

N can be larger than D.max(). If sizeof(T[N]) is larger than SIZE_MAX,
the program isn't standard conforming. The other place is:

p[i], i[p] /* yuck */
p+i, i+p, p-i, i-p
p+=i, p-=i

To allow for size_t to be used on implementations where SIZE_MAX >
PTRDIFF_MAX, no conversions are done to the integer i. But as a
side-effect of this, implementations can allow non-standard conforming
programs that create objects larger > SIZE_MAX to work instead of
trying to work around this some other way.


The STL algorithms do no such workarounds:


- iterator_traits<T*>::difference_type is required to be ptrdiff_t

- There is no iterator_traits<T*>::size_type

- Arithmetic on std::reverse_iterator takes a difference_type instead
of being parameterized.

- "X::size_type can represent any non-negative value of
difference_type". Ok, great, lets look at a typical implementation of
vector<char>::max_size():

http://cvs.sourceforge.net/viewcvs.py/stlport/STLport/stlport/stl/_vector.h?rev=5.5&view=auto
size_type max_size() const {
 size_type __vector_max_size = size_type(-1) / sizeof(_Tp);
 typename allocator_type::size_type __alloc_max_size =
this->_M_end_of_storage.max_size();
 return (__alloc_max_size <
__vector_max_size)?__alloc_max_size:__vector_max_size;
}

We basically see that the container doesn't care if
vector<char>::size_max() > PTRDIFF_MAX so it's up the programmer to be
careful when mixing this with algorithms. The problem is that it's not
exactly clear if the container is allowed to call an algorithm function
and then have it do something undefined if this case occurs.

- The non-normative example 24.3.1/5 uses the difference_type/distance
function to compute the distance. This means that this suggested
example doesn't handle valid ranges larger than difference_type.max().
If you take a random sampling of STL algorithms across different
implementations, they do similar operations using the distance function
which essentially means every single STL algorithm that takes a range
of iterators cannot be larger than difference_type.max().

- std::distance, you can see from the "reachable" wording, this
implicitly requires the distance for random access iterators to be <=
difference_type.max().

So given all this. What's the point of std::advance taking a template
parameter? It seems pretty artificial for that to be the only thing
that works for ranges larger than difference_type.max().



Richard Smith wrote:
> Me wrote:
> > //template stuff removed for legibility
> > size_type size(It first, It last);
>
> What's size_type?  Do you mean
> std::iterator_traits<It>::difference_type?  If so, this is precisely
> what std::distance does.

Doh, obviously I screwed that one up (but I definitely don't mean
difference_type).

The intent is to require an implementation to define a function that
takes 2 pointers to a complete type and returns a size_t even if the
distance between them is larger than PTRDIFF_MAX (with the expectation
that the implementation will do whatever evil tricks necessary to make
this as fast as regular pointer subtraction instead of using a loop).
Given the proper wording in the standard, I think this would be a
suitable replacement (at least for the above requirements):

template<class It, class Dist = typename
std::iterator_traits<It>::difference_type>
Dist distance(It, It);

This would allow it to work for distances larger difference_type.max().
QoI implementations could allow for that Z.max() case above but it
definitely should be required for the S.max() case to work.

I personally would rather have iterator_traits have a size_type typedef
and there be a Size size() function instead (where Size is template
parameter that defaults to iterator_traits<It>::size_type).

> > This is needed is because subtracting 2 pointers returns a ptrdiff_t
> > and there is no requirement that PTRDIFF_MAX be >= SIZE_MAX, yet you're
> > allowed to create objects larger than PTRDIFF_MAX on this
> > implementation.
>
> That's the whole point in having a difference_type typedef instead of
> hard coding ptrdiff_t.  Unfortunately there is a slight problem -- if I
> have an iterator can legitimately iterate over more values than
> ULONG_MAX, what do I make difference_type?  It has to be a signed
> iteragal type [24.1/1], so I can't use some arbitrary precission
> integer class.  Perhaps there is an argument that *this* should be
> address, perhaps by introducing a SignedInteger concept and allowing
> any type that models SignedInteger to be used as a difference_type?

Anything that blurs the line between user-defined types and built-in
types are good features to add in the standard. But what you're
suggesting doesn't work for pointers because
iterator_types<T*>::difference_type is required to be ptrdiff_t (and
hence doesn't solve my original problem of having a fast (but correct)
size_t(a-b) operation).

> > The general standard conforming way of doing this
> > requires a loop but on many implementations, subtraction and casting to
> > a size_t works. For the non-pointer case, the implementor can do
> > something fancy like determining that the positive range of
> > distance_type will fit into a size_type and doing simple subtraction.
> >
> > void increase(It &it, size_type n);
>
> Again, how does this differ from std::advance?  By having both
> arguments of std::advance use independent template paramaters, viz.,

I don't know wtf I was thinking when I wrote that. So replace what I
said with:

void retreat(It &it, Dist n);

To deal with:

char foo[SIZE_MAX];
char *e = foo + sizeof(foo);

retreat(e, sizeof(foo)) == &foo[0];

To be the -= analog of std::advance.

>   template <typename InputIterator, typename Distance>
>   void advance( InputIterator& i, Distance n );
>
> rather than
>
>   template <typename InputIterator>
>   void advance( InputIterator& i,
>                 typename std::iterator_traits<InputIterator>
>                   ::difference_type n );
>
> the argument is not (necessarily) converted to a difference_type, and
> so an implementation could correctly handle large unsigned values that
> would not convert correctly to a difference_type.  (I'm not clear
> whether an implementation is *required* to do so, though.)

The standard isn't clear about this but it's obvious the intent is to
not do a cast to difference_type (there should be a DR filed).

> If you're looking for additional functions along the lines of
> std::advance / std::distance for TR2 (it's too late for TR1 now), I
> would have thought that boost::next / boost::prior would be very strong
> candidates.  Just because they're trivial doesn't mean they're not
> worth standardising!  That's my two cents, anyway.

What's the state of TR1? Are they not accepting further functionality
or is it completely ratified?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]