[range] [general] making member functions SFINAE-friendly
Hi, I recently came across a request to make iterator_range<I>::size() SFINAE-friendly [1]. The respect in which it is not currently SFINAE-friendly is that it is only applicable to instantiations where I is a random-access iterator, but it is defined for all instantiations, and fails with a static assertion if I is not random-access. This makes it impossible to use SFINAE techniques to detect whether "r.size()" is valid where r is some iterator_range. The suggested workaround is to give iterator_range a base class, specialize this base class for random-access iterators, and only define size() in this specialization. I think this deficiency and workaround can be generalized to any template class 'C<T>' with a member function 'foo' that is only applicable for a subset of valid template arguments for 'T'. I am curious what the Boost community thinks about applying this workaround (factoring out the member function into a base class) as a general rule in such situations? Is making the member function SFINAE-friendly worth the decrease in readability? Are there other disadvantages to this workaround? Are there alternative ways of making such a function SFINAE- friendly that don't require introducing a base class? Finally, if the consensus is that such a workaround is not justified in general, is there any reason it should be justified specifically for iterator_range<I>::size()? Regards, Nate [1] https://svn.boost.org/trac/boost/ticket/8011
On Mon, Feb 18, 2013 at 9:30 AM, Nathan Ridge <zeratul976@hotmail.com> wrote:
Hi,
I recently came across a request to make iterator_range<I>::size() SFINAE-friendly [1].
The respect in which it is not currently SFINAE-friendly is that it is only applicable to instantiations where I is a random-access iterator, but it is defined for all instantiations, and fails with a static assertion if I is not random-access. This makes it impossible to use SFINAE techniques to detect whether "r.size()" is valid where r is some iterator_range.
The suggested workaround is to give iterator_range a base class, specialize this base class for random-access iterators, and only define size() in this specialization.
I think this deficiency and workaround can be generalized to any template class 'C<T>' with a member function 'foo' that is only applicable for a subset of valid template arguments for 'T'. I am curious what the Boost community thinks about applying this workaround (factoring out the member function into a base class) as a general rule in such situations? Is making the member function SFINAE-friendly worth the decrease in readability? Are there other disadvantages to this workaround?
Are there alternative ways of making such a function SFINAE- friendly that don't require introducing a base class?
Finally, if the consensus is that such a workaround is not justified in general, is there any reason it should be justified specifically for iterator_range<I>::size()?
Could you share a use case that requires to depend on size() specifically rather than the iterator category? IMHO, this approach doesn't look like worth the effort. Currently, size() is only defined for random access iterators but technically it is also valid for bidirectional and forward iterators if implemented in terms of std::distance. Yes, it will be O(N) but nonetheless still valid. If the implementation is to be extended to support these categories of iterators (why not, BTW?), the iterator range base class specializations will become equivalent and needless. As for general application of this approach, I'd say it depends. Clearly it costs some maintenance and compile times; the question is what's the outcome of it and whether it encourages to write "good" user side code. Depending on members of a third party component (in case of member functions - on the particular signature thereof) is a bad style, IMO, and should not be encouraged.
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible. If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list. If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map. However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach. Regards, Nate
On 18 February 2013 10:19, Nathan Ridge wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Yes, that perfectly sums up my use case, thanks. I'm not "Depending on members of a third party component", I'm writing a generic component and someone tried to use it with boost::iterator_range and asked me why it didn't work. The reason iterator_range::size() doesn't use std::distance is given at http://permalink.gmane.org/gmane.comp.lib.boost.devel/193055 I think it's a valid choice to only allow size() when its O(1), c.f. std::forward_list, but I think it would be even better to not even define it when it can't be used, c.f. std::forward_list.
On Mon, Feb 18, 2013 at 2:50 PM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
On 18 February 2013 10:19, Nathan Ridge wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Yes, that perfectly sums up my use case, thanks.
I'm not "Depending on members of a third party component", I'm writing a generic component and someone tried to use it with boost::iterator_range and asked me why it didn't work.
Then your generic component depends on third party component (which happened to be boost::iterator_range). When you try to introspect the third party type you should expect all sorts of difficulties, that's why I generally discourage it.
The reason iterator_range::size() doesn't use std::distance is given at http://permalink.gmane.org/gmane.comp.lib.boost.devel/193055 I think it's a valid choice to only allow size() when its O(1), c.f. std::forward_list, but I think it would be even better to not even define it when it can't be used, c.f. std::forward_list.
Well, the post doesn't give any rationale behind the choice, just that it was decided that way. Personally, I don't think that O(N) size() is invalid, however slow it may be. You do have list::size(), after all. I agree that it may seem strange that iterator_range::size() is present when it's not working but it is no less stranger that it doesn't work when it could. IMHO, the right solution in this case would be to fix iterator_range::size() to work in terms of std::distance.
On 18 February 2013 12:57, Andrey Semashev wrote:
I'm not "Depending on members of a third party component", I'm writing a generic component and someone tried to use it with boost::iterator_range and asked me why it didn't work.
Then your generic component depends on third party component (which happened to be boost::iterator_range). When you try to introspect the third party type you should expect all sorts of difficulties, that's why I generally discourage it.
I challenge you to implement something like std::allocator_traits without "introspecting" the template arguments. What I want to do is a fairly normal generic programming technique, maybe you've heard of the <type_traits> header, what do you think it's for?
The reason iterator_range::size() doesn't use std::distance is given at http://permalink.gmane.org/gmane.comp.lib.boost.devel/193055 I think it's a valid choice to only allow size() when its O(1), c.f. std::forward_list, but I think it would be even better to not even define it when it can't be used, c.f. std::forward_list.
Well, the post doesn't give any rationale behind the choice, just that it was decided that way. Personally, I don't think that O(N) size() is invalid, however slow it may be. You do have list::size(), after all.
Apparently you've missed that std::list::size() is required to be O(1) in C++11.
I agree that it may seem strange that iterator_range::size() is present when it's not working but it is no less stranger that it doesn't work when it could. IMHO, the right solution in this case would be to fix iterator_range::size() to work in terms of std::distance.
Do you also suggest that std::vector::push_front() should be defined, because it can easily be implemented in terms of v.insert(v.begin(), x) ? There is a general design principle in the STL that members functions are only defined on containers if they are more efficient than doing the same thing using the more general interfaces. So vector has push_back() but not push_front(), deque and list have both. forward_list doesn't have size() or back(). boost::iterator_range has size() but it results in a compile-time error. This is the worst of all combinations. It would be better to not define it at all, since users can always use std::distance on its iterators, which will be optimal for RA iterators anyway.
On Mon, Feb 18, 2013 at 5:17 PM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
I challenge you to implement something like std::allocator_traits without "introspecting" the template arguments. What I want to do is a fairly normal generic programming technique, maybe you've heard of the <type_traits> header, what do you think it's for?
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
Well, the post doesn't give any rationale behind the choice, just that it was decided that way. Personally, I don't think that O(N) size() is invalid, however slow it may be. You do have list::size(), after all.
Apparently you've missed that std::list::size() is required to be O(1) in C++11.
Hmm, you're right, I've missed it.
I agree that it may seem strange that iterator_range::size() is present when it's not working but it is no less stranger that it doesn't work when it could. IMHO, the right solution in this case would be to fix iterator_range::size() to work in terms of std::distance.
Do you also suggest that std::vector::push_front() should be defined, because it can easily be implemented in terms of v.insert(v.begin(), x) ?
I don't.
There is a general design principle in the STL that members functions are only defined on containers if they are more efficient than doing the same thing using the more general interfaces. So vector has push_back() but not push_front(), deque and list have both. forward_list doesn't have size() or back().
vector::size() doesn't provide any benefits compared to std::distance. Should it be removed as well? Is empty() also excessive because the same can be achieved by begin() == end()? I understand your point regarding other container operations but acquiring the size of a range is a fairly typical operation and not having it for some iterator types is rather limiting. It's a matter of a common interface for all ranges and convenience. Having to dispatch between std::distance and T::size() in the user's code is not an upside of the iterator_range interface.
boost::iterator_range has size() but it results in a compile-time error. This is the worst of all combinations. It would be better to not define it at all, since users can always use std::distance on its iterators, which will be optimal for RA iterators anyway.
Again, it's a matter of convenience. Compare: r.size(); and std::distance(r.begin(), r.end()); Of course, the convenience is ruined in generic code if you have to dispatch between the two variants depending on the iterator type. My point is to always use the first one and be happy.
On 18 February 2013 14:33, Andrey Semashev wrote:
On Mon, Feb 18, 2013 at 5:17 PM, Jonathan Wakely wrote:
I challenge you to implement something like std::allocator_traits without "introspecting" the template arguments. What I want to do is a fairly normal generic programming technique, maybe you've heard of the <type_traits> header, what do you think it's for?
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
It's only fragile because iterator_range defines a member which can't be used. C++ provides all the tools needed to conditionally define iterator_range::size(), instead of just documenting when it can and can't be used. When possible, it's more reliable to enforce policy through code than through documentation. I don't know how to write a template that checks Boost documentation. I do know how to write a template that checks for the existence of a member.
Well, the post doesn't give any rationale behind the choice, just that it was decided that way. Personally, I don't think that O(N) size() is invalid, however slow it may be. You do have list::size(), after all.
Apparently you've missed that std::list::size() is required to be O(1) in C++11.
Hmm, you're right, I've missed it.
Please think about what it takes for the committee to make such a breaking change to C++03, and whether that says the "don't define size() if it can't be done in constant time" principle is considered important or not.
I agree that it may seem strange that iterator_range::size() is present when it's not working but it is no less stranger that it doesn't work when it could. IMHO, the right solution in this case would be to fix iterator_range::size() to work in terms of std::distance.
Do you also suggest that std::vector::push_front() should be defined, because it can easily be implemented in terms of v.insert(v.begin(), x) ?
I don't.
There is a general design principle in the STL that members functions are only defined on containers if they are more efficient than doing the same thing using the more general interfaces. So vector has push_back() but not push_front(), deque and list have both. forward_list doesn't have size() or back().
vector::size() doesn't provide any benefits compared to std::distance.
The fact it exists tells you it is constant time. To know that std::distance would be constant time you have to check the iterator category. Doable, but sometimes less convenient.
Should it be removed as well? Is empty() also excessive because the same can be achieved by begin() == end()?
If I wrote a container that could not implement empty() in O(1) then I would not define empty().
I understand your point regarding other container operations but acquiring the size of a range is a fairly typical operation and not having it for some iterator types is rather limiting. It's a matter of a common interface for all ranges and convenience. Having to dispatch between std::distance and T::size() in the user's code is not an upside of the iterator_range interface.
boost::iterator_range has size() but it results in a compile-time error. This is the worst of all combinations. It would be better to not define it at all, since users can always use std::distance on its iterators, which will be optimal for RA iterators anyway.
Again, it's a matter of convenience. Compare:
r.size();
and
std::distance(r.begin(), r.end());
Of course, the convenience is ruined in generic code if you have to dispatch between the two variants depending on the iterator type. My point is to always use the first one and be happy.
Except for std::forward_list. So much for that rule.
On Monday 18 February 2013 15:05:11 Jonathan Wakely wrote:
On 18 February 2013 14:33, Andrey Semashev wrote:
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
It's only fragile because iterator_range defines a member which can't be used.
No, it broke with iterator_range. It can break with other types with different signatures and/or semantics of size().
Apparently you've missed that std::list::size() is required to be O(1) in C++11.> Hmm, you're right, I've missed it.
Please think about what it takes for the committee to make such a breaking change to C++03, and whether that says the "don't define size() if it can't be done in constant time" principle is considered important or not.
Not sure what you mean.
vector::size() doesn't provide any benefits compared to std::distance.
The fact it exists tells you it is constant time.
How so? This is true for vector as it is required by the standard but is it true for other types? And why it should be true for iterator_range in particular?
If I wrote a container that could not implement empty() in O(1) then I would not define empty().
Great. So we only implement operations if they are possible to be implemented in O(1) now?
boost::iterator_range has size() but it results in a compile-time error. This is the worst of all combinations. It would be better to not define it at all, since users can always use std::distance on its iterators, which will be optimal for RA iterators anyway.
Again, it's a matter of convenience. Compare: r.size();
and
std::distance(r.begin(), r.end());
Of course, the convenience is ruined in generic code if you have to dispatch between the two variants depending on the iterator type. My point is to always use the first one and be happy.
Except for std::forward_list. So much for that rule.
Too bad for those trying to write a generic optimized size() implementation, yes. But I was referring to iterator_range, specifically. It will support size() in all cases.
On 18 February 2013 18:30, Andrey Semashev wrote:
On Monday 18 February 2013 15:05:11 Jonathan Wakely wrote:
On 18 February 2013 14:33, Andrey Semashev wrote:
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
It's only fragile because iterator_range defines a member which can't be used.
No, it broke with iterator_range. It can break with other types with different signatures and/or semantics of size().
Given that I'm already requiring the type can be used with std::begin() and std::end(), i.e. is range-like, I'm happy to not support types that have a non-range-like size(). If your type quacks like a duck but swims like a fish it doesn't meet my requirements for a duck.
Apparently you've missed that std::list::size() is required to be O(1) in C++11.> Hmm, you're right, I've missed it.
Please think about what it takes for the committee to make such a breaking change to C++03, and whether that says the "don't define size() if it can't be done in constant time" principle is considered important or not.
Not sure what you mean.
You're arguing that size() should be provided even if it's O(n). I'm pointing out the committee disagreed so strongly they changed the standard even though that broke existing C++ implementations.
vector::size() doesn't provide any benefits compared to std::distance.
The fact it exists tells you it is constant time.
How so? This is true for vector as it is required by the standard but is it true for other types? And why it should be true for iterator_range in particular?
If I wrote a container that could not implement empty() in O(1) then I would not define empty().
Great. So we only implement operations if they are possible to be implemented in O(1) now?
You asked about empty, which as you pointed out can be tested in other ways. I wasn't talking about *all* operations, don't put words in my mouth then make silly assertions. And I said if I wrote it. You can do what you like with your own code.
boost::iterator_range has size() but it results in a compile-time error. This is the worst of all combinations. It would be better to not define it at all, since users can always use std::distance on its iterators, which will be optimal for RA iterators anyway.
Again, it's a matter of convenience. Compare: r.size();
and
std::distance(r.begin(), r.end());
Of course, the convenience is ruined in generic code if you have to dispatch between the two variants depending on the iterator type. My point is to always use the first one and be happy.
Except for std::forward_list. So much for that rule.
Too bad for those trying to write a generic optimized size() implementation, yes. But I was referring to iterator_range, specifically. It will support size() in all cases.
Great, I look forward to that change in future versions of Boost.
on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org> wrote:
On 18 February 2013 18:30, Andrey Semashev wrote:
On Monday 18 February 2013 15:05:11 Jonathan Wakely wrote:
On 18 February 2013 14:33, Andrey Semashev wrote:
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
It's only fragile because iterator_range defines a member which can't be used.
No, it broke with iterator_range. It can break with other types with different signatures and/or semantics of size().
Given that I'm already requiring the type can be used with std::begin() and std::end(), i.e. is range-like, I'm happy to not support types that have a non-range-like size(). If your type quacks like a duck but swims like a fish it doesn't meet my requirements for a duck.
This sounds like the language commonly used in the Python community about (their version of) concepts. <http://grokbase.com/t/python/python-list/02c225syvb/source-code-size-metric-python-and-modern-c#20021207htb5htssa6yj355yhcjbz4wm7y> There's no "range-like." There's a family of Range concepts: http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/concepts.html http://www.boost.org/community/generic_programming.html#concept Maybe I'm off base here, but reading the above makes it hard for me to hear the rest of what you wrote. -- Dave Abrahams
Dave Abrahams wrote:
on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org> wrote:
On 18 February 2013 18:30, Andrey Semashev wrote:
On Monday 18 February 2013 15:05:11 Jonathan Wakely wrote:
On 18 February 2013 14:33, Andrey Semashev wrote:
Yes, I'm aware of type traits. It's one thing to do tests/transforms on types and another to test for methods presence and behavior. It's doable but it is much more fragile and dangerous, as you have already discovered with iterator_range.
It's only fragile because iterator_range defines a member which can't be used.
No, it broke with iterator_range. It can break with other types with different signatures and/or semantics of size().
Given that I'm already requiring the type can be used with std::begin() and std::end(), i.e. is range-like, I'm happy to not support types that have a non-range-like size(). If your type quacks like a duck but swims like a fish it doesn't meet my requirements for a duck.
This sounds like the language commonly used in the Python community about (their version of) concepts. <http://grokbase.com/t/python/python-list/02c225syvb/source-code-size-metric-python-and-modern-c#20021207htb5htssa6yj355yhcjbz4wm7y>
There's no "range-like." There's a family of Range concepts: http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/concepts.html http://www.boost.org/community/generic_programming.html#concept
Maybe I'm off base here, but reading the above makes it hard for me to hear the rest of what you wrote.
FWIW - we had a thread a couple of months ago regarding Boost Range concepts, how they were defined and how they were implemented and what they should mean for users of Boost Range. I was dissatisfied with all three of these aspects of Boost Range but couldn't convince anyone else of my point of view. Looking that the documentation/synopsis of iterator_range<T> I see a few things of interest: a) Documentation says that it fullfills the ForwardIteratorRange concept - OK b) But then it includes the size() function - so doesn't that mean that it full fills the concept for RandomAccessRange concept? very confusing. c) shouldn't there be: template<ForwardIteratorRange> class forward_iterator_range { ... }; ... template<RandomIteratorRange> class random_access_iterator_range : public { size_type size() const; }; Boost Range concept doesn't specify size() for a ForwardIteratorRange. But I think this is another mistake since size() could be implemented (in a different way) for iterators fullfilling this concept. Wouldn't restructuring interator_range along the lines of the above resolve all the confusion here? Robert Ramey
c) shouldn't there be:
template<ForwardIteratorRange> class forward_iterator_range { ... };
...
template<RandomIteratorRange> class random_access_iterator_range : public { size_type size() const; };
...
Wouldn't restructuring interator_range along the lines of the above resolve all the confusion here?
Robert Ramey
It would solve Jonathan's problem, sure. But it would also hurt people who are trying to use iterator_range to package a pair of arbitrary iterators in generic code (which IMO is one of iterator_range's major use cases), because they would now have to use different classes for different types of iterators. Regards, Nate
Nathan Ridge wrote:
c) shouldn't there be:
template<ForwardIteratorRange> class forward_iterator_range { ... };
...
template<RandomIteratorRange> class random_access_iterator_range : public { size_type size() const; };
...
Wouldn't restructuring interator_range along the lines of the above resolve all the confusion here?
Robert Ramey
It would solve Jonathan's problem, sure.
But it would also hurt people who are trying to use iterator_range to package a pair of arbitrary iterators in generic code (which IMO is one of iterator_range's major use cases), because they would now have to use different classes for different types of iterators.
But doesn't the caller know the concept which his iterator pair models? Hmmm - different subject - when I think about it, it would seem to be that the ForwardIteratorRange concept should in fact support size() since this is easily implementable (albeit inefficiently so). I believe that this would also address the original question. But what really bugs me about the proposal is that it introduces hidden non-obvious behavior. I might invoke size() where it seems "obvious" that it should work and then something else happens because of SFINAE. The current situation where one does something "obvious" but wrong traps with a fault is far superior. I would say that boost in general has too much code which is smarter than the programmer calling it. This makes for surprising behavior which is hard to track down. Robert Ramey
Regards, Nate
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Nathan Ridge wrote:
c) shouldn't there be:
template<ForwardIteratorRange> class forward_iterator_range { ... };
...
template<RandomIteratorRange> class random_access_iterator_range : public { size_type size() const; };
...
Wouldn't restructuring interator_range along the lines of the above resolve all the confusion here?
Robert Ramey
It would solve Jonathan's problem, sure.
But it would also hurt people who are trying to use iterator_range to package a pair of arbitrary iterators in generic code (which IMO is one of iterator_range's major use cases), because they would now have to use different classes for different types of iterators.
But doesn't the caller know the concept which his iterator pair models?
Not if they are writing generic code, i.e. code where the iterator type is (or is dependent on) a template parameter).
Hmmm - different subject - when I think about it, it would seem to be that the ForwardIteratorRange concept should in fact support size() since this is easily implementable (albeit inefficiently so). I believe that this would also address the original question.
This was discussed upthread. To summarize, the standard library makes the design choice of not providing certain operations if they cannot be implemented with a certain asymptotic complexity (for example, subtraction of two iterators if it cannot be implemented in constant time), and Boost is trying to be consistent with this design choice.
But what really bugs me about the proposal is that it introduces hidden non-obvious behavior. I might invoke size() where it seems "obvious" that it should work and then something else happens because of SFINAE. The current situation where one does something "obvious" but wrong traps with a fault is far superior. I would say that boost in general has too much code which is smarter than the programmer calling it. This makes for surprising behavior which is hard to track down.
Right, now the effect of calling size() on iterator_range<I> where I is not random-access is a static assertion failure. With the proposed change, the effect would be a compiler error saying that the function doesn't exist at all. Is that worse from a user's point of view? Perhaps, but not much. Regards, Nate
On Tue, Feb 19, 2013 at 4:17 PM, Nathan Ridge <zeratul976@hotmail.com>wrote: ...
This was discussed upthread. To summarize, the standard library makes the design choice of not providing certain operations if they cannot be implemented with a certain asymptotic complexity (for example, subtraction of two iterators if it cannot be implemented in constant time), and Boost is trying to be consistent with this design choice.
I agree that consistency of the library design is important, but the case is not completely trivial. IMO, this design principle is only a theoretical one. In practice, it is often unhelpful and counterproductive. Because of this principle, STL and C++ miss the big selling point. An end user (who pays for and uses a software product) is interested in the best running time of an algorithm which is determined not only by costs of specific operations, but also by their frequencies. Relatively small number of inefficient operations does not affect the total computational cost of an algorithm. Also, this design principle makes illegal advanced and/or augmented data structures which are beneficial for many complex algorithms. For example, insert() and erase() functions for a single element with O(log N) cost are not allowed by the C++ standard, however, significantly less efficient O(N) operations are allowed for std::vector. I think that the current standard specifications for computational complexities of operations are to some degree obsolete. They create unnecessary restrictions that will be either amended or removed completely in future versions of STL. Regards, Vadim Stadnik
On Tue, Feb 19, 2013 at 2:04 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Tue, Feb 19, 2013 at 4:17 PM, Nathan Ridge <zeratul976@hotmail.com
wrote: ...
This was discussed upthread. To summarize, the standard library makes the design choice of not providing certain operations if they cannot be implemented with a certain asymptotic complexity (for example, subtraction of two iterators if it cannot be implemented in constant time), and Boost is trying to be consistent with this design choice.
I agree that consistency of the library design is important, but the case is not completely trivial. IMO, this design principle is only a theoretical one. In practice, it is often unhelpful and counterproductive. Because of this principle, STL and C++ miss the big selling point.
Okay, let's see why...
An end user (who pays for and uses a software product) is interested in the best running time of an algorithm which is determined not only by costs of specific operations, but also by their frequencies. Relatively small number of inefficient operations does not affect the total computational cost of an algorithm.
Sometimes, yes, I agree. Also, this design principle makes illegal advanced and/or augmented data
structures which are beneficial for many complex algorithms. For example, insert() and erase() functions for a single element with O(log N) cost are not allowed by the C++ standard, however, significantly less efficient O(N) operations are allowed for std::vector.
I'm not really sure what to make of this paragraph. The standard makes some guarantees for std:: data structures, but you're free to provide your own augmented data structures with whatever complexity guarantees make sense, and I guarantee you wouldn't be violating any laws. I think that the current standard specifications for computational
complexities of operations are to some degree obsolete. They create unnecessary restrictions that will be either amended or removed completely in future versions of STL.
Strongly disagree, and you haven't provided any examples of these "unnecessary restrictions" (or you aren't being precise in what you mean). Much code and many algorithms rely on the constant-time random access of std::vector for their own complexity bounds; are you suggestion the standard should drop this complexity guarantee? - Jeff
On Wed, Feb 20, 2013 at 3:12 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 2:04 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Tue, Feb 19, 2013 at 4:17 PM, Nathan Ridge <zeratul976@hotmail.com
wrote: ...
This was discussed upthread. To summarize, the standard library makes the design choice of not providing certain operations if they cannot be implemented with a certain asymptotic complexity (for example, subtraction of two iterators if it cannot be implemented in constant time), and Boost is trying to be consistent with this design choice.
I agree that consistency of the library design is important, but the case is not completely trivial. IMO, this design principle is only a theoretical one. In practice, it is often unhelpful and counterproductive. Because of this principle, STL and C++ miss the big selling point.
Okay, let's see why...
An end user (who pays for and uses a software product) is interested in the best running time of an algorithm which is determined not only by costs of specific operations, but also by their frequencies. Relatively small number of inefficient operations does not affect the total computational cost of an algorithm.
Sometimes, yes, I agree.
Also, this design principle makes illegal advanced and/or augmented data
structures which are beneficial for many complex algorithms. For example, insert() and erase() functions for a single element with O(log N) cost are not allowed by the C++ standard, however, significantly less efficient O(N) operations are allowed for std::vector.
I'm not really sure what to make of this paragraph. The standard makes some guarantees for std:: data structures, but you're free to provide your own augmented data structures with whatever complexity guarantees make sense, and I guarantee you wouldn't be violating any laws.
This is a bit non-standard interpretation of the C++ standard :). Augmented data structures have been recently discussed a number of times by Boost community, some of them are waiting for a review. There is a problem of recognizing the value of augmented data structures for STL, since formally, the subscript operator, function at() and iterators that support std::distance() with O(log N) computational complexity are currently non-standard features and thus many C++ professionals are at least cautious about new data structures.
I think that the current standard specifications for computational
complexities of operations are to some degree obsolete. They create unnecessary restrictions that will be either amended or removed completely in future versions of STL.
Strongly disagree, and you haven't provided any examples of these "unnecessary restrictions" (or you aren't being precise in what you mean). Much code and many algorithms rely on the constant-time random access of std::vector for their own complexity bounds; are you suggestion the standard should drop this complexity guarantee?
I can re-formulate the issue of STL design. After fixing for many years numerous performance bottlenecks caused first of all by linear cost update operations of std::vector, since it is the default STL container, I have come to the following conclusion. Right representation of math concepts through right interfaces is more useful than specification of computational complexities of single operations if a library provides a wide choice of interchangeable containers. The design decisions based on the computational complexity of a single operation are just not practical. At the design time of a library it is not possible to know frequencies of all specific operations for all user algorithms. The parameter of the total computational cost of a user algorithm is more important in real life. The solutions to current inefficiencies of STL are available through advanced data structures, but they are non-standard due to the specification of computational complexities for single operations. Something has to be changed in STL to take full advantage of these solutions. Regards, Vadim Stadnik
On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Wed, Feb 20, 2013 at 3:12 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 2:04 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
[...]
Also, this design principle makes illegal advanced and/or augmented data
structures which are beneficial for many complex algorithms. For example, insert() and erase() functions for a single element with O(log N) cost are not allowed by the C++ standard, however, significantly less efficient O(N) operations are allowed for std::vector.
I'm not really sure what to make of this paragraph. The standard makes some guarantees for std:: data structures, but you're free to provide your own augmented data structures with whatever complexity guarantees make sense, and I guarantee you wouldn't be violating any laws.
This is a bit non-standard interpretation of the C++ standard :).
This = above or below? I guess below :)
Augmented data structures have been recently discussed a number of times by Boost community, some of them are waiting for a review. There is a problem of recognizing the value of augmented data structures for STL, since formally, the subscript operator, function at() and iterators that support std::distance() with O(log N) computational complexity are currently non-standard features and thus many C++ professionals are at least cautious about new data structures.
I think you're overgeneralizing and/or exaggerating. IIRC, the value of augmented data structures is certainly recognized (although I'm not sure of what you mean by "value...for STL"). An operator[] which is O(log N) is not unusual (see std::map), much less "non-standard". Also, IIRC, one issue with an augmented data structure proposed in the (near) past was whether it was appropriate to classify the iterators as random access; I think such iterators (which have logarithmic-time advancement and differencing) are objectively *not* random access (according to the standard), but I agree there is a gap in the standard's iterator classification between random access and bidirectional iterators where an iterator of an augmented data structure may lie. As an event simpler example, a zip_iterator< bidirectional, random access > has *at least* bidirectional traversal, but additionally has constant-time differencing that's lost once an algorithm classifies the iterator as "simply" bidirectional. I think the present standard-endowed traversal categories are motivated by the standard-provided algorithms, so staying entirely within the standard, there probably isn't much need for further traversal granularity. Lastly, I think when you say "(non-)standard feature" you really mean "(non-)standard-*like* feature" (and I have thus far been interpreting such remarks more literally than you probably intended).
I think that the current standard specifications for computational
complexities of operations are to some degree obsolete. They create unnecessary restrictions that will be either amended or removed completely in future versions of STL.
Strongly disagree, and you haven't provided any examples of these "unnecessary restrictions" (or you aren't being precise in what you mean). Much code and many algorithms rely on the constant-time random access of std::vector for their own complexity bounds; are you suggestion the standard should drop this complexity guarantee?
I can re-formulate the issue of STL design. After fixing for many years numerous performance bottlenecks caused first of all by linear cost update operations of std::vector, since it is the default STL container, I have come to the following conclusion.
Let's not forget such performance bugs are not restricted to the STL or even C++ :) http://thedailywtf.com/Articles/InternettoLowerCase.aspx Right representation of math concepts through right interfaces is more
useful than specification of computational complexities of single operations if a library provides a wide choice of interchangeable containers.
But then how do you choose the Right Container For The Job among several choices with similar interfaces? The design decisions based on the computational complexity of a
single operation are just not practical. At the design time of a library it is not possible to know frequencies of all specific operations for all user algorithms. The parameter of the total computational cost of a user algorithm is more important in real life.
Sure, but that doesn't mean you won't have some informed ideas or concrete information on the frequency of *some* specific operations for *some* user algorithm. And this should certainly influence your design decisions, including which data structures are appropriate to use.
The solutions to current inefficiencies of STL
Can you provide examples of such inefficiencies?
are available through advanced data structures, but they are non-standard due to the specification of computational complexities for single operations.
:: mentally replacing "non-standard" with "non-standard-like" :: Sorry, I think I've veered too far from what your original gripe was. I'm still not clear what the problem is with developing and using "non-standard-like" containers (in the sense that maybe they don't offer the same complexity guarantees of its set of operations as other standard data structures...which I think calling them non-standard or non-standard-like is misleading but whatever). Something has to be changed in STL to take full advantage of these
solutions.
- Jeff
On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
...
I think you're overgeneralizing and/or exaggerating. IIRC, the value of augmented data structures is certainly recognized (although I'm not sure of what you mean by "value...for STL").
There is some interest and there are discussions, but the fact is that there are still no containers based on augmented data structures neither in STL nor in Boost libraries. I do not understand this situation, since augmenting of data structures is a relatively simple textbook method. This is also interesting in the light of the other fact that the functional language Haskell provides the augmented data structure Finger Tree. One of the explanations I have found is the standardization of computational complexities of operations for containers and iterators. The main point that I wanted to make in this thread is about damaging effect of this standardization on the generality of programming solutions and the performance optimization using interchangeable types that offer different performance guarantees.
Sure, but that doesn't mean you won't have some informed ideas or concrete information on the frequency of *some* specific operations for *some* user algorithm. And this should certainly influence your design decisions, including which data structures are appropriate to use.
In a well managed software development process both design and implementation can be fine-tuned. However, there is always unknown vector of a future change associated with an enhancement request. The cost of implementing such requests can be reduced with augmented data structures, since they provide a wider set of efficient operations against basic data structures.
The solutions to current inefficiencies of STL
Can you provide examples of such inefficiencies?
The simplest performance test is std::distance ( pos, dist ) ; container.insert ( pos, value ) ; it is discussed in details in this document: https://github.com/vstadnik/stl_ext_adv_review/blob/master/doc/doc/boost_com... Thank you for a number of useful comments. There are, of course, other aspects of augmented data structures, but I think they would be better discussed in a separate thread. Regards, Vadim Stadnik
On 20-02-2013 12:38, Vadim Stadnik wrote:
On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
...
I think you're overgeneralizing and/or exaggerating. IIRC, the value of augmented data structures is certainly recognized (although I'm not sure of what you mean by "value...for STL").
There is some interest and there are discussions, but the fact is that there are still no containers based on augmented data structures neither in STL nor in Boost libraries. I do not understand this situation, since augmenting of data structures is a relatively simple textbook method. This is also interesting in the light of the other fact that the functional language Haskell provides the augmented data structure Finger Tree. One of the explanations I have found is the standardization of computational complexities of operations for containers and iterators.
We have no problem with containers that have different complexity guarantees for certain operations. As long as the complexities are clearly documented and explained. -Thorsten
On Thu, Feb 21, 2013 at 8:20 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 20-02-2013 12:38, Vadim Stadnik wrote:
On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
I think you're overgeneralizing and/or exaggerating. IIRC, the value of augmented data structures is certainly recognized (although I'm not sure of what you mean by "value...for STL").
There is some interest and there are discussions, but the fact is that there are still no containers based on augmented data structures neither in STL nor in Boost libraries. I do not understand this situation, since augmenting of data structures is a relatively simple textbook method. This is also interesting in the light of the other fact that the functional language Haskell provides the augmented data structure Finger Tree. One of the explanations I have found is the standardization of computational complexities of operations for containers and iterators.
We have no problem with containers that have different complexity guarantees for certain operations. As long as the complexities are clearly documented and explained.
This is very encouraging! Hopefully, one day Boost community will solve the challenging problem - how to add augmented, advanced and other data structures to the C++ STL. For the beginning, there are two libraries ("STL Extensions" and "Countertree") in Boost review schedule: http://www.boost.org/community/review_schedule.html I am asking if anyone could volunteer to become a review manager for any of these libraries. Regards, Vadim Stadnik
On 21-02-2013 13:49, Vadim Stadnik wrote:
On Thu, Feb 21, 2013 at 8:20 PM, Thorsten Ottosen <
We have no problem with containers that have different complexity guarantees for certain operations. As long as the complexities are clearly documented and explained.
This is very encouraging! Hopefully, one day Boost community will solve the challenging problem - how to add augmented, advanced and other data structures to the C++ STL. For the beginning, there are two libraries ("STL Extensions" and "Countertree") in Boost review schedule:
http://www.boost.org/community/review_schedule.html
I am asking if anyone could volunteer to become a review manager for any of these libraries.
This should be a post on its own ("Review Managers wanted for XXX"), not something announced in some unrelated thread. regards -Thorsten
On Mon, Feb 18, 2013 at 4:06 PM, Robert Ramey <ramey@rrsd.com> wrote:
Dave Abrahams wrote:
on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org>
wrote:
[...]
Given that I'm already requiring the type can be used with std::begin() and std::end(), i.e. is range-like, I'm happy to not support types that have a non-range-like size(). If your type quacks like a duck but swims like a fish it doesn't meet my requirements for a duck.
This sounds like the language commonly used in the Python community about (their version of) concepts. < http://grokbase.com/t/python/python-list/02c225syvb/source-code-size-metric-...
There's no "range-like." There's a family of Range concepts:
http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/concepts.html
http://www.boost.org/community/generic_programming.html#concept
Maybe I'm off base here, but reading the above makes it hard for me to hear the rest of what you wrote.
FWIW - we had a thread a couple of months ago regarding Boost Range concepts, how they were defined and how they were implemented and what they should mean for users of Boost Range. I was dissatisfied with all three of these aspects of Boost Range but couldn't convince anyone else of my point of view.
Which three aspects are you referring to?
Looking that the documentation/synopsis of iterator_range<T> I see a few things of interest:
a) Documentation says that it fullfills the ForwardIteratorRange concept - OK
You mean the Forward Range concept. And there is a caveat that a subset of the interface is still available for Single Pass Iterators as well.
b) But then it includes the size() function - so doesn't that mean that it full fills the concept for RandomAccessRange concept? very confusing.
2 things: - Forward Iterator Range + size() does not give you a Random Access Range; you need a lot more; see [1]. - size() is listed under "for Random Access Range only". Maybe there should be an additional note that an iterator_range of a Random Access Iterator is a Random Access Range, but other than that, I'm not sure what's confusing, and I suspect it isn't the aforementioned that you're finding confusing. c) shouldn't there be:
template<ForwardIteratorRange> class forward_iterator_range { ... };
...
template<RandomIteratorRange> class random_access_iterator_range : public { size_type size() const; };
Boost Range concept doesn't specify size() for a ForwardIteratorRange. But I think this is another mistake since size() could be implemented (in a different way) for iterators fullfilling this concept.
In a different O(n) way, sure, but the standard has made a conscious decision to keep any size functions O(1). If you want a potentially O(n) "size", just do distance. You can augment your classification of ranges to include RangesWithConstantTimeSize, which would include all Random Access Ranges as well as some non-Random Access Ranges. But there is no such precisely-defined, widely agreed-upon concept and corresponding interface (AFAIK). Wouldn't restructuring interator_range along the lines of the above resolve
all the confusion here?
As pointed out before, that requires you to dig out the traversal category of your iterator in order to choose the right iterator_range variant. Eventually we'd just end up with a trait that wraps a given iterator with the iterator_range variant with the strongest traversal category, which usage-wise isn't really much different from the present situation. - Jeff [1] http://www.boost.org/libs/range/doc/html/range/concepts/random_access_range....
Jonathan, Hello! I agree that the current implementation of size() sucks. I think the standard library design is a bit pants too. I intend to make providing implementations of size via ADL extension points. Once this has been done I'll make the boost::size algorithm work via this extension point and deprecate the iterator_range::size() member function. I inherited this mistake IIRC. I'm happy to sort it out. Just give me some time. I'm busy crushing Getco ;-) Neil On Mon, Feb 18, 2013 at 10:50 AM, Jonathan Wakely <jwakely.boost@kayari.org>wrote:
On 18 February 2013 10:19, Nathan Ridge wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Yes, that perfectly sums up my use case, thanks.
I'm not "Depending on members of a third party component", I'm writing a generic component and someone tried to use it with boost::iterator_range and asked me why it didn't work.
The reason iterator_range::size() doesn't use std::distance is given at http://permalink.gmane.org/gmane.comp.lib.boost.devel/193055 I think it's a valid choice to only allow size() when its O(1), c.f. std::forward_list, but I think it would be even better to not even define it when it can't be used, c.f. std::forward_list.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 19 February 2013 16:46, Neil Groves wrote:
Jonathan,
Hi Neil,
Hello! I agree that the current implementation of size() sucks. I think the standard library design is a bit pants too. I intend to make providing implementations of size via ADL extension points. Once this has been done I'll make the boost::size algorithm work via this extension point and deprecate the iterator_range::size() member function.
I inherited this mistake IIRC.
I'm happy to sort it out. Just give me some time. I'm busy crushing Getco ;-)
No rush, I know game-changing comes first ;-) I've already got a workaround in place, so created the ticket as a "I think this would be better" not "I need this right now!"
on Mon Feb 18 2013, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
But you can't detect that in general. If you're trying to make this work in generic code, simply fixing it for iterator_range doesn't fix anything.
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general). -- Dave Abrahams
On 18 February 2013 18:04, Dave Abrahams wrote:
on Mon Feb 18 2013, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
But you can't detect that in general. If you're trying to make this work in generic code, simply fixing it for iterator_range doesn't fix anything.
It fixes my generic template so it can be used with iterator_range. What's the general case you're referring to? Do you mean because there are other cases (apart from iterator_range) where a size() member function exists, but must not be called?
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
AMDG On 02/18/2013 10:15 AM, Jonathan Wakely wrote:
On 18 February 2013 18:04, Dave Abrahams wrote:
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
That's irrelevant. The point is that the range concepts provide no such requirement. It is unsafe to rely on any behavior which is not intentional and explicitly documented, /especially/ with generic code. In Christ, Steven Watanabe
On 18 February 2013 18:56, Steven Watanabe wrote:
AMDG
On 02/18/2013 10:15 AM, Jonathan Wakely wrote:
On 18 February 2013 18:04, Dave Abrahams wrote:
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
That's irrelevant. The point is that the range concepts provide no such requirement. It is unsafe to rely on any behavior which is not intentional and explicitly documented, /especially/ with generic code.
What range concepts? The Boost ones? My template is not part of Boost and does not claim to interoperate with Boost.Range or work with models of its concepts. My template works with standard containers and arrays, someone tried to use it with iterator_range and it failed, so I asked for a change to make iterator_range::size() more user-friendly. It seems that's unpopular, which is fine by me. Nathan, feel free to close the ticket.
On Mon, Feb 18, 2013 at 11:10 AM, Jonathan Wakely <jwakely.boost@kayari.org>wrote:
On 18 February 2013 18:56, Steven Watanabe wrote:
AMDG
On 02/18/2013 10:15 AM, Jonathan Wakely wrote:
On 18 February 2013 18:04, Dave Abrahams wrote:
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
That's irrelevant. The point is that the range concepts provide no such requirement. It is unsafe to rely on any behavior which is not intentional and explicitly documented, /especially/ with generic code.
What range concepts? The Boost ones? My template is not part of Boost and does not claim to interoperate with Boost.Range or work with models of its concepts. My template works with standard containers and arrays, someone tried to use it with iterator_range and it failed, so I asked for a change to make iterator_range::size() more user-friendly. It seems that's unpopular, which is fine by me. Nathan, feel free to close the ticket.
IMHO, Jon's making a reasonable QOI request, it's just the costs to implement it don't appear (in the view of the community) to outweigh the benefits. Philosophically, all things being equal, I'm on board with iterator_range only defining those member functions it actually supports; sadly, the language doesn't make this trivial :( - Jeff
on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org> wrote:
On 18 February 2013 18:56, Steven Watanabe wrote:
AMDG
On 02/18/2013 10:15 AM, Jonathan Wakely wrote:
On 18 February 2013 18:04, Dave Abrahams wrote:
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
That's irrelevant. The point is that the range concepts provide no such requirement. It is unsafe to rely on any behavior which is not intentional and explicitly documented, /especially/ with generic code.
What range concepts? The Boost ones? My template is not part of Boost and does not claim to interoperate with Boost.Range or work with models of its concepts. My template works with standard containers and arrays, someone tried to use it with iterator_range and it failed, so I asked for a change to make iterator_range::size() more user-friendly. It seems that's unpopular, which is fine by me.
I am not sure it's unpopular. I think there's just some concern about whether it achieves what we ultimately want. Maybe there's a more generally-useful way to get the same benefits. -- Dave Abrahams
on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org> wrote:
On 18 February 2013 18:04, Dave Abrahams wrote:
on Mon Feb 18 2013, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
Could you share a use case that requires to depend on size() specifically rather than the iterator category?
Given an arbitrary range r, determine its size by the fasest means possible.
If we use std::distance, we can do it in O(1) for std::vector, O(n) for std::map, and O(n) for std::forward_list.
If we can detect whether "r.size()" is a valid expression, and use that if available, and std::distance otherwise, then we have O(1) for std::vector, O(1) for std::map, and O(n) for std::forward_list. Notice how that's an improvement for std::map.
But you can't detect that in general. If you're trying to make this work in generic code, simply fixing it for iterator_range doesn't fix anything.
It fixes my generic template so it can be used with iterator_range.
What's the general case you're referring to?
Do you mean because there are other cases (apart from iterator_range) where a size() member function exists, but must not be called?
Yes.
However, if detecting whether "r.size()" is a valid expression cannot be done reliably (for example, if we determine that for iterator_range<I> where I is not random-access it is a valid expression, but then that static-asserts on us), then we can't use this approach.
Then you can't use this approach (in general).
Why? What other range-like types provide an size() member that appears to be callable but must not be called?
Anyone else's personal version of iterator_range, for example, that hasn't yet had this process applied to it. Also there are some types that might provide a size() with different meaning (or efficiency) than you expect. -- Dave Abrahams
On 18/02/13 06:30, Nathan Ridge wrote:
The suggested workaround is to give iterator_range a base class, specialize this base class for random-access iterators, and only define size() in this specialization.
This kind of thing is very tedious to do, this is exactly why class-scope static_if is so useful.
On 18-02-2013 13:32, Mathias Gaunard wrote:
On 18/02/13 06:30, Nathan Ridge wrote:
The suggested workaround is to give iterator_range a base class, specialize this base class for random-access iterators, and only define size() in this specialization.
This kind of thing is very tedious to do, this is exactly why class-scope static_if is so useful.
Would using enable_if on size() not solve the problem? -Thorsten
On 2013-02-19 17:01:14 +0000, Jonathan Wakely said:
On 19 February 2013 17:00, Thorsten Ottosen wrote:
Would using enable_if on size() not solve the problem?
It's not a template function, so you can't.
I'm not suggesting to actually use the following hack in boost::iterator_range, but since you claimed the opposite, this trick has the wished SFINAE behavior in C++11. /Pyry. * * * #include <list> #include <vector> struct zero { template <typename T> T && operator+(T && x) const { return std::forward<T>(x); } }; template <typename T> struct always_zero { using type = zero; }; template <typename I> struct iterator_range { I b, e; iterator_range(I b, I e) : b(b), e(e) {} // SFINAE trick: template <typename Ignore=void> auto size(typename always_zero<Ignore>::type z={}) -> decltype(z + e - b) { return e - b; } }; using std::begin; using std::end; template <typename R> auto make_iterator_range(R const & r) -> iterator_range<decltype(begin(r))> { return iterator_range<decltype(begin(r))>(begin(r), end(r)); } int main() { std::list<int> list; std::vector<int> vector; auto r1 = make_iterator_range(list); // no error auto r2 = make_iterator_range(vector); // r1.size(); // compiler error r2.size(); } * * * -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
On 19 February 2013 18:18, Pyry Jahkola wrote:
On 2013-02-19 17:01:14 +0000, Jonathan Wakely said:
On 19 February 2013 17:00, Thorsten Ottosen wrote:
Would using enable_if on size() not solve the problem?
It's not a template function, so you can't.
I'm not suggesting to actually use the following hack in boost::iterator_range, but since you claimed the opposite, this trick has the wished SFINAE behavior in C++11.
Yes, "can't" was too strong. "Can't without changing the signature and making it even uglier than most SFINAE tricks" would have been more accurate!
On Tue, Feb 19, 2013 at 5:00 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 18-02-2013 13:32, Mathias Gaunard wrote:
On 18/02/13 06:30, Nathan Ridge wrote:
The suggested workaround is to give iterator_range a base class,
specialize this base class for random-access iterators, and only define size() in this specialization.
This kind of thing is very tedious to do, this is exactly why class-scope static_if is so useful.
Would using enable_if on size() not solve the problem?
I think this is tricky to achieve without obfuscating the code, which might be ok. I've been dissatisfied when attempting to optimally write generic algorithms and require size. Obviously I've found this to be a more general problem than with just iterator_range. It is a problem that plagues the development of writing generic algorithms. Frequently knowing if one has access to an O(1) size appreciably changes an optimal implementation. Dave mentioned that std::map has O(1) size and yet from the iterators we only have access to non-member distance. I have been wrestling with this issue for some time, and think that deprecating the member function size() on iterator_range combined with the provision of an extensible boost::size(rng) that has O(1) would be a reasonable compromise. We have boost::distance already which provides the complexity guarantee equivalent of std::distance. If we add boost::size(rng) that delegates to range_size then I could provide implemetentations for the standard containers, and users could augment the behaviour to keep O(1) size for other containers, and could even choose to loosen the performance guarantee if they desired. To me this seems simpler than having more base classes, but comes at the cost of eventually breaking backward compatibility. I've been very wary to discuss this since I've never managed to convince myself sufficiently that this is the optimal solution. I'm extremely reluctant to break interfaces, but with a sufficient period for the deprecation perhaps the community would prefer this option? I'm very keen to hear the thoughts of current users since I am unsure how much code relies upon iterator_range member size() function. Additionally I bet Thorston and Nate have some great ideas. -Thorsten
Thanks for all of your help and input, and sorry for being so slow to address some of these issues. Regards, Neil Groves
______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
On Wed, Feb 20, 2013 at 0:13 AM, Neil Groves <neil@grovescomputing.com> wrote:
I'm very keen to hear the thoughts of current users since I am unsure how much code relies upon iterator_range member size() function.
The codebase my colleagues and I manage makes heavy use of the boost range library. I do not think that a single line of code depends of size being a method of iterator_range. Actually, before reading this thread I assumed that boost::size would work via ADL extension points similar to boost::begin and boost::end. Even if it would break some code, it seems easy enough to replace the calls to the method size with calls to the function. We would trade some breaking tests for a better library any day (well, most days at least). Markus www.clean-cpp.org
On 20-02-2013 00:11, Neil Groves wrote:
To me this seems simpler than having more base classes, but comes at the cost of eventually breaking backward compatibility.
I've been very wary to discuss this since I've never managed to convince myself sufficiently that this is the optimal solution. I'm extremely reluctant to break interfaces, but with a sufficient period for the deprecation perhaps the community would prefer this option?
I have been wrestling with this issue for some time, and think that deprecating the member function size() on iterator_range combined with the provision of an extensible boost::size(rng) that has O(1) would be a reasonable compromise. We have boost::distance already which provides the complexity guarantee equivalent of std::distance. If we add boost::size(rng) that delegates to range_size then I could provide implemetentations for the standard containers, and users could augment the behaviour to keep O(1) size for other containers, and could even choose to loosen the performance guarantee if they desired.
I'm very keen to hear the thoughts of current users since I am unsure how much code relies upon iterator_range member size() function. Additionally I bet Thorston and Nate have some great ideas.
-1 for the idea of introducing another base class. Breaking the interface could be done, but I guess we would have 2 or three releases before it actually came into the code? What's the official Boost policy on this matter? I don't know how much that time line would help Jonathan's clients or those writing generic code that accepts an O(n) time size operation. Having a tool for getting the O(1) size() from containers which currently fail to work with boost::size() would be good. However, how do we do that without concept-based overloading? -Thorsten
on Wed Feb 20 2013, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
Breaking the interface could be done, but I guess we would have 2 or three releases before it actually came into the code? What's the official Boost policy on this matter?
There isn't one. -- Dave Abrahams
On Wed, Feb 20, 2013 at 2:57 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 20-02-2013 00:11, Neil Groves wrote:
To me this seems simpler than having more base classes, but comes at the
cost of eventually breaking backward compatibility.
I've been very wary to discuss this since I've never managed to convince myself sufficiently that this is the optimal solution. I'm extremely reluctant to break interfaces, but with a sufficient period for the deprecation perhaps the community would prefer this option?
I have been wrestling with this issue for some time, and think that deprecating the member function size() on iterator_range combined with the provision of an extensible boost::size(rng) that has O(1) would be a reasonable compromise. We have boost::distance already which provides the complexity guarantee equivalent of std::distance. If we add boost::size(rng) that delegates to range_size then I could provide implemetentations for the standard containers, and users could augment the behaviour to keep O(1) size for other containers, and could even choose to loosen the performance guarantee if they desired.
I'm very keen to hear the thoughts of current users since I am unsure how
much code relies upon iterator_range member size() function. Additionally I bet Thorston and Nate have some great ideas.
-1 for the idea of introducing another base class.
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng). Then generic algorithms can be written by using boost::size(rng) knowing that the optimal solution will be selected. This also allows the users to customise and chose trade-offs in generic support versus algorithm complexity.
Breaking the interface could be done, but I guess we would have 2 or three releases before it actually came into the code? What's the official Boost policy on this matter? I don't know how much that time line would help Jonathan's clients or those writing generic code that accepts an O(n) time size operation.
Since the solution I propose is not a new base-class it solves the problem both more completely and immediately. The users of Boost.Range would simply be encouraged to use the non-member function. In parallel the member function size() on iterator_range can be deprecated and subsequently removed.
Having a tool for getting the O(1) size() from containers which currently fail to work with boost::size() would be good. However, how do we do that without concept-based overloading?
As dull as it may seem I think, just allowing a simple extension point would be fine. We could simply provide the standard containers and container writers could implement an overload. This is probably simpler than adding additional trait classes etc. I am torn between a simple ADL extension point and combining this with a n additional type_trait. It seems the idiomatic thing to do would be to use a trait, but when I think through the use-cases the code required for the container developer is longer with the trait. Currently I'm leaning toward just providing a simple ADL extension point. It would address this problem and one of the biggest niggles I come across when writing generic algorithm code.
-Thorsten
Thanks, Neil Groves
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com>wrote: [...]
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng).
You mean like range_calculate_size [1] ? [1] http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/con... - Jeff
On Wed, Feb 20, 2013 at 9:02 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com
wrote: [...]
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng).
You mean like range_calculate_size [1] ?
Exactly I thought that when I introduced this it has been quite successful, and that we could build upon this by adding the optimal implementations for standard library components. I have been using this as an extension mechanism privately in this manner for a while and it has worked well for me. I wanted to get other peoples views on this solution before making the extension mechanism more widely used and optimised by default for the standard library containers.
[1]
http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/con...
- Jeff
Thanks, Neil Groves
On 20-02-2013 22:12, Neil Groves wrote:
On Wed, Feb 20, 2013 at 9:02 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com
wrote: [...]
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng).
You mean like range_calculate_size [1] ?
Exactly I thought that when I introduced this it has been quite successful, and that we could build upon this by adding the optimal implementations for standard library components. I have been using this as an extension mechanism privately in this manner for a while and it has worked well for me. I wanted to get other peoples views on this solution before making the extension mechanism more widely used and optimised by default for the standard library containers.
I would like to keep boost::size() O(1). Anybody that writes code relying on boost::size() should know that this is guaranteed. As I understand it, there is a wish from som users to get a size even when O(1) time is not possible. This suggest to me that we also need to extend boost::distance() to work for containers. Either way, customizing a trait/providing an overload for every standard and boost container seems to be a solution that scales poorly and which requires huge amounts of code to be included. -Thorsten
On 2/21/2013 5:18 AM, Thorsten Ottosen wrote:
On 20-02-2013 22:12, Neil Groves wrote:
On Wed, Feb 20, 2013 at 9:02 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com
wrote: [...]
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng).
You mean like range_calculate_size [1] ?
Exactly I thought that when I introduced this it has been quite successful, and that we could build upon this by adding the optimal implementations for standard library components. I have been using this as an extension mechanism privately in this manner for a while and it has worked well for me. I wanted to get other peoples views on this solution before making the extension mechanism more widely used and optimised by default for the standard library containers.
I would like to keep boost::size() O(1). Anybody that writes code relying on boost::size() should know that this is guaranteed.
As I understand it, there is a wish from some users to get a size even when O(1) time is not possible. This suggest to me that we also need to extend boost::distance() to work for containers.
+1 Jeff
-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeff Flinn Sent: Thursday, February 21, 2013 4:06 PM To: boost@lists.boost.org Subject: Re: [boost] [range] [general] making member functions SFINAE-friendly
On 2/21/2013 5:18 AM, Thorsten Ottosen wrote:
On 20-02-2013 22:12, Neil Groves wrote:
On Wed, Feb 20, 2013 at 9:02 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com
wrote: [...]
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng).
You mean like range_calculate_size [1] ?
Exactly I thought that when I introduced this it has been quite successful, and that we could build upon this by adding the optimal implementations for standard library components. I have been using this as an extension mechanism privately in this manner for a while and it has worked well for me. I wanted to get other peoples views on this solution before making the extension mechanism more widely used and optimised by default for the standard library containers.
I would like to keep boost::size() O(1). Anybody that writes code relying on boost::size() should know that this is guaranteed.
As I understand it, there is a wish from some users to get a size even when O(1) time is not possible. This suggest to me that we also need to extend boost::distance() to work for containers.
+1 (though I don't like the name much - is length possible name?) Paul PS I think that the Standard is unwise in specifying what seems to me a Quality of Implementation issue. It should specify that the implementation should document what is achieves (or even probably achieves - I'm not sure that is it always fixed). --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow@hetp.u-net.com
On Thu, Feb 21, 2013 at 2:18 AM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 20-02-2013 22:12, Neil Groves wrote:
On Wed, Feb 20, 2013 at 9:02 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Wed, Feb 20, 2013 at 12:55 PM, Neil Groves <neil@grovescomputing.com
wrote:
[...]
I agree. My suggestion didn't have a new base class. I think by making
boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and
boost::end(rng).
You mean like range_calculate_size [1] ?
Exactly I thought that when I introduced this it has been quite
successful, and that we could build upon this by adding the optimal implementations for standard library components. I have been using this as an extension mechanism privately in this manner for a while and it has worked well for me. I wanted to get other peoples views on this solution before making the extension mechanism more widely used and optimised by default for the standard library containers.
I would like to keep boost::size() O(1). Anybody that writes code relying on boost::size() should know that this is guaranteed.
Agreed. As I understand it, there is a wish from som users to get a size even when
O(1) time is not possible. This suggest to me that we also need to extend boost::distance() to work for containers.
+1 Either way, customizing a trait/providing an overload for every standard
and boost container seems to be a solution that scales poorly and which requires huge amounts of code to be included.
This can be mitigated somewhat if range_calculate_size(r) defaults to r.size() if that is available, but there's the tradeoff that r publishes a non-O(1) size member function, in which case range_calculate_size must be explicitly overridden. And then there are the cases when r.size() static asserts :/ In any case, providing an overload for every standard and boost container is what we already do with swap, so there is precedent. - Jeff
On Thu, Feb 21, 2013 at 12:55 AM, Neil Groves <neil@grovescomputing.com> wrote:
Since the solution I propose is not a new base-class it solves the problem both more completely and immediately. The users of Boost.Range would simply be encouraged to use the non-member function. In parallel the member function size() on iterator_range can be deprecated and subsequently removed.
Hmm, may I ask not to deprecate the member size()? Not that I have a special case that cannot be solved with the free size() function, it's just we have a lot of code that uses the member size(). Also, member size() looks a little bit more natural to me, although this is a matter of habit, I guess.
participants (15)
-
Andrey Semashev -
Dave Abrahams -
Jeff Flinn -
Jeffrey Lee Hellrung, Jr. -
Jonathan Wakely -
Markus Klein -
Mathias Gaunard -
Nathan Ridge -
Neil Groves -
Paul A. Bristow -
Pyry Jahkola -
Robert Ramey -
Steven Watanabe -
Thorsten Ottosen -
Vadim Stadnik