Boost logo

Boost :

Subject: Re: [boost] [range] [general] making member functions SFINAE-friendly
From: Jonathan Wakely (jwakely.boost_at_[hidden])
Date: 2013-02-18 10:05:11

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.

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