On Tue, Jun 26, 2012 at 5:12 PM, Michel Morin <mimomorin@gmail.com> wrote:
Jeffrey Lee Hellrung, Jr. wrote:
My rebuttal is that: [...] (b) Range adaptors can be free to cache begin and end iterators (in addition to the adapted range), if that would yield noticeably better performance for more than one begin/end calls (e.g., filtered_range and dropped_range), but I suspect for most range adaptors, it doesn't make a difference. Take, for example, a transformed_range. If it's implemented as a pair of transform_iterators, calling begin/end requires copying the underlying iterators in addition to the transform function. If transformed_range is implemented as the underlying range paired with a function, calling begin/end requires generating the underlying begin/end iterators and still copying the transformation function. If copying the underlying iterators is no faster than generating the begin/end iterators from the underlying range, there should be no difference in performance between the two implementations of transformed_range. Of course, there's a big assumption on the relative speed of begin/end versus iterator copying of the underlying range, but I think it's, again, the common case; it's something we can aim to guarantee for all provided range adaptors; and if it's a client range that fails this assumption, we can provide a facility (oh yeah, that's what iterator_range is for) to explicitly address this. [...]
I don't know what the consequence of the following fact is, but it's worth noting:
Repeatedly adapted ranges might have **very** large size. For example, on Mac OS X 10.7 with gcc-4.7,
std::vector<int> v;
sizeof(v | uniqued) --> 32 sizeof(v | uniqued | uniqued) --> 80 sizeof(v | uniqued | uniqued | uniqued) --> 176 sizeof(v | uniqued | uniqued | uniqued | uniqued) --> 368
// OvenToBoost's taken adaptor sizeof(v | taken(1)) --> 48 sizeof(v | taken(1) | taken(1)) --> 112 sizeof(v | taken(1) | taken(1) | taken(1)) --> 240 sizeof(v | taken(1) | taken(1) | taken(1) | taken(1)) --> 496
sizeof(v | strided(1)) --> 80 sizeof(v | strided(1) | strided(1)) --> 272 sizeof(v | strided(1) | strided(1) | strided(1)) --> 848 sizeof(v | strided(1) | strided(1) | strided(1) | strided(1)) --> 2576
Wow. I might investigate what this looks like with this alternative range adaptor implementation I've been suggesting (i.e., a lazy implementation rather than the iterator-based implementation presently in Boost.Range). This might be a consequence of failing or not having the necessary infrastructure to take advantage of EBO within the adapted iterators...? - Jeff