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.