Re: [boost] boost::range needs help

From: Neal Becker (ndbecker2_at_[hidden])
Date: 2007-09-25 11:20:01

Giovanni Piero Deretta wrote:

> On 9/25/07, Neal Becker <ndbecker2_at_[hidden]> wrote:
>> Thorsten Ottosen wrote:
>>
>> > Neal Becker skrev:
>> >> boost::size of a std::list gives:
>> >>
>> >> /usr/local/src/boost.hg/boost/range/size.hpp:28: error: no match
>> >> for 'operator-' in 'boost::end [with T = std::list<double,
>> >> std::allocator<double> >](((const std::list<double,
>> >> std::allocator<double>
>> >>> &)((const std::list<double, std::allocator<double> >*)r))) -
>> >>> boost::begin
>> >> [with T = std::list<double, std::allocator<double> >](((const
>> >> std::list<double, std::allocator<double> >&)((const std::list<double,
>> >> std::allocator<double> >*)r)))'
>> >>
>> >> I would hope that boost::size (type with member .size()) would use the
>> >> member .size().
>> >
>> > Use boost::distance( my_list );
>> >
>> > size() was changed to reflect O(1) complexity.
>> >
>> > -Thorsten
>>
>> Sorry, I don't think that was my question.  boost::size(T t) has a
>> default
>> implementation using t.end()-t.begin() (in boost/range/size.hpp).  I can
>> supply my own implementation of size(std:list<T>).  I was wishing that
>> boost::size would implement boost::size using the member .size() if it
>> exists.
>>
> 
> I think that what Thorsten was saying ist that the whole point of
> using operator- is to guarantee that boost::size is *always* O(1).
> 
> With some list implementations size is O(N), so forwarding to .size()
> would violate the guarantee. If you really need to know the size but
> do not care of the complexity guarantee, you can use boost::distance.
> 
Thank you.  I understand that now.  But doesn't this conflict with the range
documentation?  Look at the last statement:

size(x): ...
std::distance(p.first,p.second) if p is of type std::pair<T>
 sz if a is an array of size sz
 end(s) - s if s is a string literal or a Char*
 boost_range_size(x) if that expression would invoke a function found by ADL 
 t.size() otherwise