Re: [boost] Re: iterator ranges; eliminating private member functions

From: brangdon_at_[hidden]
Date: 2001-12-16 12:22:13

In-Reply-To: <E16BZhB-0008Vc-00_at_[hidden]>
On Wed, 5 Dec 2001 13:54:33 +0300 Vladimir Prus (ghost_at_[hidden]) wrote:
> If it needs to create range with Sequence interface, it should do so 
> explicitly:

Terminology is letting us down. I think what you call "range" is what I 
call "sequence". What you call "sequence" is what I call "container". I am 
taking my terminology partly from references like Stroustrup's C++PL, 
$18.3.

I'll avoid "sequence" for the rest of this message, using "range" or 
"container" instead.

> It depends... actually my original proposal 
> (http://groups.yahoo.com/group/boost/message/15179)
> was to make algorithms work on containers.

OK... my view is that we need algorithms which work on ranges. No, scratch 
that - we already have algorithms which work on ranges. It was part of the 
STL's original insight that such algorithms are more general than working 
directly with containers. The problem is that the current STD represents 
these ranges in a low-level and cumbersome way.

I believe that if we have a direct, high-level and less cumbersome data 
structure for representing a range, the need for algorithms which work on 
containers will be greatly diminished.

I also believe that containers and ranges are very different things, and 
therefore conversions from one to the other should be explicit. It should 
not be possible to accidentally pass a container to an algorithm which 
expects a range, or vice versa.

> >  - Problems with algorithms that need to return sequences as results.
> >    For example, std::equal_range(), my fat_partition().
> 
> This is not directly related. It is good if such algortihm return 
> something more usable than std::pair, but I see no connection to the 
> way of passing containers/sequences to algorithms.

A basic problem with representing a ranges as two iterators is that C++ 
functions can only return one object. This is something any new proposal 
should fix.

The connection is that the argument to one function often needs to be the 
result of another. Algorithms which accept ranges ought to work seamlessly 
with algorithms which return ranges.

> >  - Problems with algorithms that want to construct new sequences, or
> >    copy existing ones, internally, such as my fat_qsort().
> 
> Do you imply possible inefficiencies?

The issue is semantics. Some algorithms need to construct new ranges 
without copying their elements. For example, fat_qsort() needs to work on 
its data in-place. It wants to sort the original data, not a copy of the 
data.

I think this is fairly uncontroversal as long as we use the word "range" 
rather than "sequence".

> >  - Inelegance of algorithms having to use iterators in addition to
> >    sequences if they want to do anything more than pass the sequence
> >    on.
> 
> Not sure I get you. What is wrong with using iterators to denote 
> elements in sequence.

It is OK to use iterators to denote individual elements. What bothers me 
is resorting to manual iterator pairs to denote ranges. An iterator pair 
is denoting a covert range whenever we write code like "first != last" 
instead of "!range.empty()". It is wrong because it drops down a level of 
abstraction. Problems show up as code which is less clear, less efficient 
and less general.

I have gone over all this before. I don't mind a brief re-statement of my 
position, but I don't see much point in endlessly repeating the same 
arguments.

> Does your observation still hold for case of special kind of container 
> returned? 

It depends on how special. I notice that VTL has a "referenced_ownership" 
tag. Presumably copying a view with that tag does not copy the underlying 
elements. In which case it is very much like what I am calling a range. 
However, I can't help feeling that this is a bit of a hack caused by 
trying to force the range concept into container packaging.

> Algorithm taking Sequence should not assume it can be copied in O(1).

To me this is just a re-statement of the design choice, not an argument.

Dave Harris