On Wed, Feb 20, 2013 at 2:57 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 20-02-2013 00:11, Neil Groves wrote:
To me this seems simpler than having more base classes, but comes at the
cost of eventually breaking backward compatibility.
I've been very wary to discuss this since I've never managed to convince myself sufficiently that this is the optimal solution. I'm extremely reluctant to break interfaces, but with a sufficient period for the deprecation perhaps the community would prefer this option?
I have been wrestling with this issue for some time, and think that deprecating the member function size() on iterator_range combined with the provision of an extensible boost::size(rng) that has O(1) would be a reasonable compromise. We have boost::distance already which provides the complexity guarantee equivalent of std::distance. If we add boost::size(rng) that delegates to range_size then I could provide implemetentations for the standard containers, and users could augment the behaviour to keep O(1) size for other containers, and could even choose to loosen the performance guarantee if they desired.
I'm very keen to hear the thoughts of current users since I am unsure how
much code relies upon iterator_range member size() function. Additionally I bet Thorston and Nate have some great ideas.
-1 for the idea of introducing another base class.
I agree. My suggestion didn't have a new base class. I think by making boost::size(rng) call range_size(rng) we can provide an extension method similar to that already provided for boost::begin(rng) and boost::end(rng). Then generic algorithms can be written by using boost::size(rng) knowing that the optimal solution will be selected. This also allows the users to customise and chose trade-offs in generic support versus algorithm complexity.
Breaking the interface could be done, but I guess we would have 2 or three releases before it actually came into the code? What's the official Boost policy on this matter? I don't know how much that time line would help Jonathan's clients or those writing generic code that accepts an O(n) time size operation.
Since the solution I propose is not a new base-class it solves the problem both more completely and immediately. The users of Boost.Range would simply be encouraged to use the non-member function. In parallel the member function size() on iterator_range can be deprecated and subsequently removed.
Having a tool for getting the O(1) size() from containers which currently fail to work with boost::size() would be good. However, how do we do that without concept-based overloading?
As dull as it may seem I think, just allowing a simple extension point would be fine. We could simply provide the standard containers and container writers could implement an overload. This is probably simpler than adding additional trait classes etc. I am torn between a simple ADL extension point and combining this with a n additional type_trait. It seems the idiomatic thing to do would be to use a trait, but when I think through the use-cases the code required for the container developer is longer with the trait. Currently I'm leaning toward just providing a simple ADL extension point. It would address this problem and one of the biggest niggles I come across when writing generic algorithm code.
-Thorsten
Thanks, Neil Groves