Mostafa wrote:

any_iterator<...> it_any = my_mapped_type_iterator_adaptor(map_instance.begin());

How would I go about doing that with ranges?

Something like this (untested): boost::iterator_range< any_iterator<...> > range_any = boost::make_iterator_range( map_instance | boost::adaptors::map_values ); Simply boost::iterator_range< any_iterator<...> > range_any = map_instance | boost::adaptors::map_values; might work just as well, but I am not sure.

Thanks, -Mostafa

HTH, Gevorg

On Sat, 15 May 2010 14:59:25 -0700, Neil Groves <neil@grovescomputing.com> wrote:

Indeed there were a number of older library designs that used runtime polymorphism with iterator hierarchies that ultimately discovered that this approach was vastly inferior to the generic iterator approach of the standard library. However I can certainly see that this is useful across module interface boundaries for small collections etc.

I've found any_iterator to be indispensible in defining generic, decoupled interfaces. Previously, I had to resort to writing my own GOF-like runtime polymorphic iterators. As for cost, that's a matter of perspective driven by business needs. For example, I've used interface-level polymorphic-iterators with ~100k sized collections on 3-year old medium-priced desktops that ran under 3 seconds (if even that), a result which was quite acceptable for the product's target audience. Not that I don't appreciate your insights, I do, however for people unfamiliar with this topic who may be reading this I think it would be quite helpful to put into perspective the costs of using runtime polymorphic iterators. Ultimately, it's up to the programmer to run their own metrics and determine if it meshes with their business needs. (Personal rant: another reason for this response is that too often I see C++ programmers, especially the older crowd, sacrificing generic/decoupled design out of cost concerns, without first putting into perspective what those costs entail, ie, a) what is the range of the measured cost and b) is it acceptable?)

You can use the boost::iterator_range type and the boost::make_iterator_range function to help create a range from iterators.

I'm reading the Boost.Range documentation and I have a number of questions/comments, listed below: 1) The documentation is a great reference. It's a frustrating as an introduction. It's a frustrating as a tutorial. (Please don't take this the wrong way, or personally.) 2) What exactly is the definition of Range? Is it any type that meets the requirements of any one of the following concepts: Single Pass Range Concept, Forward Range Concept, Bidirectional Range Concept, Random Access Range Concept? If so, can you explicitly and prominently declare that in the documentation? The documentation here: http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/over... , really beats around the bush. It describes some attributes of Range, but doesn't quite define it. Additionally, right next to this definition, can you give examples of some common types which match the definition of Range? (Some are alluded to in the Introduction.) 3) Why is the library named Range when it seems that only iterator_range actually encompasses a range of iterators. Am I missing something here? 4) Having both range_iterator and iterator_range is just confusing. Are you trying to purposefully make me dyslexic? ;) 5) Put "Notice that the above functions should always be called with qualification (boost::) to prevent unintended Argument Dependent Lookup (ADL)." prominently at the *top* of the following document, preferably with some sort of advisory icon. http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/con... 6) Same thing as 5) for the following comment "If an instance of iterator_range is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end)." in the following page: http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/uti... It's just too easy to miss these important preconditions if they're not blatantly in your face. 7) The use of operator| is jarring. Especially in the introductory examples without any textual introduction. (Yes, I did read the motivation behind it, but it still doesn't jive with me. Maybe it's all those years of math/cs indoctrination.) I think programmers won't freak out as much if the introductory examples used function composition first then showed the alternative with operator|. See page: http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/ada...

However for cases like these where you would like to have some syntactic sugar I would write this:

Finally, thanks for providing a usable any_range example. It's very gracious of you. Thanks, -Mostafa

On Sun, 16 May 2010 03:06:07 -0700, Neil Groves <neil@grovescomputing.com> wrote:

I have acknowledged on this mailing list that a tutorial would make the Boost.Range documentation better. My schedule only just allowed a good, correct implementation with reference documentation for 1.43. Delaying for another release to fit in a tutorial would not have been the right decision. I apologise for the steeper than optimal learning curve.

No problem. Let me clarify that I am approaching the documentation/library from three perspectives: as an individual programmer, as an employee of company X, and as a supervisor with technological decision making responsibilities. From a an individual programmer's perspective, I can figure out how to use the library from the documentation, and if I find the syntax a little funny, I can live with that, same goes for the naming convention. But it's mostly from an employee's perspective and a supervisor's perspective that I am approaching this. Why? Because I think that Boost can make my life easier at work, and I would like to be able to use it. And the only way I would be able to use it would be to sell it to my boss and my peers. On technical grounds, it's a pretty easy sell. On usability, it's harder. What's a crucial factor in making usability easier, the documentation. Hence my comments/criticisms/suggestions on it (with no guarantee that any of it is actually valid, but, which is given in good faith).

Of course if you wish to contribute to the tutorial that would be very welcome.

Let me see what I can come up with.

...

2) What exactly is the definition of Range? Is it any type that meets the requirements of any one of the following concepts: Single Pass Range Concept, Forward Range Concept, Bidirectional Range Concept, Random Access Range Concept?

I normally speak of a Range as something that models the SinglePassRangeConcept or above.

...

If so, can you explicitly and prominently declare that in the documentation? The documentation here: http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/over..., really beats around the bush. It describes some attributes of Range, but doesn't quite define it.

The above link is to an overview of the Range concept. From my perspective it therefore, by definition, does not fully describe the Range Concepts. Specific improvements or at an example improvement would be more applicable feedback. The technical explanations for each of the range concepts is provided here:

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/sing... http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/forw... http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/bidi... http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/concepts/rand...

Specifically I would suggest putting the definition of 2) in the Overview. (I take from your response that that is indeed the definition of Range.)

...

3) Why is the library named Range when it seems that only iterator_range actually encompasses a range of iterators. Am I missing something here?

I don't understand this point. The library is called Range because it defines Range types, Range algorithms and Range adaptors. This has been one of the less controversial naming decisions.

Maybe if Range was defined early on I wouldn't have this question. The reason I bring it up is because the word Range, in the absence of any definition, immediately conjures up something along the lines of [x, y) or some variation thereof. But, from my reading of the documentation a range can be any stl container, an array, a std::string, a pair of iterators, etc... And when I see the word Range, the first thing that pops to mind isn't exactly a container or an array, I have an easier time associating iterator_range with Range.

...

4) Having both range_iterator and iterator_range is just confusing. Are you trying to purposefully make me dyslexic? ;)

I appreciate that this can be a little confusing but coming up with a better name for range_iterator is very tricky, and there is actually a formulaic naming convention applied to the metafunctions where range_ is prefixed to the type that is extracted by the metafunction. iterator_range is the most sensible name for a range of iterators. That is the rationale, and of course it is too late to be flexible on this issue. This was not listed as a concern by anyone during the review process IIRC.

No problem. I'm approaching this with no expectations on my part. My only goal is to raise usability flags where I think there exists some.

...

5) Put "Notice that the above functions should always be called with qualification (boost::) to prevent unintended Argument Dependent Lookup (ADL)." prominently at the *top* of the following document, preferably with some sort of advisory icon.

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/con...

No! I respectfully disagree that it would be an improvement. Accidental ADL lookup for non-member functions is a general C++ issue, the only reason for the clarification requirement in the reference documentation is to ensure that it is understood that not using ADL will not prohibit the invocation of the extension mechanism. The extension mechanism is carefully designed to support extension even when the user is making fully qualified calls.

I probably should alter the documentation to clarify my intent however.

One of the hardest jobs of being a maintainer is saying 'No', but if I put to the top everything that each user considered the most important I would simply be shuffling the docs perpetually.

Just to clarify, as a general rule should the client always use boost:: ? If so, then let me explain my rationale. I'm working on a laptop with 1280 x 800 resolution. When I first land on the above website I see a table of functions that's cut off at "const_begin(x)". Okay, I mentally tell myself, it's just a table of functions and their explanations, good for reference, don't need it now, then press the "->" at the top of the page and keep reading on. Because the "->" appears on both the top of the page and the bottom, I'm not forced to scroll down to go to the next page, hence I miss whatever info is at the bottom. (This may very well be a bad habit on my part, but I don't think I'm the only one.) Even if I return to this page to lookup something, what I'll most likely be interested in can still be found without scrolling down enough to see that there exists non-tabular information at the bottom of the page.

This was carefully chosen language that actually resembles the documentation that the original author of any_iterator provides. A rant appears to be an inappropriate response.

Maybe I shouldn't have used the word rant; and hopefully I haven't dissuaded you from providing future insights/advice. Thanks, -Mostafa

Mostafa skrev:

On Sun, 16 May 2010 03:06:07 -0700, Neil Groves <neil@grovescomputing.com> wrote:

...

...

Of course if you wish to contribute to the tutorial that would be very welcome.

Let me see what I can come up with.

Attached is a sketch of my proposed tutorial. Please comment/amend as appropriate.

"Informally, a Range is any type that can be associated with a collection of objects of some arbitrary type or types. Hence, a Range is a concept, like that of an STL Container. The motivation for the Range concept is that there are many useful Container-like types that do not meet the full requirements of Container, and many algorithms that can be written with this reduced set of requirements" - I would refrase the first sentence to "Informally, a Range is any type that can be associated with a collection of objects and which allows one to iterate over all the elements of the collection." - I would refrase the third sentence as "The motivation for the Range concept is that is provides a simpler and more expressive encapsulation of a half-open iterator range [begin,end) that is normally used in interfaces of containers and in specification of generic algorithms." -Thorsten

Am 15.05.2010 23:59, schrieb Neil Groves:

I feel compelled to suggest caution at performing type-erasure at an iterator level. This would often be the wrong place to incur runtime overhead for compiler-time advantage. The deterioration in locality of data, the worsening of cache-line performance and reduced in-lining capability would often make this a poor design choice. Indeed there were a number of older library designs that used runtime polymorphism with iterator hierarchies that ultimately discovered that this approach was vastly inferior to the generic iterator approach of the standard library. However I can certainly see that this is useful across module interface boundaries for small collections etc. [snip] Thank you for an interesting problem. I do wonder if it might be a good idea to provide a type-erasure Boost.Range adaptor so that you could write something like:

map_instance | boost::adaptors::map_values | boost::adaptors::type_erased<int, boost::forward_traversal_tag>

Is there much interest in using the library in this way? I'm happy to implement this if there is.

Yes, please. I would love to see a type-erased range and a type-erasing adaptor - exactly for the reason you pointed out. -Christopher

I have a working range implementation, but I find it very difficult to write

an output iterator for use with std::copy, because the updated output iterator is returned by value, and I cannot prove statically that the returned iterator is indeed of the same type as the local one.

As a bit of a workaround,

vector<int> v1 = { 1, 2, 3 }; vector<int> v2; output_iterator<int> o = back_inserter(v2); o = copy(v1.begin(), v2.end(), o);

works, but the operator= is expensive and we lose all the optimization potential from knowing the actual iterator type in the caller as well.

Instead of type erasing the output iterator have you considered type-erasure applied to a 'sink' concept? Alternatively I often find I can use the new algorithm extensions such as boost/range/algorithm_ext/push_back.hpp so that I need not know the output type. I imagine there are many valid use-cases where a type-erased output iterator is a good design choice considering the state of libraries and frameworks at the moment. I thought that the algorithm_ext information might be useful to you now, but if you do need type erasure then perhaps you might like to work on refining a 'Sink' concept. I've got a little bit too much on to investigate and refine this concept in a very short time frame otherwise I would leap to it straight away of course.

Simon

Regards, Neil Groves