Re: [Boost-users] [Range] size and list, for example.

Subject: Re: [Boost-users] [Range] size and list, for example.
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2013-04-12 02:17:59

> I know this has come up before, so I'm really seeking to discover the  
> current situation. 
>  
> boost::size( std::list<...> ) fails because the implementation of size  
> is end - begin. 
>  
> I know I could use distance, but am surprised size(list) doesn't work  
> out of the box. 
>  
> * So, is it correct that size(list) doesn't work? 
>
> * Does distance(begin, end) specialise for random access iterators to  
> O(n) performance? 
>
> * Why doesn't size similarly specialise? 

size() and distance() have different purposes.

size() is for when you want to know the size of a range in constant
time, and do something else if it cannot be determined in constant time.

distance() is for when you want to know the size of a range
regardless of whether it takes constant time or linear time to
calculate.

Note that Boost.Range provides a distance(range) overload of distance,
so it's not any more verbose to use than size() if your use case is
the second one.

Regarding std::list, there are different stories for C++98 and C++11:

In C++98, the complexity of std::list::size() was not guaranteed to
be constant [1]. My understanding is that some implementations didn't 
keep track of the size in order to implement constant-time splice(),
and consequently their size() was linear-time. So I think that it is
not reasonable to expect that size() works for std::list in C++98.

In C++11, however, the complexity of std::list::size() is guaranteed 
to be constant [1]. Therefore, I think it would be reasonable if in
C++11, Boost.Range provided a specialized version of size() for 
std::list that forwarded to std::list::size(). This has not been
implemented yet. If you would like to see it implemented, please file
a Trac ticket. If no one objects to this addition, I will implement
it when I get a chance.

Regards,
Nate

[1] http://www.cplusplus.com/reference/list/list/size/