David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

1. leave the return type as it is.

2. return an iterator_range describing the range [found,end) this allows us to do stuff like

namespace br = boost::ranges; br::erase( rng, br::unique(rng) );

3. inspired by John Torjo's range lib, provide a whole list of possible return values:

[snip]

2 is the answer for me.

...

the default would be the range [found,end), but the you can pick different slices or simply iterators. In the above scheme, "found" is the iterator normally returnes by the algorithm, "next" means boost::next(found) and "prior" means boost::prior(found).

And that works for ranges without bidirectional iterators, e.g. slist?

"prior" can of course not work with bidirectional iterators.

...

The advantage of the latter approach is

- flexibility/power - safety (we can tjeck that next(found) and prior(found) stays in range)

The disadvantage is that it will require twice as many overloads in C++03 (since we can't put defaults template arguments in function templates).

And it's complex.

implementation wise or interface wise?

I'm wary of introducing any such complexity without a strong catalog of use cases.

basically it makes splitting of ranges way easier and safer. assume I want to find the first occurence of 5 and then copy the range [begin,found] (that is, [begin,next(found)) ) somewhere: std::vector<int> v = ...; std::vector<int>::iterator i = find( v, 5 ); if( i != v.end() ) { ++i; copy( v.begin(), i, out ); } vs copy( find<return_begin_next>( v, 5 ), out ); (*) If found == v.end(), the returned ranges are empty and so you completely avoid forgetting about checking for the end iterator. Having only (2) we can still, however, do a little better than above: copy( find( c, 5 ).advance_end(1), out ) but now we can't be sure we don't iterator past the end. Thus we would be forced to create a temporary. -Thorsten (*) without much extra work, I could probably get a generalized version like xx_next<N> xx_prior<N> to work.

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

In that case, this should *not* be integrated with the algorithms, but should instead be provided (if it's needed) as a separate layer that can adjust the endpoints of a range:

drop_front(r) -> new view of r with the begin iterator incremented grow_front(r) -> new view of r with the begin iterator decremented drop_back(r) -> new view of r with the end iterator decremented grow_back(r) -> new view of r with the end iterator incremented

Okay, I see from your points below that the "grow" variants can be dangerous.

Well, all versions can be dangerous: just remember that r can be empty. More importantly, to make them safe, you need to supply the original range as a second input. This implies that you need to store a temporary --- this what we are actually trying to avoid. At least for me this *proves* that we can't extract the adjustsments of the return value from the algorithm itself. I agree it would have been nice if we could.

...

...

...

The advantage of the latter approach is

- flexibility/power - safety (we can tjeck that next(found) and prior(found) stays in range)

The disadvantage is that it will require twice as many overloads in C++03 (since we can't put defaults template arguments in function templates).

And it's complex.

implementation wise or interface wise?

Yes. And documentation-wise. And comprehension-wise.

well, implementation wise it consist of 9 partial specializations and twice as many function overloads (remark: in C++0x 4 functions reduce to one function) documentation-wise you don't have to explain the mechanism for every function, just show an interface that supports it. comprehension-wise, well, all new things take time.

...

...

I'm wary of introducing any such complexity without a strong catalog of use cases.

basically it makes splitting of ranges way easier and safer.

assume I want to find the first occurence of 5 and then copy the range [begin,found] (that is, [begin,next(found)) ) somewhere:

std::vector<int> v = ...; std::vector<int>::iterator i = find( v, 5 ); if( i != v.end() ) { ++i; copy( v.begin(), i, out ); }

vs

copy( find<return_begin_next>( v, 5 ), out ); (*)

copy( drop_front( find( v, 5 ) ), out );

it's even shorter.

and it will lead to undefined behavior of the range was empty.

...

If found == v.end(), the returned ranges are empty and so you completely avoid forgetting about checking for the end iterator.

Having only (2) we can still, however, do a little better than above:

copy( find( c, 5 ).advance_end(1), out )

but now we can't be sure we don't iterator past the end.

Okay, that's a different case. Why would you ever want to advance the *end* of a find? It's really beside the point, though.

Feh.

right, stupid example.

If this is an important case (still not convinced),

generally it is hard to say what is important to all people. I do think, however, that splitting a range into different sub-ranges is a fairly common activity. Some ranges are more common: [begin,found) [found,end) for example, take unique: erase( rng, unique(rng) ); // unique should return[found,end) copy( unique<return_begin_found>(rng), out ); but I'm sure that sometimes you want to include the found value in the

I would consider generalizing find with this overload:

find( -1, v, 5 )

That is, "find the element before the one that's equal to 5". And I would *certainly* make it work for forward ranges with somewhat reduced efficiency.

I'm not that keen on providing to many new algoriths. The return-value mechanism is a more like a layer on top of the algorithm, not a new algorithm.

That's consistent with the spirit of generic programming.

well, as soon as we have to implement different algorithms for different iterator categories, some of the benefits and beauty goes away IMO.

I don't think it's necessary to have the policy be a compile-time thing. But if it were, I'd still pass it by by value.

it is necessary if you want the algorithm to be able to return either an iterator or a range. if only ranges are supported, using a parameter seems like the thing to do. the iterator version may of course be emjulated easily by calling foo<return_begin_found>(rng).end() etc.

Anyway, how do you check for success? What if 5 is the first element? Do you get an empty range or do you just get v back?

you get an empty range back if nothing is found: if( find( v, 6 ) ) { ... }

...

Thus we would be forced to create a temporary.

yes, but only if you're not passing the range directly to another algorithm. -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

...

In that case, this should *not* be integrated with the algorithms, but should instead be provided (if it's needed) as a separate layer that can adjust the endpoints of a range:

drop_front(r) -> new view of r with the begin iterator incremented grow_front(r) -> new view of r with the begin iterator decremented drop_back(r) -> new view of r with the end iterator decremented grow_back(r) -> new view of r with the end iterator incremented

Okay, I see from your points below that the "grow" variants can be dangerous.

Well, all versions can be dangerous: just remember that r can be empty.

No, the "drop" versions are always safe because you can avoid shrinking past empty.

right, my mistake. Now consider having the range [found,end) being returned. How do you supply the functionality given by the return_begin_found flag?

...

More importantly, to make them safe, you need to supply the original range as a second input. This implies that you need to store a temporary --- this what we are actually trying to avoid.

No, that only applies to the "grow" versions.

right.

...

...

If this is an important case (still not convinced),

generally it is hard to say what is important to all people. I do think, however, that splitting a range into different sub-ranges is a fairly common activity. Some ranges are more common:

[begin,found) [found,end)

For that drop_front works great.

how do you construct the range [begin,found) if the algorithm returns ther range [found,end) ?

...

for example, take unique:

erase( rng, unique(rng) ); // unique should return[found,end) copy( unique<return_begin_found>(rng), out );

but I'm sure that sometimes you want to include the found value in the

...

I would consider generalizing find with this overload:

find( -1, v, 5 )

That is, "find the element before the one that's equal to 5". And I would *certainly* make it work for forward ranges with somewhat reduced efficiency.

I'm not that keen on providing to many new algoriths.

What do you think this thing called "find" with the explicit template parameter is, if not a new algorithm?!

It's a utility wrapper of an existing std algorihtm.

...

The return-value mechanism is a more like a layer on top of the algorithm, not a new algorithm.

How is that distinct from the much simpler find illustrated above? Are you saying that the use of the explicit template argument is what makes it "not a new algorithm?"

You'l need to implement a new version of find so that it works for forward iterators, you don't just forward to an existing.

...

...

I don't think it's necessary to have the policy be a compile-time thing. But if it were, I'd still pass it by by value.

it is necessary if you want the algorithm to be able to return either an iterator or a range.

I don't want that, but please explain.

For eaxmple, take unique(): template< range_return_value re, class Rng > inline BOOST_DEDUCED_TYPENAME range_return<Rng,re>::type unique( Rng& r ) { return range_return<Rng,re>::pack( std::unique(boost::begin(r), boost::end(r)), r ); } this allows the algorithm to return an iterator like the old version. It also illustrates that if we change the template parameter to a function parameter, pack() becomes a big function with a switch case.

...

if only ranges are supported, using a parameter seems like the thing

^ regular run-time function---------+ ??

right.

...

...

Anyway, how do you check for success? What if 5 is the first element? Do you get an empty range or do you just get v back?

you get an empty range back if nothing is found:

Of course you do. That wasn't my question. In the original example you were searching for 5. So what happens when you ask for the range beginning just before (or just after, for that matter) 5 in a single-element range containing just 5?

then you get an empty range. [Dave:]

Anyway, how do you check for success? What if 5 is the first element? Do you get an empty range or do you just get v back?

...

if( find( v, 6 ) ) { ... }

...

...

Thus we would be forced to create a temporary.

yes, but only if you're not passing the range directly to another algorithm.

Now you're arguing with yourself. I'm happy to sit back and see who wins this one.

You asked how you check for success. My reply was the if-statement above. If you ask for a range [begin,found) when you search for 5, and 5 is the fist element, then of course you get back an empty range. -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

...

For that drop_front works great.

how do you construct the range [begin,found) if the algorithm returns ther range [found,end) ?

Maybe you just write an algorithm for that?

There are lots of ways to approach this. Maybe you want an uber-find that returns a quadruple of iterators from which you can choose:

uber_find( x, 5 ).range(0,2);

or

uber_find( x, 5 ).range(_0,_2);

that is, it grabs the 0th (beginning) and 2nd (after-found-element) iterators from the result.

That can just be a member function in iterator_range<T>, eg slice(size_type,size_type). Anyway, if the convention of range-based algorithms should be "always return [found,end)", it raises the question why we think this range is more imoprtant than [begin,found) (and some of the others). The natural answer is of course: it is not more important or more fundamental. Therefore it is natural to investigates means to return the slices you need. We have already seen that seperate slice functions cannot be always be safe unless they require the use of a temporary, thus defeating the much purpose of ranges.

...

...

...

...

I don't think it's necessary to have the policy be a compile-time thing. But if it were, I'd still pass it by by value.

it is necessary if you want the algorithm to be able to return either an iterator or a range.

I don't want that, but please explain.

For eaxmple, take unique():

template< range_return_value re, class Rng > inline BOOST_DEDUCED_TYPENAME range_return<Rng,re>::type unique( Rng& r ) { return range_return<Rng,re>::pack( std::unique(boost::begin(r), boost::end(r)), r ); }

this allows the algorithm to return an iterator like the old version.

How is that choice made?

at the call site: unique<return_found>( rng ); range_return_value is just an enumeration used to implement partical specializations of range_return<T,range_return_value>.

...

It also illustrates that if we change the template parameter to a function parameter, pack() becomes a big function with a switch case.

I don't see it. It looks like my function is a new overload of find.

well, you have to decide which range to construct based on the indexes passed to the algorihtm.

...

...

Of course you do. That wasn't my question. In the original example you were searching for 5. So what happens when you ask for the range beginning just before (or just after, for that matter) 5 in a single-element range containing just 5?

then you get an empty range.

Even when you're asking for the range from found-1 to end? In that case, there is no "found-1" position, right?

I'm have settled on anything certain here, I'm just giving the samentics I find most natural. The basic principle should be that the range is always open at the end. Let's recab: // rng = {5} find<return_begin_found>( rng, 5 ) returns an empty range find<return_begin_prior>( rng, 5 ) returns an empty range find<return_begin_next>( rng, 5 ) returns a range with one element find<return_found_end>( rng, 5 ) returns a range with one element find<return_prior_end>( rng, 5 ) returns a range with one element find<return_next_end>( rng, 5 ) returns an empty range thus we only increment or decrement if we does not exceed the bounds of the range.

...

[Dave:]

...

Anyway, how do you check for success? What if 5 is the first element? Do you get an empty range or do you just get v back?

...

...

if( find( v, 6 ) ) { ... }

...

...

Thus we would be forced to create a temporary.

yes, but only if you're not passing the range directly to another algorithm.

Now you're arguing with yourself. I'm happy to sit back and see who wins this one.

You asked how you check for success. My reply was the if-statement above.

Huh? The result of find is now convertible to bool?

yes, iterator_range<T> defines operator unspecified_bool().

...

If you ask for a range [begin,found) when you search for 5, and 5 is the fist element, then of course you get back an empty range.

Yes, but suppose you ask for [found-1,end)?

correponds to the case return_prior_end above: a range with one element. -Thorsten

Thorsten Ottosen <tottosen@dezide.com> writes:

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

...

...

...

For that drop_front works great.

how do you construct the range [begin,found) if the algorithm returns ther range [found,end) ?

Maybe you just write an algorithm for that?

There are lots of ways to approach this. Maybe you want an uber-find that returns a quadruple of iterators from which you can choose: ^^^^^^^^^^^^^^^^^^^^^^^^

uber_find( x, 5 ).range(0,2);

or

uber_find( x, 5 ).range(_0,_2);

that is, it grabs the 0th (beginning) and 2nd (after-found-element) iterators from the result.

That can just be a member function in iterator_range<T>, eg slice(size_type,size_type).

No, that's not the same thing at all. Read what I wrote again.

Anyway, if the convention of range-based algorithms should be "always return [found,end)", it raises the question why we think this range is more imoprtant than [begin,found) (and some of the others).

The natural answer is of course: it is not more important or more fundamental.

Therefore it is natural to investigates means to return the slices you need. We have already seen that seperate slice functions cannot be always be safe unless they require the use of a temporary, thus defeating the much purpose of ranges.

I'm sure you must mean a named intermediate value, not a temporary.

...

...

It also illustrates that if we change the template parameter to a function parameter, pack() becomes a big function with a switch case.

I don't see it. It looks like my function is a new overload of find.

well, you have to decide which range to construct based on the indexes passed to the algorihtm.

Sounds easy enough to do without a switch. And anyway, who cares about such a tiny implementation detail? -- Dave Abrahams Boost Consulting www.boost-consulting.com

Thorsten Ottosen <tottosen@dezide.com> writes:

...

No, that's not the same thing at all. Read what I wrote again.

ok, so we could return a tripple {begin,found,end}.

I said quadruple. I meant {begin,found,found+1,end}.

this means that

1. we loose the benefit of a default

The default might be a different function. In fact it would be in your case, too, since you can't deduce an explicit template argument from a default value.

2. a slight overhead (the tripple construction cannot be optmized away)

How do you know? The compiler can optimize anything it wants as long as it doesn't change the observable behavior.

3. at least as complicated an implementation

Maybe.

I couldn't find the definition of "temporary" in the standard; is it defined and inherted from C?

It's not explicitly defined anywhere. The standard describes situations in which a "temporary object" or "temporary" is created and then has special rules for what can be done with such an object.

...

Sounds easy enough to do without a switch. And anyway, who cares about such a tiny implementation detail?

nobody unless it affects the generated code size/speed.

Right. -- Dave Abrahams Boost Consulting www.boost-consulting.com

David Abrahams writes:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

...

...

...

If this is an important case (still not convinced),

generally it is hard to say what is important to all people. I do think, however, that splitting a range into different sub-ranges is a fairly common activity. Some ranges are more common:

[begin,found) [found,end)

For that drop_front works great.

how do you construct the range [begin,found) if the algorithm returns ther range [found,end) ?

Maybe you just write an algorithm for that?

FWIW, that's what we did here at Meta; our "plain" sequence version of 'find' returns an iterator (like 'std::find'), while 'find_head' and 'find_tail' return the corresponding ranges. -- Aleksey Gurtovoy MetaCommunications Engineering

Eric Niebler wrote:

Thorsten Ottosen wrote:

...

Dear all,

The plan is to include range-based overloads of std algorithms in the next boost.range.

Range algorithms are more complicated than they look. I think it would be a mistake to bang this out and sneak it in without a full review.

ok, I was hoping for a mani-review, but I don't mind a full review.

...

We have several options for specifying the return type of functions that normally return an iterator that I would like your feedback on.

This is, of course, just one of the questions range-based algorithms raise, and probably the least controversial.

the others would be a. calling members b ?

...

1. leave the return type as it is.

Not a good idea. Range algorithms should consume *and* produce ranges. This is so that multiple range algorithms can be composed/chained together, a-la the functional style of programming.

right, but do you also waht sort() to return the sorted range?

...

2. return an iterator_range describing the range [found,end) this allows us to do stuff like

namespace br = boost::ranges; br::erase( rng, br::unique(rng) );

Yes, this one, please.

But there is no "erase" algorithm. Do you mean something like:

vect.erase(br::unique(vect).begin());

? This actually argues *against* returning a range, at least until the appropriate members are added to the std containers to accept ranges as arguments. Or are you suggesting adding such an erase() algorithm as a stop-gap until the std is changed:

template<typename Rng1, typename Rng2> void erase(Rng1 & rng1, Rng2 const & rng2) { rng1.erase(rng2.begin(), rng2.end()); }

? This is probably necessary, in fact.

yes, and ditto for push_back, push_front and insert.

...

3. inspired by John Torjo's range lib, provide a whole list of possible return values:

std::vector<int> v; namespace br = boost::ranges; br::unique(v); br::unique<br::return_found>(v); br::unique<br::return_next>(v); br::unique<br::return_prior>(v); br::unique<br::return_begin_found>(v); br::unique<br::return_begin_next>(v); br::unique<br::return_begin_prior>(v); br::unique<br::return_found_end>(v); br::unique<br::return_next_end>(v); br::unique<br::return_prior_end>(v);

Yuk! I'd need to see justification.

well, you may comment on the thread with Dave.

There are lots more issues with range algorithms that have not been discussed yet. What about algorithms that accept an output iterator and write into it? Will they now take an output range?

My say would be no. We still have the concept of an unbounded iterator. The unsafe usage of copy should be done with a new function called overwrite(rng1,rng2) which can tjeck the bounds with an assert.

? Is it undefined behavior? Or is this range-checked? And if so, do we truncate, assert or throw? Is there a way to make range-checking optional? Can we specify the failure mode? And what should the default be?

Using an exception seems not to in the spirit of STL.

And what does br::copy return? You might think the answer is easy: the range designating the unused elements at the end of the second range. But what if br::copy is range-checked and truncates? That return value is no longer sufficient -- if br::copy returns an empty range, did the algorithm truncate, or did it all just fit?

I'd be quite happy with copy returning void. -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

Eric Niebler wrote:

...

right, but do you also waht sort() to return the sorted range?

Yes, but as a "reference" to the original, i.e. a boost::range iterator bundle.

I assume you mean iterator_range< range_iterator<Rng>::type > or something similar.

...

...

There are lots more issues with range algorithms that have not been discussed yet. What about algorithms that accept an output iterator and write into it? Will they now take an output range?

My say would be no. We still have the concept of an unbounded iterator.

There is also the issue of O(1) size, for which you have not got support in your concept hierarchy.

Did I forget to mention this? Anyway, size() is now O(1). If you want a generic version, dictance(rng) is supplied instead.

And then there's property maps.

How do they relate to this?

...

...

And what does br::copy return? You might think the answer is easy: the range designating the unused elements at the end of the second range. But what if br::copy is range-checked and truncates? That return value is no longer sufficient -- if br::copy returns an empty range, did the algorithm truncate, or did it all just fit?

I'd be quite happy with copy returning void.

I think that's a mistake.

What do you want it to return then? -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

...

There is also the issue of O(1) size, for which you have not got support in your concept hierarchy.

Did I forget to mention this? Anyway, size() is now O(1). If you want a generic version, dictance(rng) is supplied instead.

That's not what I mean. Is there a way to distinguish, at compile-time, a range that has support for O(1) size from one that does not? One needs that for important "benefit and beauty"-destroying optimzations that you dislike so.

ok, if range_category<R>::type is convertible to std::random_access_iterator_tag, then you may call boost::size(rng)

...

...

And then there's property maps.

How do they relate to this?

They're an important part of a generalized range concept.

perhaps, but its hard for me to see how and why they are it. how do you imagine that property maps would affect the interface of range-based algorithms? isn't range concepts orthogonal to PMs? -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

...

...

...

There is also the issue of O(1) size, for which you have not got support in your concept hierarchy.

Did I forget to mention this? Anyway, size() is now O(1). If you want a generic version, dictance(rng) is supplied instead.

That's not what I mean. Is there a way to distinguish, at compile-time, a range that has support for O(1) size from one that does not? One needs that for important "benefit and beauty"-destroying optimzations that you dislike so.

ok, if range_category<R>::type is convertible to std::random_access_iterator_tag, then you may call boost::size(rng)

There are non-random-access ranges/containers that have O(1) size.

That is true that eg. std::list<T>::size() might be O(1). But how do you detect that? (A: you can't). IIRC, you where one of the people who were very conserned about the performance discontinuity induced by boost::size() is its original form. I now totally agree that such discontinuities are more harmful than useful. Anyway, what issue are you really talking about. I must be missing something.

...

...

...

...

And then there's property maps.

How do they relate to this?

They're an important part of a generalized range concept.

perhaps, but its hard for me to see how and why they are it. how do you imagine that property maps would affect the interface of range-based algorithms?

isn't range concepts orthogonal to PMs?

No, a more general range concept is a property map and two cursors, rather than just two iterators.

Ok, but it still appears to me that you basically replace iterators with cursors. Boost.range is merely a utility layer on top of a more generic fabric. It shouldn't matter what lies underneith. For example, if I write boost::unique( rng ) I don't care about if it is cursors or iterators doing the hard work. Unlike some, I fully support your and Dietmars efforts to develop the cursor/pm abstraction. But I don't see how it is relevant to boost.range right now. -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

That is true that eg. std::list<T>::size() might be O(1).

But how do you detect that? (A: you can't).

Sure you can; you just look at your implementation and if it is O(1) you write a specialization of the metafunction (or whatever).

Well, I don't personally have access to all the implementations. This seems like overkill.

...

Anyway, what issue are you really talking about. I must be missing something.

If there's an O(1) size available you can do loop unrolling; otherwise you have to test the iterators every time through the loop.

You mean Duff's device? Do we have tests on all our platforms that suggests that Duffing leads to faster code? I was told that Duffing could actually hurt a modern optimizer.

...

Boost.range is merely a utility layer on top of a more generic fabric. It shouldn't matter what lies underneith. For example, if I write

boost::unique( rng )

I don't care about if it is cursors or iterators doing the hard work.

Unlike some, I fully support your and Dietmars efforts to develop the cursor/pm abstraction. But I don't see how it is relevant to boost.range right now.

Look at the big picture. A generalized algorithm suite will be written in terms of property maps and cursors, not in terms of iterators.

And how does it affect the return type of range_based algorithms other than replacing iterator_range with cursor_range? I still don't see the relevance until we have an established cursor/pm library. -Thorsten

David Abrahams wrote:

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

Thorsten Ottosen <tottosen@dezide.com> writes:

...

David Abrahams wrote:

...

...

Sure you can; you just look at your implementation and if it is O(1) you write a specialization of the metafunction (or whatever).

Well, I don't personally have access to all the implementations. This seems like overkill.

std::list is not the only sequence out there that might have O(1) size and no random access iterators! Consider slist, hash_set, ...

right, so what do you propose exactly?

...

I was told that Duffing could actually hurt a modern optimizer.

Loop unrolling helps unconditionally in this sort of case because you eliminate comparisons and branches.

how much does it help and on which datastructures and for which types in the container? -Thorsten