[range] Proposal: addition of front(), back(), at(), operator[]

newer
Creating a new(-ish) library in...

older
Re: [boost] [Parallel Algorithms]...

Adam Wulkiewicz

23 Mar 2014 23 Mar '14

7:59 p.m.

Hi, I propose to add the functions described below to the Boost.Range. I found the use of those very convenient WRT the corresponding use of begin() and end(), and a lot more readable. 1. front() returning the reference to the first element precondition (assert): !empty(rng) return *begin(rng); 2. back() returning the reference to the last element precondition (assert): !empty(rng) For BidirectionalRange return *(--end(rng)); For SinglePassRange it could iterate over the range and return the reference to the last element 3. at() returning the reference to the i-th element of the range precondition (throw std::out_of_range or assert): index < size(rng) For RandomAccessRange return *(begin(rng) + index); For SinglePassRange it could iterate over the range and return the required element For me, non-throwing at() would be more useful however this behavior won't be intuitive. So the following should also be provided: 4. sub(), subscript(), el(), element(), at_index(), at_(), index(), indexed(), access(), operator[], ...? the implementation of indexing operator[] same as 3 but instead of throwing an assert would be used The use of operator[] could be similar to this: { using boost::range::subscript_operator; rng[index]; } So not very convenient. But maybe you have a better idea? Regards, Adam

Show replies by date

Neil Groves

23 Mar 23 Mar

8:32 p.m.

iterator_range already has front() and back() functions. These are not part of the Range Concept since we want to be able to model them non-intrusively. The iterator_range and sub_range classes can be used to wrap other iterator pairs or ranges and provide most of the member functions that you are suggesting.

...

3. at() returning the reference to the i-th element of the range precondition (throw std::out_of_range or assert): index < size(rng)

For RandomAccessRange return *(begin(rng) + index);

operator[] is implemented. An at(index) function can be written that throws upon out-of-range. I have not provided one.

...

For SinglePassRange it could iterate over the range and return the required element

For me, non-throwing at() would be more useful however this behavior won't be intuitive. So the following should also be provided:

4. sub(), subscript(), el(), element(), at_index(), at_(), index(), indexed(), access(), operator[], ...? the implementation of indexing operator[] same as 3 but instead of throwing an assert would be used

The use of operator[] could be similar to this:

Already exists for iterator_range.

...

{ using boost::range::subscript_operator; rng[index]; }

So not very convenient. But maybe you have a better idea?

Perhaps this is useful: http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/uti... I believe that everything you have asked for is already present except a throwing at() function which might be a nice addition.

...

Regards, Adam

Regards, Neil Groves

Adam Wulkiewicz

9:33 p.m.

New subject: [range] Proposal: addition of front(), back(), at(), operator[]

Hi, Neil Groves wrote:

...

iterator_range already has front() and back() functions. These are not part of the Range Concept since we want to be able to model them non-intrusively. The iterator_range and sub_range classes can be used to wrap other iterator pairs or ranges and provide most of the member functions that you are suggesting.

Thanks for the tip. However I rather see those functions as algorithms, not a part of the Concept. They musn't be modeled intrusively, just like any other Boost.Range algorithm. So in the case of iterator_range the use case would look like this: boost::make_iterator_range(range).front(); boost::make_iterator_range(range).back(); boost::make_iterator_range(range)[index]; I'd say it's less intuitive/readable/convenient than: boost::front(range); boost::back(range); boost::at(range); And the readability is what I wanted to achieve but ok, the functionality is there. And this way the implementation of operator[] is straightforward. Still, I prefer my way :) Regards, Adam

Adam Wulkiewicz

10:31 p.m.

New subject: [range] Proposal: addition of front(), back(), at(), operator[]

Adam Wulkiewicz wrote:

...

Hi,

Neil Groves wrote:

...
iterator_range already has front() and back() functions. These are not part of the Range Concept since we want to be able to model them non-intrusively. The iterator_range and sub_range classes can be used to wrap other iterator pairs or ranges and provide most of the member functions that you are suggesting.

Thanks for the tip. However I rather see those functions as algorithms, not a part of the Concept. They musn't be modeled intrusively, just like any other Boost.Range algorithm.

So in the case of iterator_range the use case would look like this:

boost::make_iterator_range(range).front(); boost::make_iterator_range(range).back(); boost::make_iterator_range(range)[index];

I'd say it's less intuitive/readable/convenient than:

boost::front(range); boost::back(range); boost::at(range); Of course this should be:

boost::at(range, index);

...

And the readability is what I wanted to achieve but ok, the functionality is there. And this way the implementation of operator[] is straightforward. Still, I prefer my way :)

Regards, Adam

Neil Groves

24 Mar 24 Mar

1:21 a.m.

...

So in the case of iterator_range the use case would look like this:

boost::make_iterator_range(range).front(); boost::make_iterator_range(range).back(); boost::make_iterator_range(range)[index];

I'd say it's less intuitive/readable/convenient than:

boost::front(range); boost::back(range); boost::at(range);

And the readability is what I wanted to achieve but ok, the functionality is there. And this way the implementation of operator[] is straightforward. Still, I prefer my way :)

Yes, I agree with your comment. I wanted to demonstrate that the functionality existed in currently released versions. I have been planning to add support for non-member front and back functions in addition to drop_front and drop_back functions. With these and a few other additions we will be able to model range primitives while interoperating with existing iterator-based ranges. I was hoping to get my trac tickets in good shape so that 1.56 is nice and stable before adding these new features for 1.57.

...

Regards, Adam

Regards, Neil Groves

Marshall Clow

23 Mar 23 Mar

9:43 p.m.

On Mar 23, 2014, at 12:59 PM, Adam Wulkiewicz wrote:

...

For SinglePassRange it could iterate over the range and return the reference to the last element

I am not in favor of things that are sometimes silently expensive. I would much rather this call failed for SinglePassRanges, and if I wanted that, I could write it myself. — Marshall

Krzysztof Czainski

10:15 p.m.

2014-03-23 20:59 GMT+01:00 Adam Wulkiewicz :

...

Hi,

Hello,

...

I propose to add the functions described below to the Boost.Range. I found the use of those very convenient WRT the corresponding use of begin() and end(), and a lot more readable.

1. front() returning the reference to the first element precondition (assert): !empty(rng)

return *begin(rng);

Usage: front(rng) +1

...

2. back() returning the reference to the last element precondition (assert): !empty(rng)

For BidirectionalRange return *(--end(rng));

...

For SinglePassRange it could iterate over the range and return the reference to the last element

-1 for silent O(n), when O(1) is expected for other ranges. 3. at()

...

returning the reference to the i-th element of the range precondition (throw std::out_of_range or assert): index < size(rng)

-1 for throwing on logic errors; I think "container::at()" is a mistake in the Standard Library. For RandomAccessRange

...

return *(begin(rng) + index);

For SinglePassRange it could iterate over the range and return the required element

-1 for silent O(n), when O(1) is expected for other ranges. For me, non-throwing at() would be more useful however this behavior won't

...

be intuitive. So the following should also be provided:

4. sub(), subscript(), el(), element(), at_index(), at_(), index(), indexed(), access(), operator[], ...?

+1 for subscript(rng,n). -1; for operator[], I'd definitely prefer a named function call. The name 'at' would be a perfect name, if it only didn't have the throwing behavior in the Standard Library. the implementation of indexing operator[]

...

same as 3 but instead of throwing an assert would be used

...

The use of operator[] could be similar to this:

{ using boost::range::subscript_operator; rng[index]; }

So not very convenient. But maybe you have a better idea?

Just a named function call is fine for me.

...

Regards, Adam

Thanks for some interesting ideas, Adam

Regards, Kris

Adam Wulkiewicz

25 Mar 25 Mar

4:22 p.m.

New subject: [range] Proposal: addition of front(), back(), at(), operator[]

Hi, Krzysztof Czainski wrote:

...

2014-03-23 20:59 GMT+01:00 Adam Wulkiewicz :

...
be intuitive. So the following should also be provided:

4. sub(), subscript(), el(), element(), at_index(), at_(), index(), indexed(), access(), operator[], ...? +1 for subscript(rng,n). -1; for operator[], I'd definitely prefer a named function call. The name 'at' would be a perfect name, if it only didn't have the throwing behavior in the Standard Library.

I'd add on(rng, i) in(rng, i) the last might also be related to the word 'index'. Regards, Adam

Valentin Ziegler

24 Mar 24 Mar

9:14 a.m.

Hi Adam,

...

1. front() returning the reference to the first element precondition (assert): !empty(rng)

...

return *begin(rng);

...

2. back() returning the reference to the last element precondition (assert): !empty(rng)

...

For BidirectionalRange return *(--end(rng));

In 99% of all cases above implementations will work just fine. However, there may be rare cases where the lifetime of the reference is bound to the lifetime of the iterator: [iterator.requirements.general] 9. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator. Valentin -- Valentin Ziegler | vziegler@think-cell.com Senior Software Engineer We are looking for C++ Developers: http://www.think-cell.com/career think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091 Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Sch?dl

Adam Wulkiewicz

12:38 p.m.

New subject: [range] Proposal: addition of front(), back(), at(), operator[]

Hi Valentin, Valentin Ziegler wrote:

...

Hi Adam,

...
return *begin(rng); For BidirectionalRange return *(--end(rng)); In 99% of all cases above implementations will work just fine. However, there may be rare cases where the lifetime of the reference is bound to the lifetime of the iterator:

[iterator.requirements.general] 9. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

Thanks for pointing this one out. So yes, iterator_wrapper/reference_proxy should be returned. With members: operator casting to reference and for non-mutable Range - copy assignment and probably move assignment, probably using Boost.Move move emulation. Btw, do you know the reason for this requirement? I can imagine that some iterator could store a temporary created from data gathered during the traversal. Or when dereferenced return some wrapper/proxy with a pointer to itself or one of its members. But this doesn't convince me. It should be a case when some external data or block of memory could "dissapear" after the destruction. So there could be a container e.g. loading data to the memory on the fly or some external memory mapped somehow. In this case the Iterator would behave like a shared_ptr<> since we'd be forced to track all Iterators pointing to the data which might "dissapear". Still it's too complicated for an Iterator. Is there some prosaic reason that I can't see? Regards, Adam

Adam Wulkiewicz

12:46 p.m.

New subject: [range][iterator] iterators desctuction and proxies (was: Re: [range] Proposal: addition of front(), back(), at(), operator[])

Adam Wulkiewicz wrote:

...

Hi Valentin,

Valentin Ziegler wrote:

...
Hi Adam,

...
return *begin(rng); For BidirectionalRange return *(--end(rng)); In 99% of all cases above implementations will work just fine. However, there may be rare cases where the lifetime of the reference is bound to the lifetime of the iterator:

[iterator.requirements.general] 9. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

Thanks for pointing this one out.

So yes, iterator_wrapper/reference_proxy should be returned. With members: operator casting to reference and for non-mutable Range - copy assignment and probably move assignment, probably using Boost.Move move emulation. a remark: of course the assignment operators should be defined for mutable ranges or non-const iterators.

Is there a reason why move assignment isn't defined in proxies implemented in Boost.Iterator?

...

Btw, do you know the reason for this requirement? I can imagine that some iterator could store a temporary created from data gathered during the traversal. Or when dereferenced return some wrapper/proxy with a pointer to itself or one of its members. But this doesn't convince me. It should be a case when some external data or block of memory could "dissapear" after the destruction. So there could be a container e.g. loading data to the memory on the fly or some external memory mapped somehow. In this case the Iterator would behave like a shared_ptr<> since we'd be forced to track all Iterators pointing to the data which might "dissapear". Still it's too complicated for an Iterator. Is there some prosaic reason that I can't see?

Regards, Adam

Valentin Ziegler

3:01 p.m.

New subject: [range] Proposal: addition of front(), back(), at(), operator[]

Hi Adam,

...

Btw, do you know the reason for this requirement? I can imagine that some iterator could store a temporary created from data gathered during the traversal. Or when dereferenced return some wrapper/proxy with a pointer to itself or one of its members. But this doesn't convince me.

I do not know of a particular reason. Guess when the ISO committee did the wording for "iterator requirements", they had to say something about the lifetime of a reference returned by an iterator. The only guarantee that can be expressed without further assumptions (e.g., the existence of a parent container) is "reference lifetime == iterator lifetime". For example, boost's counting iterator did return by reference, not sure if that has changed by now ( https://svn.boost.org/trac/boost/ticket/2640?version=0 ). One could imagine other iterators that are mere proxies to some cached computation or streaming iterators. In my opinion, all such iterators should rather return a value instead of a reference to some internal state, but the standard does not preclude it. Valentin -- Valentin Ziegler | vziegler@think-cell.com Senior Software Engineer We are looking for C++ Developers: http://www.think-cell.com/career think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091 Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Sch?dl

Marshall Clow

5:36 p.m.

On Mar 24, 2014, at 2:14 AM, Valentin Ziegler wrote:

...

Hi Adam,

...
1. front() returning the reference to the first element precondition (assert): !empty(rng)

...
return *begin(rng);

...
2. back() returning the reference to the last element precondition (assert): !empty(rng)

...
For BidirectionalRange return *(--end(rng));

In 99% of all cases above implementations will work just fine. However, there may be rare cases where the lifetime of the reference is bound to the lifetime of the iterator:

[iterator.requirements.general] 9. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

Interesting. I think that in C++14, the committee put that possibility to bed. See LWG issue 2360 http://cplusplus.github.io/LWG/lwg-defects.html#2360 I’ll open an issue that gets that cleared up. — Marshall

...

Valentin

-- Valentin Ziegler | vziegler@think-cell.com Senior Software Engineer

We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091

Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Sch?dl

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Marshall Clow

25 Mar 25 Mar

8:50 p.m.

On Mar 24, 2014, at 10:36 AM, Marshall Clow wrote:

...

On Mar 24, 2014, at 2:14 AM, Valentin Ziegler wrote:

...
Hi Adam,

...
1. front() returning the reference to the first element precondition (assert): !empty(rng)

...
return *begin(rng);

...
2. back() returning the reference to the last element precondition (assert): !empty(rng)

...
For BidirectionalRange return *(--end(rng));

In 99% of all cases above implementations will work just fine. However, there may be rare cases where the lifetime of the reference is bound to the lifetime of the iterator:

[iterator.requirements.general] 9. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

Interesting. I think that in C++14, the committee put that possibility to bed. See LWG issue 2360 http://cplusplus.github.io/LWG/lwg-defects.html#2360

I’ll open an issue that gets that cleared up.

Thinking about this some more, I think that “may” is the key there. [forward.iterators] says: • 6 If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object. which disallows “stashing iterators” for forward (or greater) iterators. So, I think that [iterator.requirements.general] 9 can only really be true for input iterators. — Marshall

Eric Niebler

26 Mar 26 Mar

4:50 p.m.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/25/2014 01:50 PM, Marshall Clow wrote:

...

On Mar 24, 2014, at 10:36 AM, Marshall Clow wrote:

...
Interesting. I think that in C++14, the committee put that possibility to bed. See LWG issue 2360 http://cplusplus.github.io/LWG/lwg-defects.html#2360

I’ll open an issue that gets that cleared up.

Thinking about this some more, I think that “may” is the key there.

[forward.iterators] says: • 6 If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

which disallows “stashing iterators” for forward (or greater) iterators.

So, I think that [iterator.requirements.general] 9 can only really be true for input iterators.

That's always been my understanding. \e -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBAgAGBQJTMwVEAAoJEAeJsEDfjLbX2UQH/3xdwzJFwq77IYIwaa20hcMY eRB3oqjc7SBDgwfA/rxrmnyjk1VZTO16zV4SsSWhBNLgN6UV6GhgECguoD6Ru6VG BWHZQqPp+o6dsxjIntMtPSipqIs+nZTQpw7SkNGqsQ2VpUqb/rlUCT22MslKqWtU j/BnmtFGZpuQ/OXsiQGeJwQPwLDAj1qo/J+TUJymJ58nU8BAL/doSVDfKKkJR3xA 02HdjXx62upeDdw35fXCkaAMvVa/uzS1En4cajTKVQkzhkZRw81TxCVmYVXG6nbL Fdb7hxRWkC8F6wbxeNuF5cRQ4upYBhD4Tnl0NkF8oIh1W2G9bSG9KTTvn/yPGFg= =ChA8 -----END PGP SIGNATURE-----

3898

Age (days ago)

3901

Last active (days ago)

List overview

Download

14 comments

6 participants

participants (6)

Adam Wulkiewicz
Eric Niebler
Krzysztof Czainski
Marshall Clow
Neil Groves
Valentin Ziegler