Distance/size of boost ranges for std::set.
Hi, I'm working within a C++ library which makes extensive use of the range concept, and also of boost::size. The current version of the library makes use of boost 1_38, however, updating to the newer versions of boost, I've had to replace boost::size with boost::distance as some of the ranges involved, such as std::set don't have random access iterators. However, this presents a problem - it's not really acceptable within our application to have linear time complexity for the size operation on sets when the size member function of the set container is constant time, so I'm looking for some advice. Are we misusing the range concept here and should be using something else? Everything other than this matches up nicely, and it's only the time complexity with regards to boost::distance that will cause problems. Should we simply be extending the boost::size function with additional overloaded versions specific to std::set if we wish to use it in this way (is this reasonable?)? Thanks in advance! Matthew Gwynne
On 11.10.2010 11:32, Matthew Gwynne wrote:
Hi,
I'm working within a C++ library which makes extensive use of the range concept, and also of boost::size. The current version of the library makes use of boost 1_38, however, updating to the newer versions of boost, I've had to replace boost::size with boost::distance as some of the ranges involved, such as std::set don't have random access iterators.
However, this presents a problem - it's not really acceptable within our application to have linear time complexity for the size operation on sets when the size member function of the set container is constant time, so I'm looking for some advice.
Are we misusing the range concept here and should be using something else?
Well, either you're expecting constant-time size for subsets of set, or you're using range to represent the entire set. The former is a wrong expectation, the latter could be called a misuse, yes. The alternative depends on what exactly you're doing currently that requires the size. Sebastian
On 11/10/10 10:32, Matthew Gwynne wrote:
Should we simply be extending the boost::size function with additional overloaded versions specific to std::set if we wish to use it in this way (is this reasonable?)?
There was an idea of making boost::size(c) call c.size(), boost::sort(c) use c.sort() etc. if those were available. I don't know what exactly happened to that idea, or why it was scrapped.
Hi,
On Mon, Oct 11, 2010 at 5:31 PM, Mathias Gaunard
On 11/10/10 10:32, Matthew Gwynne wrote:
Should we simply be extending the boost::size function with additional overloaded versions specific to std::set if we wish to use it in this way (is this reasonable?)?
There was an idea of making boost::size(c) call c.size(), boost::sort(c) use c.sort() etc. if those were available.
I don't know what exactly happened to that idea, or why it was scrapped.
Well this was basically what we were expecting initially. The functions in question are given a container, it's a standard container, why not use the special method for the few cases are well known and achieve reasonable performance? On the other hand, I can see from a simplicity of explanation and modelling point of few why only considering the iterators for the containers makes sense (as this is the only thing, in theory, the range works on). What I'm wondering is, is there a better concept if one wants 1) the generic approach of a container (allowing everything up to and including pairs of iterators etc), but 2) achieving reasonable performance for the size/distance operation on containers which allow this? Certainly one can extend the operations oneself, but when one updates to a new boost version, this can cause endless headaches, and it may not fit with the underlying philosophy of the library. Therefore, I'm just wondering what others suggest. I'd certainly be very much interested in reading any mailing list posts or other material surrounding past discussions of this issue! Thanks! Matthew
participants (3)
-
Mathias Gaunard -
Matthew Gwynne -
Sebastian Redl