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.