Boost logo

Boost :

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,

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

> It depends... actually my original proposal
> (
> 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

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

> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at