[boost] Re: Library proposal --- pair (and tuple) iterators

From: Anthony Williams (anthony.williamsNOSPAM_at_[hidden])
Date: 2003-09-24 03:13:54

David Abrahams <dave_at_[hidden]> writes:
> Anthony Williams <anthony.williamsNOSPAM_at_[hidden]> writes:
>> Possibly, but the new categories aren't here yet, are they? They're not
>> even in the library TR, so code written today still needs to deal with the
>> reality of the current iterator categoriess. As it stands, the zip iterator
>> can't even claim to be a forward iterator if it doesn't return a reference
>> from *it, which makes it useless with a very large category of algorithms,
>> even though it might otherwise meet all the requirements of a random access
>> iterator.
>
> Not really useless.  Very few algorithms depend on actually addressing
> lvalues.  For most algorithm implementations, either the algorithm
> dispatches based on category and has an implementation which works on
> input iterators, or it "requires" a random access iterator and it
> doesn't bother to check the category.  It's only the algorithms which
> actually depend on addressing lvalues or which will do a static
> assertion of the category which will break.

Forward iterators can be used as input or output iterators. An iterator which
doesn't have an lvalue dereference must choose to be one or the other, which
restricts its usage considerably, especially when this is an imposed
restriction --- if you want an input or output iterator that supplies a tuple,
then I expect there are simpler ways to do it, e.g. as a transform_iterator,
and if you want a forward iterator the overhead is *required*.

I would expect that a reasonable number of library implementations assert
based on the category, and several will actually check the iterator meets the
requirements of the category it claims, especially in debug mode. Blithely
saying "no real algorithms depend on this requirement, so we can ignore it"
strikes me as just irresponsible. Surely part of the aim of boost is to write
standard compliant libraries that are therefore portable to any
fully-compliant compiler. If for particular platforms we can make assumptions
based on knowledge about the platform which enables the code to be smaller,
faster or simpler, then that's fine *for that platform*, but the general code
should be standard compliant, and claiming forward iterator-ness when you
don't return a reference from *it is non-conformant.

The following algorithms from the standard library (section 25) *require*
forward iterators and are therefore not legally usable with zip_iterator if it
doesn't meet the forward iterator requirements, irrespective of the actual
implementation details:

find_end
find_first_of
adjacent_find
search
search_n
swap_ranges
iter_swap
replace
replace_if
fill
generate
remove
remove_if
unique
rotate
rotate_copy
lower_bound
upper_bound
equal_range
binary_search
min_element
max_element

The following require bidirectional iterators

copy_backward
reverse_copy
partition
stable_partition
inplace_merge
next_permutation
prev_permutation

The following require random access iterators

random_shuffle
sort
stable_sort
partial_sort
partial_sort_copy
nth_element
push_heap
pop_heap
make_heap
sort_heap

>>
>> If you think that this is an acceptable scenario, then that's your
>> choice, and I'll pursue my submission as an alternative that works
>> with current algorithms, but is more heavyweight. Otherwise, I'm
>> happy to help enhance zip iterator to work with the current
>> categories, if you wish.
>
> I think it makes sense to have an additional template parameter to
> zip_iterator which causes it to be an lvalue iterator.

Hmmm. I'm not sure that's necessarily any use, since it requires the user to
decide, but its a step in the right direction. I would expect the parameter to
have 3 states --- input, output, forward+ (max supported by underlying
iterators). Of course, just because the iterator is labelled as input or
output in the old categories doesn't mean it can't support more of the new
categories.

If the new categories are accepted into the TR in Kona, that's a step forward,
but it won't change existing implementations or the existing requirements of
the standard library algorithms; we'll have to wait until C++0x before those
get changed, and then we'll have to wait n years before there are
implementations which use the new categories for the standard algorithms.

Anthony
-- 
Anthony Williams
Senior Software Engineer, Beran Instruments Ltd.
Remove NOSPAM when replying, for timely response.