<snip>

I'll let Tomas answer for himself fully. But in short:

You used to be able to call member functions on default-constructed iterator_ranges, now you cannot. [Apologies for the hard-coded paths in the following code]:

---

//#include "c:/boost/boost_1_34_0/boost/range/iterator_range.hpp" #include "c:/boost/boost_1_36_0/boost/range/iterator_range.hpp"

#include <vector> #include <iostream> #include <cstddef>

int main() { boost::iterator_range< std::vector<int>::const_iterator> r;

bool b1 = r.empty(); //returns true in 1.34, //asserts in debug 1.35+, undefined behaviour in release std::size_t b2 = r.size(); //returns 0 in 1.34 , //asserts in debug 1.35+, undefined behaviour in release

std::cout << "\n\n" << b1 << b2 << "\n\n"; }

Furthermore, the following code changes have occured: boost::iterator_range<std::vector<int>::const_iterator> r; bool b1 = r.is_singular(); // returns true in 1.34 and debug 1.35. Returns false in release 1.35 Look at this code (copied directly from boost::iterator_range 1.37): bool is_singular() const { #ifndef NDEBUG return singular; #else return false; #endif } Taken from the iterator_range class. IMHO this is broken, the functionality changes between debug and release in 1.35, as well as changing from 1.34 to 1.35. The assertions occur in virtually all the interface functions. Dave

Comments inlined: <snip>

...

Furthermore, the following code changes have occured:

boost::iterator_range<std::vector<int>::const_iterator> r; bool b1 = r.is_singular(); // returns true in 1.34 and debug 1.35. Returns false in release 1.35

If singular means what I think it does(**) I don't think such a function should exist in the public interface. There is no test for a singular pointer or its moral equivalent, an uninitialized int.

(**) well, probably with these kinds of fluctuations in semantics the meaning was never really well-understood by its author

...

Look at this code (copied directly from boost::iterator_range 1.37):

bool is_singular() const { #ifndef NDEBUG return singular; #else return false; #endif }

Taken from the iterator_range class. IMHO this is broken,

I think I'll probably agree with you, but I'd like it in general if statements are accompanied by some rationale. From here I can't be sure _why_ you think it's broken.

Sorry if this wasn't clear - I patched in the code to follow my description of why I thought it was broken - debug and release doing something completely different.

...

the functionality changes between debug and release in 1.35,

Yeah, that's problematic. Such changes should usually be restricted to changes in the expression of undefined behavior.

...

as well as changing from 1.34 to 1.35. The assertions occur in virtually all the interface functions.

My guess is that they're Thorsten's attempt to avoid silent breakage. Whether or not the attempt was well-executed is another matter, but I can understand why he might have done it: he realized that the original design was wrong, and rather than silently letting people get away with using it in ways that were to become illegal, he detected the newly-illegal usage in the only way possible, at runtime.

Newly illegal usage should always be documented as such - and in this instance I'm not convinced it was. Dave

David Abrahams skrev:

on Sat Nov 22 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

...

...

My guess is that they're Thorsten's attempt to avoid silent breakage. Whether or not the attempt was well-executed is another matter, but I can understand why he might have done it: he realized that the original design was wrong, and rather than silently letting people get away with using it in ways that were to become illegal, he detected the newly-illegal usage in the only way possible, at runtime. Newly illegal usage should always be documented as such - and in this instance I'm not convinced it was.

It should be easy enough to verify one way or another.

I'm pretty sure it wasn't documented. But if you do use a non-documented public function, you're on your own. I think it is made public as a work-around. I didn't want to batle with compilers different interpretations of friends and templates. -Thorsten

My guess is that they're Thorsten's attempt to avoid silent breakage. Whether or not the attempt was well-executed is another matter, but I can understand why he might have done it: he realized that the original design was wrong, and rather than silently letting people get away with using it in ways that were to become illegal, he detected the newly-illegal usage in the only way possible, at runtime.

A better way to fix it though, is to introduce another class, instead of breaking an existing one. At this point I don't care what they're called - I think they should be both in boost, even though I think the best way to proceed would be to keep iterator_range as it was before and add a base class which has the new semantics.

on Fri Nov 21 2008, "Scott McMurray" <me22.ca+boost-AT-gmail.com> wrote:

...

On Fri, Nov 21, 2008 at 17:09, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

...

1) Empty ranges are useless and they cannot even be reliably tested for emptiness.

No, empty ranges are useful and can be reliably tested.

...

The empty() function now asserts and the is_singular() function behaves differently between debug and release builds, making it impossible to detect if a range is, in fact, empty.

Yes, singular ranges are almost useless, and cannot be tested for singularity. This seems reasonable, as it's just like ints and iterators. I wouldn't say that a singular range is empty, just as I wouldn't say that an uninitialized int has a value.

That's my inclination, too. Of course, I wouldn't object to another iterator range class that gives the stronger guarantee that it is never singular. There's no point in distinguishing the idea of "singular" from that of "empty" if they are really the same thing, though.

...

I would agree that is_singular should not be available at all in release builds, if it's never useful there. I'd consider it analagous to iterator debugging features, and would think it might be exposition only.

"Exposition only" in the standard is used to give a sense of how something might be implemented, or to say, "here's a working implementation but we're not saying you actually have to do it that way, so long as you give the right observable behavior."

So I don't think "exposition only" is quite the right terminology. Iterator debugging isn't described that way anywhere, AFAIK.

...

...

In addition, this is not documented well and can lead to subtle bugs and undefined behaviour, which will only manifest itself in release builds.

But what semantics for empty *are* documented?

http://www.boost.org/doc/libs/1_37_0/libs/range/doc/boost_range.html#Semanti...) returns boost::begin(x) == boost::end(x)

That's undefined when begin and end return singular iterators,

Correct.

...

so I'm not convinced that the "singular implies empty" behaviour was ever documented. (The "returns" entry for empty is the same for 1_36_0, 1_35_0, 1_34_0, and 1_33_1.)

Hmmm.

Sorry - I'm not convinced this is correct. In 1.35.0 onwards the functionality looked like this: bool empty() const { BOOST_ASSERT( !is_singular() ); return m_Begin == m_End; } In earlier releases the functionality looked like this: bool empty() const { if( singular ) return true; return m_Begin == m_End; } This means that in earlier releases, empty() would return true for singular ranges, in newer releases, debug would assert for singular ranges and be undefined for non-singular ranges. Perhaps the documentation didn't reinforce this fact, but the functionality has most definitely changed. If the documentation didn't follow what the library does, that just points to poor documentation IMHO.

...

...

2) The behaviour is unintuitive. Range is a generalisation of the interface of the std::containers. With this change, containers and ranges can no longer be used in the same code path.

Why would you ever want to pass a default-constructed range to anything?

I will admit that there have been times that I really wished default-constructed iterators all had a value analogous to NULL, that was different from all other values of the same type and yet nonsingular. But that's not how it is, and if you're going to build a range on top of the existing iterator abstraction, I don't see how you can do much better.

Whilst I understand where everyone is coming from in this thread, I'm going to slightly disagree. Again quoting from the source, at the top of iterator_range we see: /*! \file Defines the \c iterator_class and related functions. \c iterator_range is a simple wrapper of iterator pair idiom. It provides a rich subset of Container interface. */ This implies to me that range is trying to look and feel like a container - not like an iterator. I agree that singular iterators (as defined in the standard) are undefined when default constructed; however, no equivalent exists for containers. One of the most useful use cases for iterator_range is where you allow some generic code to accept both iterator_ranges and containers. In this context having some sort of empty range that isn't tied to a specific underlying container is extremely useful. Creating that sort of empty range by default constructing an iterator range was intuitive (at least to me), and actually worked in 1.34 and earlier. Now of course that functionality doesn't work. The new implementation might seem more "pure" if you think of a range as being more like an iterator than a container, but I would argue that it is more like a container. In that context, you really need some sort of empty construct. In general, range sits in a strange middle ground. It is trying to be a clever pair of iterators, and also trying to look and feel like a container. As such it has properties of both. Singularity is something really reserved for iterators, and therefore, I don't think it is necessarily obvious that a range either should or shouldn't have the same iterator like singularity features. Personally, reading this entire thread, I find the proposal by both Tomas Puverle and David Abrahams that 2 versions of iterator_range exist, one that tests for singularity and one that doesn't, by far the most palatable solution. It allows you to have a lean and mean iterator_range if you want to store lots of them in a container (the use case that Dave talks about), it also allows you to have an empty range when you need an iterator_range to look like a container. This could be trivially implemented with inheritance or a policy template. It would be a nice solution to the problem from both directions, and I think it makes the most sense. Dave

on Sat Nov 22 2008, "Pete Bartlett" <pete-AT-pcbartlett.com> wrote:

Thinking of two versions, another point to consider is the existence of sub_range.

Whilst I can see that it seems fairly natural for iterator_range<iterator_t> to have iterator-like behaviour, what about when it is phrased as sub_range<container_t> ? At the moment this is also iterator-like but if you were working from intuition rather than from docs, users could also easily guess it is container-like.

Not I; I don't expect the elements to be copied. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Sat Nov 22 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

...

...

on Fri Nov 21 2008, "Scott McMurray" <me22.ca+boost-AT-gmail.com> wrote:

...

...

so I'm not convinced that the "singular implies empty" behaviour was ever documented. (The "returns" entry for empty is the same for 1_36_0, 1_35_0, 1_34_0, and 1_33_1.)

Hmmm.

Sorry - I'm not convinced this is correct. In 1.35.0 onwards the functionality looked like this:

bool empty() const { BOOST_ASSERT( !is_singular() ); return m_Begin == m_End; }

In earlier releases the functionality looked like this:

bool empty() const { if( singular ) return true;

return m_Begin == m_End; }

This means that in earlier releases, empty() would return true for singular ranges, in newer releases, debug would assert for singular ranges and be undefined for non-singular ranges. Perhaps the documentation didn't reinforce this fact, but the functionality has most definitely changed. If the documentation didn't follow what the library does, that just points to poor documentation IMHO.

The library may indeed have been poorly documented, but I don't see how what you wrote here addresses Scott's statement in any way. You simply cannot count on undocumented behaviors of a library; they are subject to change without notice.

Actually, looking at the quotes from Tom in a separate part of the thread, much of this behaviour was documented.

...

...

...

...

2) The behaviour is unintuitive. Range is a generalisation of the interface of the std::containers. With this change, containers and ranges can no longer be used in the same code path.

Why would you ever want to pass a default-constructed range to anything?

I will admit that there have been times that I really wished default-constructed iterators all had a value analogous to NULL, that was different from all other values of the same type and yet nonsingular. But that's not how it is, and if you're going to build a range on top of the existing iterator abstraction, I don't see how you can do much better.

Whilst I understand where everyone is coming from in this thread, I'm going to slightly disagree. Again quoting from the source,

I doubt I'll find quotes from the source very persuasive, since what you can count on should be determined by the docs.... of course comments in the source are a kind of documentation.

And much of this was also in the docs; although this brings up a separate point. One of the biggest complaints I got when supported boost for my firm was about the documentation. Generally it just isn't up to the same standard as the code. This is something that is gradually being fixed, but hearing the complaints from Java programmers moving to using C++ and Boost, it's very hard to argue against them. Given the quality of the docs, are you surprised when people figure things out from the source?

...

at the top of iterator_range we see:

/*! \file Defines the \c iterator_class and related functions. \c iterator_range is a simple wrapper of iterator pair idiom. It provides a rich subset of Container interface. */

This implies to me that range is trying to look and feel like a container - not like an iterator.

I understand that you drew that conclusion, but IMO it's a huge stretch to claim that a concept that doesn't even exist for containers (singularity) should behave in some container-like way for ranges.

It's not a huge stretch, it's just something that is useful for generic programming. Like everything in programming, if we get hung up on principles, we forget that people have to use this code.

...

I agree that singular iterators (as defined in the standard) are undefined when default constructed;

To be precise, they're not undefined. All singular iterators are alike, regardless of how they're produced (default-constructed or otherwise). They have two defined operations: assignment and destruction.

...

however, no equivalent exists for containers. One of the most useful use cases for iterator_range is where you allow some generic code to accept both iterator_ranges and containers. In this context having some sort of empty range that isn't tied to a specific underlying container is extremely useful.

Yes, it can be.

...

Creating that sort of empty range by default constructing an iterator range was intuitive (at least to me),

Yes, it is intuitive.

...

and actually worked in 1.34 and earlier.

Perhaps. But did the documentation guarantee that it would work?

I believe it did - looking at a quote from Tom elsewhere in the thread.

...

Now of course that functionality doesn't work. The new implementation might seem more "pure" if you think of a range as being more like an iterator than a container, but I would argue that it is more like a container. In that context, you really need some sort of empty construct.

You're free to define models of Range that have a default-constructed empty state. Requiring all models of Range to behave that way is antithetical to the principles of generic programming.

And that isn't what I'm arguing for. Tom has proposed (and I think in your first response you in general agreed) that 2 versions of iterator_range would be the best solution here. I fundamentally agree with that position.

...

In general, range sits in a strange middle ground. It is trying to be a clever pair of iterators, and also trying to look and feel like a container.

I disagree. IMO Range is a pair of iterators You can see that by looking at all of the models that don't behave in any container-like way, e.g. std::pair<int*,int*>, and if you read any book on the STL you'll even see pairs of iterators referred to as "ranges." The key feature of a Container that distinguishes it from a Range is its ownership of the values: when you copy it, the values are copied, too.

One feature of some containers is that. Some containers (not in the STL) don't own the data. But that point isn't really that important. An iterator range is also not an iterator, as well as not being a container.

It's unfortunate that the original implementation of iterator_range set up different expectations for you, but AFAICT the only thing that a Range has in common with a container is that it supplies a begin() and end() that delimit a sequence of elements.

And an empty() and a size() and a random access function operator[], etc. And a comment in the source about being container-like.

...

As such it has properties of both. Singularity is something really reserved for iterators, and therefore, I don't think it is necessarily obvious that a range either should or shouldn't have the same iterator like singularity features.

I would find that argument more compelling if there was a "singular" concept that applied to containers, but there isn't.

This is precisely the sort of discussion that comes about with a concept that sits between 2 other concepts. Iterator_range sits in between iterator and container, which is the whole basis of my argument. How much like an iterator or like a container it is is open to discussion, but it certainly isn't either one of them. Singularity is a feature of iterators, not containers - I agree - but that also shouldn't necessarily drive the design of iterator_range, since an iterator_range isn't an iterator. It is; however, what the library intends it to be. Clearly, in both documentation and code, the library changed it's mind about what an iterator_range was between 1.34 and 1.35 - that's problematic when people have spent a long time coding off the old functionality. Finally, we can discuss detailed semantics of what an iterator_range should be all we like, the core issue here though is that iterator_range changed unannounced between 2 versions of boost. Why can't we come to an agreement that 2 versions of iterator_range would make some sense, and move this discussion forward? Dave

David Abrahams wrote:

on Sat Nov 22 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

...

One of the biggest complaints I got when supported boost for my firm was about the documentation. Generally it just isn't up to the same standard as the code.

I don't see it. It's my experience that the quality of the code and of the documentation are strongly linked; maybe even tautologically linked. If you can't tell what something is supposed to do from reading the docs, how can its implementation possibly be correct in any meaningful sense?

So effectively you are saying that if I am correct in my assertion that boost documentation is frequently poor, then it follows that boost itself is poor. I can't say I agree - in general, even for those libraries where I've suffered poor documentation, I've still been pretty happy with the library (with a few exceptions).

I'm not saying all of Boost is well-documented of course; probably some of the code isn't as good as I'd like. Also, not knowing the speicifics of peoples' complaints, it's hard to understand much about what constitutes "well-documented" from their point of view.

If I get the chance, I may feed back some of the complaints I've heard. Although I haven't had good experiences with this list in the past (this thread being a good example).

...

This is something that is gradually being fixed, but hearing the complaints from Java programmers moving to using C++ and Boost, it's very hard to argue against them. Given the quality of the docs, are you surprised when people figure things out from the source?

I guess you're assuming I'll agree that the docs are lacking.

You don't necessarily need to agree. If the docs in any library are lacking, people will go to the source to figure out how to use it.

...

...

...

at the top of iterator_range we see:

/*! \file Defines the \c iterator_class and related functions. \c iterator_range is a simple wrapper of iterator pair idiom. It provides a rich subset of Container interface. */

This implies to me that range is trying to look and feel like a container - not like an iterator.

I understand that you drew that conclusion, but IMO it's a huge stretch to claim that a concept that doesn't even exist for containers (singularity) should behave in some container-like way for ranges.

It's not a huge stretch, it's just something that is useful for generic programming.

That seems like a non-sequitur. The comment I'm replying to seems to claim that Ranges are container-like, and thus their is_singular function should behave in a container-like way. I still maintain that's a huge stretch: there's just no a priori container-like behavior for a function called is_singular, since there are no singular containers.

At no point have I argued that the is_singular function makes a range more container like. All the other "container-like" functions make range more container like. Like begin(), end(), size(), empty(), operator[], etc. None of these functions exist on a standard library iterator.

...

Like everything in programming, if we get hung up on principles, we forget that people have to use this code.

I'm not hung up on principles, and am fully aware of the importance of usability. Now that the documentation of the old functionality has been revealed, I am also fully confident that there is a library evolution bug here. However, I am not convinced that there is a bug in the current design because it isn't sufficiently container-like, and the argument about is_singular doesn't do anything to bolster that case IMO for the reasons I am stating.

That's not my argument. See my previous comment above.

...

...

Perhaps. But did the documentation guarantee that it would work?

I believe it did - looking at a quote from Tom elsewhere in the thread.

Agreed.

...

...

You're free to define models of Range that have a default-constructed empty state. Requiring all models of Range to behave that way is antithetical to the principles of generic programming.

And that isn't what I'm arguing for.

Maybe not, but the argument that a supposed model of Range is broken because it is not sufficiently container-like is headed in that direction.

Not really, there are plenty of libraries around there, specifically designed for generic programming, where different entities do different things. That's why the standard defined all the different types of iterators for example - random access iterators are different to bi-directional iterators in many ways, but are still called iterators. Just because you have some ranges where default construction implies empty, doesn't mean all of them have to.

...

Tom has proposed (and I think in your first response you in general agreed) that 2 versions of iterator_range would be the best solution here. I fundamentally agree with that position.

Probably -- and unfortunately -- so. However I also feel it's important to temper peoples' expectations about what Range is, and to prevent any moves to make the concept more refined than it should be (and thus rule out many currently-valid models of Range).

...

...

...

In general, range sits in a strange middle ground. It is trying to be a clever pair of iterators, and also trying to look and feel like a container.

I disagree. IMO Range is a pair of iterators You can see that by looking at all of the models that don't behave in any container-like way, e.g. std::pair<int*,int*>, and if you read any book on the STL you'll even see pairs of iterators referred to as "ranges." The key feature of a Container that distinguishes it from a Range is its ownership of the values: when you copy it, the values are copied, too.

One feature of some containers is that. Some containers (not in the STL) don't own the data.

Then you're not talking about the STL container concept (http://www.sgi.com/tech/stl/Container.html) and I don't know what you *are* talking about when you say "container."

When I say container I mean any container that anyone has written. I usually try (although don't always succeed) to distinguish this from the example you are giving above, by talking about standard library containers in that context. I have personally written containers that don't necessarily own data. I don't think containers in general have a single "defining feature". I agree that owning the data is a common feature of many containers, but so is the interface they have. A lot of containers have a superset of the interface we see on boost::iterator_range.

...

But that point isn't really that important.

Sorry, I do think it's important.

We'll be left disagreeing here then.

...

An iterator range is also not an iterator,

Never claimed it was. It's a range (see http://www.sgi.com/tech/stl/Iterators.html)

I know it's a range. Incidentally, the link you have doesn't define a range - it just refers a lot to ranges (and mentions a few properties of them). A range, as I've said before, is something in between a container and an iterator. It has features of both, it also lacks features of both. We shouldn't necessarily design singularity into ranges (which is what seems to have happened at the moment), since as library writers, we are allowed to define whether a particular range has singularity or not.

...

as well as not being a container.

...

It's unfortunate that the original implementation of iterator_range set up different expectations for you, but AFAICT the only thing that a Range has in common with a container is that it supplies a begin() and end() that delimit a sequence of elements.

And an empty() and a size()

Okay, fine, but with a different (free function) syntax.

empty() and size() on an iterator_range are both member functions - so I'm not sure what you mean here. Boost::iterator_range also provides front and back.

...

and a random access function operator[],

random-access iterators provide that too.

Agreed.

...

etc. And a comment in the source about being container-like.

...

...

As such it has properties of both. Singularity is something really reserved for iterators, and therefore, I don't think it is necessarily obvious that a range either should or shouldn't have the same iterator like singularity features.

I would find that argument more compelling if there was a "singular" concept that applied to containers, but there isn't.

This is precisely the sort of discussion that comes about with a concept that sits between 2 other concepts. Iterator_range sits in between iterator and container, which is the whole basis of my argument. How much like an iterator or like a container it is is open to discussion, but it certainly isn't either one of them. Singularity is a feature of iterators, not containers - I agree - but that also shouldn't necessarily drive the design of iterator_range, since an iterator_range isn't an iterator.

Right. Since you want to talk about what should drive the design of iterator_range, I'll tell you what's relevant to this discussion: iterator_range should represent a range built on iterators as its name implies (see the link I provided) and should not make any promises that force it to have space or time overhead beyond what a pair of iterators costs.

I disagree - what should drive the design of iterator_range is what people will find useful. The link you provided uses a range - it doesn't define it. The library is free to define ranges to have the behaviour that is considered useful. In this case different people are asserting that different behaviour is useful - in your case you assert that time and space constraints are important, Tom has shown that valid empty ranges are useful. The most obvious solution to this is 2 versions of the iterator_range class.

Of course, it may be too late for that if people have been relying on the earlier behavior.

...

It is; however, what the library intends it to be.

Hm?

That assertion comes from the comment in the code that says iterator_range is container-like.

...

Clearly, in both documentation and code, the library changed it's mind about what an iterator_range was between 1.34 and 1.35 - that's problematic when people have spent a long time coding off the old functionality.

Agreed. It's not clear to me what the best solution is at this point. Changing the meaning of iterator_range back is going to break some other peoples' code.

Agreed.

...

Finally, we can discuss detailed semantics of what an iterator_range should be all we like, the core issue here though is that iterator_range changed unannounced between 2 versions of boost.

Well, that's certainly a separate issue, and a real problem, and one that needs to be addressed somehow.

Agreed.

...

Why can't we come to an agreement that 2 versions of iterator_range would make some sense, and move this discussion forward?

Because I'm not yet convinced that's the way to go. Maybe the best solution is a preprocessor switch that restores the old behavior.

In that context you would be telling Tom that because he wants the old behaviour in some of his code, he would be banned from using the new behaviour elsewhere in his code? Is that your intention? Dave

on Sun Nov 23 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

David Abrahams wrote:

...

on Sat Nov 22 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

...

One of the biggest complaints I got when supported boost for my firm was about the documentation. Generally it just isn't up to the same standard as the code.

I don't see it. It's my experience that the quality of the code and of the documentation are strongly linked; maybe even tautologically linked. If you can't tell what something is supposed to do from reading the docs, how can its implementation possibly be correct in any meaningful sense?

So effectively you are saying that if I am correct in my assertion that boost documentation is frequently poor, then it follows that boost itself is poor. I can't say I agree - in general, even for those libraries where I've suffered poor documentation, I've still been pretty happy with the library (with a few exceptions).

I guess it's a matter of personal judgement, then.

...

I'm not saying all of Boost is well-documented of course; probably some of the code isn't as good as I'd like. Also, not knowing the speicifics of peoples' complaints, it's hard to understand much about what constitutes "well-documented" from their point of view.

If I get the chance, I may feed back some of the complaints I've heard. Although I haven't had good experiences with this list in the past (this thread being a good example).

What's your problem with this thread? The problem is certainly getting a lot of attention.

...

...

...

...

at the top of iterator_range we see:

/*! \file Defines the \c iterator_class and related functions. \c iterator_range is a simple wrapper of iterator pair idiom. It provides a rich subset of Container interface. */

This implies to me that range is trying to look and feel like a container - not like an iterator.

I understand that you drew that conclusion, but IMO it's a huge stretch to claim that a concept that doesn't even exist for containers (singularity) should behave in some container-like way for ranges.

It's not a huge stretch, it's just something that is useful for generic programming.

That seems like a non-sequitur. The comment I'm replying to seems to claim that Ranges are container-like, and thus their is_singular function should behave in a container-like way. I still maintain that's a huge stretch: there's just no a priori container-like behavior for a function called is_singular, since there are no singular containers.

At no point have I argued that the is_singular function makes a range more container like.

I wasn't claiming you did. I suggest we drop this point as I've been unsuccessful thus far in communicating it and I don't much care whether anybody understands it.

All the other "container-like" functions make range more container like. Like begin(), end(), size(), empty(), operator[], etc. None of these functions exist on a standard library iterator.

No argument. Again, let's drop it unless you're really eager to understand what I was saying.

...

...

...

...

Perhaps. But did the documentation guarantee that it would work?

I believe it did - looking at a quote from Tom elsewhere in the thread.

Agreed.

...

...

You're free to define models of Range that have a default-constructed empty state. Requiring all models of Range to behave that way is antithetical to the principles of generic programming.

And that isn't what I'm arguing for.

Maybe not, but the argument that a supposed model of Range is broken because it is not sufficiently container-like is headed in that direction.

Not really, there are plenty of libraries around there, specifically designed for generic programming, where different entities do different things. That's why the standard defined all the different types of iterators for example - random access iterators are different to bi-directional iterators in many ways, but are still called iterators. Just because you have some ranges where default construction implies empty, doesn't mean all of them have to.

Sure. The argument I was responding to included statements like, "This implies to me that range is trying to look and feel like a container - not like an iterator." and "...if you think of a range as being more like an iterator than a container, but I would argue that it is more like a container." Those (maybe unintentionally) are general statements about the range concept rather than a specific one about iterator_range.

...

...

...

...

In general, range sits in a strange middle ground. It is trying to be a clever pair of iterators, and also trying to look and feel like a container.

I disagree. IMO Range is a pair of iterators You can see that by looking at all of the models that don't behave in any container-like way, e.g. std::pair<int*,int*>, and if you read any book on the STL you'll even see pairs of iterators referred to as "ranges." The key feature of a Container that distinguishes it from a Range is its ownership of the values: when you copy it, the values are copied, too.

One feature of some containers is that. Some containers (not in the STL) don't own the data.

Then you're not talking about the STL container concept (http://www.sgi.com/tech/stl/Container.html) and I don't know what you *are* talking about when you say "container."

When I say container I mean any container that anyone has written.

In other words, it's a term without a solid definition?

I usually try (although don't always succeed) to distinguish this from the example you are giving above, by talking about standard library containers in that context.

I'm not talking about standard library containers, in the sense of vector, list, deque, etc. I'm talking about the standard library definition of what it means to be a container.

I have personally written containers that don't necessarily own data.

What makes them "containers," then? What do you consider container-ness to be, if it doesn't include element ownership?

I don't think containers in general have a single "defining feature". I agree that owning the data is a common feature of many containers, but so is the interface they have. A lot of containers have a superset of the interface we see on boost::iterator_range.

If you're going to argue about peoples' expectations for a category of types based on its similarity to some notion of "container," you at least have to make reference to some commonly-understood definition of the term. I chose the one in the standard, because that's what we all have access to.

...

...

An iterator range is also not an iterator,

Never claimed it was. It's a range (see http://www.sgi.com/tech/stl/Iterators.html)

I know it's a range. Incidentally, the link you have doesn't define a range - it just refers a lot to ranges (and mentions a few properties of them).

This is a definition of "range of iterators." Most algorithms are expressed not in terms of a single iterator but in terms of a range of iterators [1]; the notation [first, last) refers to all of the iterators from first up to, but not including, last. [2] Note that a range may be empty, i.e. first and last may be the same iterator. Note also that if there are n iterators in a range, then the notation [first, last) represents n+1 positions. This is crucial: algorithms that operate on n things frequently require n+1 positions. Linear search, for example (find) must be able to return some value to indicate that the search was unsuccessful.

A range, as I've said before, is something in between a container and an iterator. It has features of both, it also lacks features of both. We shouldn't necessarily design singularity into ranges (which is what seems to have happened at the moment), since as library writers, we are allowed to define whether a particular range has singularity or not.

On that point we agree.

...

...

as well as not being a container.

...

It's unfortunate that the original implementation of iterator_range set up different expectations for you, but AFAICT the only thing that a Range has in common with a container is that it supplies a begin() and end() that delimit a sequence of elements.

And an empty() and a size()

Okay, fine, but with a different (free function) syntax.

empty() and size() on an iterator_range are both member functions - so I'm not sure what you mean here. Boost::iterator_range also provides front and back.

Yes, but now you've switched backfrom talking about the range concept to talking about a specific model of that concept.

...

Right. Since you want to talk about what should drive the design of iterator_range, I'll tell you what's relevant to this discussion: iterator_range should represent a range built on iterators as its name implies (see the link I provided) and should not make any promises that force it to have space or time overhead beyond what a pair of iterators costs.

I disagree - what should drive the design of iterator_range is what people will find useful.

I think there are any number of designs people might find useful, including ones that deviate substantially from either one under discussion. I am saying that we have an unfortunate precedent to contend with, so we may or may not be able to supply the ideal design under that name, but if we were starting from scratch, a Boost component called iterator_range that contains two iterators delimiting a range of elements should meet peoples' expectations by following the design principles of generic programming, and the extra bool simply clashes with those principles.

The link you provided uses a range - it doesn't define it. The library is free to define ranges to have the behaviour that is considered useful.

I disagree, and for the same reason I argued that the filesystem library mustn't have a function called "base_name" that meant something fundamentally different from Posix's base_name. In our domain, "range" has an accepted meaning.

In this case different people are asserting that different behaviour is useful - in your case you assert that time and space constraints are important, Tom has shown that valid empty ranges are useful.

I assert that both are useful.

The most obvious solution to this is 2 versions of the iterator_range class.

Yes, if Tom needs the old behavior, he should have it. The question is, how should he get it? He could write it himself, or Boost could provide it in any number of ways. I think if I were the Range library maintainer, I would feel responsible enough for my initial design mistake to have made this transition a lot easier for my users, and I'd be bending over backwards to make up for the breakage. I would also be very reluctant to maintain the old design as anything more than a deprecated feature, though, because --- in my opinion --- it is fundamentally flawed. That said, it's not up to me as long as we're going to respect Thorsten's right to maintain his own library.

...

Of course, it may be too late for that if people have been relying on the earlier behavior.

...

It is; however, what the library intends it to be.

Hm?

That assertion comes from the comment in the code that says iterator_range is container-like.

Apparently the "intentions of the library" are a bit like the shifting sands.

...

...

Finally, we can discuss detailed semantics of what an iterator_range should be all we like, the core issue here though is that iterator_range changed unannounced between 2 versions of boost.

Well, that's certainly a separate issue, and a real problem, and one that needs to be addressed somehow.

Agreed.

...

...

Why can't we come to an agreement that 2 versions of iterator_range would make some sense, and move this discussion forward?

Because I'm not yet convinced that's the way to go. Maybe the best solution is a preprocessor switch that restores the old behavior.

In that context you would be telling Tom that because he wants the old behaviour in some of his code, he would be banned from using the new behaviour elsewhere in his code? Is that your intention?

Whoa there, Mr. Prosecutor! I'm not intending to ban anything; I am merely exploring the solution space. Incidentally, Tom cannot have both behaviors under the same name (including namespace) without either violating the ODR or introducing still more runtime overhead, thread safety problems, and other global state evil. If he is going to use both behaviors, I'd prefer he use the new behavior under the existing name and use a different name elsewhere. If that was indeed a viable option for him (though I expect it's not), the workaround would be easy: provide his own old_iterator_range -- Dave Abrahams BoostPro Computing http://www.boostpro.com

I usually try (although don't always succeed) to distinguish this from

...

...

the example you are giving above, by talking about standard library containers in that context.

I'm not talking about standard library containers, in the sense of vector, list, deque, etc. I'm talking about the standard library definition of what it means to be a container.

In the context of the standard library. The standard library doesn't have a monopoly on the term container.

But it does define the *concept* of a 'Container' (with a capital 'C') which, in turn defines the syntax, semantics, and guarantees thereof within the context of the standard library. The same goes for Iterator and its refinements. Concepts are also going to be part of C++0x language so there should be no imprecision or ambiguity when talking about a Container. The *notion* of a 'container' (with a lowercase 'c') can be substantially broader and mean different things to different people at different times. Unfortunately, it's hard to build reliable structures on shifting sand. These concepts (Container, Iterator, etc.) in the standard are the foundations of Boost.Range and every other generic library in Boost. Concepts are the language of generic libraries, and you can't expect to have meaningful discussions about them if you refuse to learn the language. Are you surprised? That's the original topic of this thread, and the key

point. Again - this is precisely why I stopped posting to boost development a long time back - a simple problem becomes a lengthy philosophical discussion. I'm not talking about anything complex here. I've read the docs, I've looked at the code, I've used the code. Somewhere along the way we seem to now need exact definitions of iterator, container, range, and a whole host of other things in order to figure out how to resolve an undocumented breaking change.

To a degree, I think this is an unfortunate side-effect of building and maintaining generic libraries. If you don't get it exactly right the first time (both code and docs), then discussion of solutions absolutely must concern the definitions of concepts. Unfortunately, problems with Iterators (and by extension Ranges) tend to be lengthy and detailed since they're such fundamental concepts and can have far reaching impact. I'm not particularly fond of the is_singular() solution with preprocessed code, but It does appear to result in correct behavior when compiled for release - so I'm definitely not in favor of rolling out those changes. Other solutions have been proposed. Andrew Sutton andrew.n.sutton@gmail.com

on Sun Nov 23 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

Response inlined - thread snipped where we agree :)

David Abrahams wrote:

...

What's your problem with this thread? The problem is certainly getting a lot of attention.

My main issue with this thread is not the attention it received - it's the extent to which a discussion about a breaking change to a library has turned into a philosophical discussion. Really the discussion about what a range is should have taken place at review time for the library, now we should just be able to confirm or not that a breaking change has happened, and either fix it or not.

I think if you look back at the thread you'll see that you introduced the first philosophical statements.

...

Sure. The argument I was responding to included statements like,

"This implies to me that range is trying to look and feel like a container - not like an iterator."

and

"...if you think of a range as being more like an iterator than a container, but I would argue that it is more like a container."

Those (maybe unintentionally) are general statements about the range concept rather than a specific one about iterator_range.

This is all based on the following - the first line in the *current* docs for boost.range.

"A Range is a concept similar to the STL Container concept."

The same pre-amble goes on to talk about the differences between a range and a container; for example it says:

"In particular, a Range does not necessarily

* own the elements that can be accessed through it, * have copy semantics, "

That sounds familiar. In other words, a container has copy semantics and owns its elements.

It doesn't say that a range doesn't have a concept of emptiness,

But a range *does* have a concept of emptiness!

or that it has properties of an iterator. This is why I have been contending that ranges are more container like than they are iterator like. I'm not making this up - it's what the docs tell me.

I understand that you feel the docs gave you reason to think that, but IMO drawing that conclusion from the docs you cite is a stretch at best. But you don't want to talk about philosophy, so let's drop it.

...

...

I don't think containers in general have a single "defining feature". I agree that owning the data is a common feature of many containers, but so is the interface they have. A lot of containers have a superset of the interface we see on boost::iterator_range.

If you're going to argue about peoples' expectations for a category of types based on its similarity to some notion of "container," you at least have to make reference to some commonly-understood definition of the term. I chose the one in the standard, because that's what we all have access to.

Ok then - based on the contents of the docs here: http://www.boost.org/doc/libs/1_37_0/libs/range/doc/range.html what does that page mean? I'm basing the similarity on what the docs tell me to expect - are the docs wrong?

To the extent to which they imply that every default-constructed Range should be testable for emptiness, yes. But frankly, I don't see such an implication in that text except as a stretch. You have just as much reason to expect all Ranges to have begin() and end() members (they don't, in general) and Allocator template arguments (ditto), and insert() members, etc. And now we're back to philosophy. So, sorry.

...

...

...

...

...

It's unfortunate that the original implementation of iterator_range set up different expectations for you, but AFAICT the only thing that a Range has in common with a container is that it supplies a begin() and end() that delimit a sequence of elements.

And an empty() and a size()

Okay, fine, but with a different (free function) syntax.

empty() and size() on an iterator_range are both member functions - so I'm not sure what you mean here. Boost::iterator_range also provides front and back.

Yes, but now you've switched backfrom talking about the range concept to talking about a specific model of that concept.

Are you surprised?

Not insofar as you and I seem to have very different ideas about what constitutes a valid argument here.

That's the original topic of this thread, and the key point. Again - this is precisely why I stopped posting to boost development a long time back - a simple problem becomes a lengthy philosophical discussion.

If you want to stick with iterator_range I'm more than happy to. "Philosophy" in this conversation exists only because you made assertions about the Range concept that I can't accept.

I'm not talking about anything complex here. I've read the docs, I've looked at the code, I've used the code. Somewhere along the way we seem to now need exact definitions of iterator, container, range, and a whole host of other things in order to figure out how to resolve an undocumented breaking change.

Absolutely. I can't even begin to imagine how to resolve questions of whether the thing is broken in the first place without precise definitions. Sorry, I know I'm very literal-minded, but I don't know another way to thing these issues through.

...

...

The most obvious solution to this is 2 versions of the iterator_range class.

Yes, if Tom needs the old behavior, he should have it. The question is, how should he get it? He could write it himself, or Boost could provide it in any number of ways.

I think if I were the Range library maintainer, I would feel responsible enough for my initial design mistake to have made this transition a lot easier for my users, and I'd be bending over backwards to make up for the breakage. I would also be very reluctant to maintain the old design as anything more than a deprecated feature, though, because --- in my opinion --- it is fundamentally flawed.

So by that statement, you are saying that Tom's use case, which relied on the old behaviour, is fundamentally flawed?

No.

...

...

...

...

It is; however, what the library intends it to be.

Hm?

That assertion comes from the comment in the code that says iterator_range is container-like.

Apparently the "intentions of the library" are a bit like the shifting sands.

Why then do the docs still assert that a range is container-like? That's the 1.37 docs, not the 1.34 docs.

I can't account for the way the thing is documented. Do you really think that one of the two designs in question was inconsistent with Thorsten's intentions when he wrote it?

...

Incidentally, Tom cannot have both behaviors under the same name (including namespace) without either violating the ODR or introducing still more runtime overhead, thread safety problems, and other global state evil. If he is going to use both behaviors, I'd prefer he use the new behavior under the existing name and use a different name elsewhere. If that was indeed a viable option for him (though I expect it's not), the workaround would be easy: provide his own old_iterator_range

I realise that - which was why I believe 2 versions under different names is by far and away the best way to resolve this. From my perspective I don't much care what they are each called, but I do strongly believe (in the absence of a better solution) that 2 versions is the way forward.

Okay, but should they both be in Boost, now that the damage is done? I'm not sure that's the right answer either. And, by the way, I'm not saying it's the wrong answer; I'm saying I haven't been convinced in either direction. If Tom isn't prepared to accept using boost::old_iterator_range instead of boost::iterator_range, we have to break a bunch of other peoples' code, which seems worse to me. Then both groups of users will have been disrupted. If Tom *is* prepared to use boost::old_iterator_range, IMO it may as well be tom::iterator_range: we don't have to have this component in Boost at all, except as an example along with the change notes that tell you how to write a component with the old behavior if you need it. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Sun Nov 23 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:

David Abraham[sic] wrote: <big snip - cos I can't be bothered with this thread any more>

...

Okay, but should they both be in Boost, now that the damage is done? I'm not sure that's the right answer either. And, by the way, I'm not saying it's the wrong answer; I'm saying I haven't been convinced in either direction.

If Tom isn't prepared to accept using boost::old_iterator_range instead of boost::iterator_range, we have to break a bunch of other peoples' code, which seems worse to me. Then both groups of users will have been disrupted. If Tom *is* prepared to use boost::old_iterator_range, IMO it may as well be tom::iterator_range: we don't have to have this component in Boost at all, except as an example along with the change notes that tell you how to write a component with the old behavior if you need it.

It is absolutely clear from this post that you are missing the entire point. I've tried to cover the point from about 3 different directions, and each time you get bogged down in something off-topic.

Too bad, and just when I thought we were getting down to brass tacks. Well, maybe Tom would care to weigh in on these issues; I'm still making an effort to figure out how best to resolve them. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Sat Nov 22 2008, Tomas Puverle <Tomas.Puverle-AT-morganstanley.com> wrote:

...

The library may indeed have been poorly documented, but I don't see how what you wrote here addresses Scott's statement in any way. You simply cannot count on undocumented behaviors of a library; they are subject to change without notice.

The behaviour WAS documented, as I've stated in a different thread: It's right there at the top of the iterator_range class if the pre 1.35 docs.

Agreed, now that I've seen your quote.

However, I have to say I don't like what you're doing - I feel like you're trying to prove that what we're doing is actually wrong in some way.

I'm sorry you feel that way. I don't intend that at all.

We're looking for a solution to real problem.

Agreed.

Forget for a second about whether it or it documented. The question is - what can be done?

Agreed again. However, whether it was documented or not has a huge effect on my opinion about what can be done.

...

...

at the top of iterator_range we see:

/*! \file Defines the \c iterator_class and related functions. \c iterator_range is a simple wrapper of iterator pair idiom. It provides a rich subset of Container interface. */

This implies to me that range is trying to look and feel like a container - not like an iterator.

I understand that you drew that conclusion, but IMO it's a huge stretch to claim that a concept that doesn't even exist for containers (singularity) should behave in some container-like way for ranges.

Remember that our problem is not with is_singular(),

A lot of arguments have been flying around this thread, some about is_singular and others about the fundamental nature of the Range concept. I understand those are not *your* concern.

it is with empty(). is_singular() is just an implementatin artifact. The behaviour we care about is whether or not a default constructed iterator_range should be empty(), in line with standard containers.

Understood.

...

...

I agree that singular iterators (as defined in the standard) are undefined when default constructed;

To be precise, they're not undefined. All singular iterators are alike, regardless of how they're produced (default-constructed or otherwise). They have two defined operations: assignment and destruction.

But not all default constucted iterators are singular.

True, but in generic code (e.g. inside of iterator_range), in the absence of any further information, you have to treat them that way.

...

You're free to define models of Range that have a default-constructed empty state. Requiring all models of Range to behave that way is antithetical to the principles of generic programming.

We certainly agree on this. We're not proposing that we have a single iterator_range class that fits all purposes, again as I've stated in several posts.

I understand that. Others' arguments seemed to be headed that way.

...

but AFAICT the only thing that a Range has in common with a container is that it supplies a begin() and end() that delimit a sequence of elements.

Actually, the similarity is much stronger than that:

iterator begin() const; iterator end() const; size_type size() const; bool empty() const;

On the Range concept those are free functions, not members.

Unfortunately I don't have my standard at hand (it's at work) but IIRC all of the are part of the "Container requirements".

Yes, but they're not part of the "Range requirements." If they were, pair<int*,int*> couldn't be a Range. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On Sat, Nov 22, 2008 at 13:12, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

...

But what semantics for empty *are* documented?

http://www.boost.org/doc/libs/1_37_0/libs/range/doc/boost_range.html empty(x) returns boost::begin(x) == boost::end(x)

Prior to 1.35, the iterator_range<> documentation read the following:

"Recall that many default constructed iterators are singular and hence can only be assigned, but not compared or incremented or anything. However, if one creates a default constructed iterator_range, then one can still call all its member functions. This means that the iterator_range will still be usable in many contexts even though the iterators underneath are not. "

Does this answer your question?

Thank you; I hadn't noticed that. However, the documentation for both says that "The intention of the iterator_range class is to encapsulate two iterators so they fulfill the Forward Range concept," given a template argument that matches the ForwardTraversalIterator concept. The problem, then, is that neither the 1.34 nor 1.35 implementation satisfies the requirements for the Forward Range concept given an iterator such as the following, despite it being, as far as I can tell, a perfectly legal Forward Traversal Iterator: template <typename T> struct contrived_iterator { shared_ptr<T> x; bool dirty; contrived_iterator() : x(new T()), dirty() {} contrived_iterator(contrived_iterator const &i) : x(i.x), dirty(i.dirty) {} contrived_iterator &operator=(contrived_iterator const &i) { x = i.x; dirty = i.dirty; } contrived_iterator &operator++() { dirty = true; } contrived_iterator operator++(int) { contrived_iterator i = *this; ++*this; return i; } bool operator==(contrived_iterator i) { return dirty || i.dirty; } bool operator!=(contrived_iterator i) { return !(*this == i); } T &operator*() { return *x; } T const &operator*() { return *x; } typedef int difference_type; typedef T value_type typedef T& reference; } template <typename T> struct iterator_traversal<contrived_iterator<T> > { typedef forward_traversal_tag type; } It seems there's an assumption that a default-constructed iterator is either singular or past-the-end, but I saw no such requirement in either the standard or the "New iterator concepts" document.

On 2008-11-23, David Abrahams <dave-AT-boostpro.com> wrote:

on Sat Nov 22 2008, "Scott McMurray" <me22.ca+boost-AT-gmail.com> wrote:

...

It seems there's an assumption that a default-constructed iterator is either singular or past-the-end, but I saw no such requirement in either the standard or the "New iterator concepts" document.

Where was such an assumption made? I don't see it.

In both the old iterator_range implementation (which assumes that a range between default constructed iterators is empty) and the new one (which assumes that all default constructed iterators are singular). The sentence in 1.34 "This means that the iterator_range will still be usable in many contexts even though the iterators underneath are not" seems to descripe the assumption that 2 default-constructed iterators can never delimit a valid range. (This discussion does treat the previously-mentioned sentence, along with "Recall that many default constructed iterators are singular" as documentation that the begin and end iterators are default-constructed, which is backed up by the source, analogy to std::pair, and the fact that since my iterator type has a default constructor, pointless gymnastics would be required for it to not be used.) As I can find no requirement that prevents two default-constructed iterators from delimiting a valid range, I think that neither implementation properly models the range concept (under the presumption, justified above, that a default-constructed iterator_range contains default-constructed iterators).

Finally, it answers mine. Now the question is: whose code will remain broken? Those who used iterator_range prior to 1.35 and relied on this feature, or those who used it after 1.35 and expect not to incur space and time overhead to support it?

At this point I have no expectations about the outcome of this, especially given Thorsten's response that "he's too busy to deal with this". I'm going to have to go through my code and change it and remove all uses of iterator_range. Perhaps it's better that we go forward and invest the effort in 1) Making sure that some of the Range concepts get fixed 2) See if we can come up with a way to prevent changes like this in the future

David Abrahams skrev:

on Mon Nov 24 2008, "Tomas Puverle" <Tomas.Puverle-AT-morganstanley.com> wrote:

If you really like the abstraction, there's no reason you can't use toms::iterator_range instead of the one in Boost. That would surely induce far less churn and instability in your codebase.

...

Perhaps it's better that we go forward and invest the effort in

1) Making sure that some of the Range concepts get fixed

What is broken? -Thorsten

Daniel Walker skrev:

On Tue, Nov 25, 2008 at 4:50 PM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:

...

David Abrahams skrev:

...

on Mon Nov 24 2008, "Tomas Puverle" <Tomas.Puverle-AT-morganstanley.com> wrote: If you really like the abstraction, there's no reason you can't use toms::iterator_range instead of the one in Boost. That would surely induce far less churn and instability in your codebase.

...

Perhaps it's better that we go forward and invest the effort in

1) Making sure that some of the Range concepts get fixed What is broken?

I tried to give an explanation last night. If I wasn't clear or if you disagree on some points, just say so, and we can discuss it.

I getting lost in this thread. And yes, I definitely disagree that the old range concepts where better than the new ones. -Thorsten

On Tue, Nov 25, 2008 at 10:20 PM, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:492C7337.5090800@dezide.com...

...

David Abrahams skrev:

...

on Mon Nov 24 2008, "Tomas Puverle" <Tomas.Puverle-AT-morganstanley.com> wrote:

...

If you really like the abstraction, there's no reason you can't use toms::iterator_range instead of the one in Boost. That would surely induce far less churn and instability in your codebase.

...

Perhaps it's better that we go forward and invest the effort in

1) Making sure that some of the Range concepts get fixed

What is broken?

...

From my personal perspective, I would like to see some of the assertions removed from iterator_range. I believe that in principle you and others agree with this point.

It seems some other people on this thread have also expressed their concern about how the concepts defined during the review have changed.

When we use the term "concept", we're referring to a specific convention for abstraction in the generic programming paradigm. See the introduction to the original STL. http://www.sgi.com/tech/stl/stl_introduction.html However, my favorite introduction of all time for generic programming is Chapter 2 of Jeremy Siek, et. al. The Boost Graph Library. That book changed my life. :) Daniel Walker

"Tomas Puverle" <Tomas.Puverle@morganstanley.com> wrote in message news:ggii1a$e44$1@ger.gmane.org...

I would have used a capitalised "Concept" to refer to what you describe.

Ah, I just noticed the inconsistency in my post.

On 2008-11-22, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

Why would you ever want to create an empty container?

To add stuff to it, but you can't do that with a range.

Let me give you an example of one of the ways I use empty ranges, which I've found extremely useful:

typedef iterator_range<SomeIterator> MyRange;

class MyIterator: public boost::iterator_facade<... MyRange > { private: MyRange dereference() const { //if the internal representation is point to a valid entry (say //in a file) return a set of valid iterators, otherwise return //an empty range if (...) { return MyRange(....); } else { return MyRange(); } } };

typedef iterator_range<MyIterator> Range2;

Range2 r1(...); Range2 r2(...);

Now one can work with these ranges recursively, because of the overloaded operators of boost::iterator_range, e.g.

r1 == r2; or r1 != r2;

I can also write generic code which can take list of vectors of iterators or perhaps can just read the data directly from the file representation or what not.

Now, there is no way to reproduce this behaviour with the new implementation.

What sequence do those iterators iterate? I don't see what it could be that wouldn't let you get at least the PTE iterator even if the representation doesn't "point to a valid entry", so you ought to be able to just return MyRange(end, end); And the iterator range constructor is a perfectly legal container construct too, so it doesn't break your desire to use containers in the same code path. So I don't see how there "no way to reproduce" the behaviour, at least in the outline of code you provided.

<snip>

With such a notion this, indeed, is a rather useless component. I have to agree with Tomas and others in one of their points: one of the major advantages or ranges before pairs of iterators is that they attempt to reproduce containers as far as possible. Yes, in general default-constructed iterators are singular and they cannot be used reliably. However, not all iterators behave that way. Pointers, for example, are NULL on default-initialization (which is used in the default constructor of the iterator_range class). I can well have my own iterators that are default-constructible and allow comparison in this state. And I don't understand why an iterator range of these iterators suddenly restricts me from being able to compare these iterators in empty(), for example.

The documentation of the iterator_range states for several functions, such as size() and operator[], that these functions depend on the iterator nature. I believe, empty() could just do the same - rely on the ability to compare iterators, even default-initialized ones. Of course, this should be clearly stated in the docs.

Whilst the documentation might say that, the implementation of size() and operator[] depends on underlying iterator nature, the reality is that both these functions will assert on a singular range.

If it was just me, default-constructing iterators and ranges shouldn't even

...

be allowed (unless that is sufficient that initialize it). A range that is not properly initialized is not in any usable state. It's not an empty range, it's more like a pointer to somewhere random. Just don't try to use it. If Boost.Range used to allow it, that was a bug; good thing it is now fixed.

...

As for is_singular, that function shouldn't be exposed to the public.

I agree that is_singular is evil. More over, I am sure that asserts based on it are also evil. My point is: don't try to make iterator_range more clever than it is stated in the docs (that is, a pair of iterators with a forwarding interface of a container).

This is the crux of the issue. What is an iterator_range trying to be. If it is supposed to be nothing more than a glorified pair of iterators, then so be it. Allow singular ranges, but don't assert on them. If on the other hand it wants to make a pair of iterators look like a container, then there pretty much has to be a way to create an empty range without having to tie that empty range to a specific container. The glorified pair will only ever get used as a glorified pair. A pair of iterators looking like a container though is far more useful in generic programming - so that would be my personal proposal. At the moment, iterator_range is trying to be both things, and failing at both as well. Dave

On Sat, Nov 22, 2008 at 09:13, Andrey Semashev <andrey.semashev@gmail.com> wrote:

With such a notion this, indeed, is a rather useless component. I have to agree with Tomas and others in one of their points: one of the major advantages or ranges before pairs of iterators is that they attempt to reproduce containers as far as possible. Yes, in general default-constructed iterators are singular and they cannot be used reliably. However, not all iterators behave that way. Pointers, for example, are NULL on default-initialization (which is used in the default constructor of the iterator_range class). I can well have my own iterators that are default-constructible and allow comparison in this state. And I don't understand why an iterator range of these iterators suddenly restricts me from being able to compare these iterators in empty(), for example.

I think you just raised the most important point in this thread. iterator_range<ostream_iterator<string> >() is not singular, yet 1.37 will say it is, so that's clearly wrong. But yet, the old way is also bad. iterator_range<string::iterator>() was singular, with its empty() returning true, while the conceptually equilavent iterator_range<string::iterator>(string::iterator(), string::iterator()), which is also singular, has an empty() that invokes UB. Also, what if I write a random_number_iterator, a forward iterator which returns a different random number after each increment? Then iterator_range<random_number_iterator>() is again non-singular, and it has an infinite size (operator== would always be false), so the empty() for the range should *not* return false. An iterator_range is just that, and trying to hide what it is seems doomed to failure.

The documentation of the iterator_range states for several functions, such as size() and operator[], that these functions depend on the iterator nature. I believe, empty() could just do the same - rely on the ability to compare iterators, even default-initialized ones. Of course, this should be clearly stated in the docs.

That is, as mentioned, precisely what has been stated in the docs since at least 1_33_1.

On Sat, Nov 22, 2008 at 12:13, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:

iterator_range being a generic tool, it wants to maintain the invariants which are necessary to make it work whatever its parameters are, even if those invariants happen not to be necessary for some parameters.

I'm not that much of a fan of the invariant, though, since the problematic values are undetectable and the approximation has both false negatives and false positives. The invariants can be checked reliably at the iterator level -- and are, with iterator debugging enabled -- which seems sufficient to me. On Sat, Nov 22, 2008 at 12:20, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:

Scott McMurray wrote:

...

Also, what if I write a random_number_iterator, a forward iterator which returns a different random number after each increment? Then iterator_range<random_number_iterator>() is again non-singular, and it has an infinite size (operator== would always be false)

In that case, it might be clearer to write something like

iterator_range<random_number_iterator> r(random_number_iterator(), random_number_iterator());

Here, it is explicitly initialized and thus iterator_range should know that this is not a singular range.

That is quite a pain, of course.

...

, so the empty() for the range should *not* return false.

I'm not sure I'm following. The way you wrote it, it should abort, and the way I wrote it, it should return false.

I meant "should not" as in "inconsistent with what the iterators would say", but you're right, I was relying on implementation detail rather than documented behaviour. Having a default-constructed iterator_range not be useful as anything other than the lhs of an assignment does seem reasonable, but I can't see any justification for making iterator_range<I>() any different from iterator_range<I>(I(), I()), since it's neither POD nor aggregate. Similarly, pair<A,B>() is specified as "Initializes its members as if implemented: pair() : first(T1()), second(T2()) {}", giving it the same value as pair<A,B>(A(), B()). (Not explicitly initializing the members seems without gain, since initializing a POD has trivial cost, and everything else will get constructed anyways.) Changing tacks slightly, has anyone yet elaborated the use case for the old behaviour? A default-constructed container is useful because you can add elements to it, but since a default-constructed iterator range can never be manipulated in a useful fashion, why would someone ever want to pass or store it at all?

Andrey Semashev wrote:

Yes, in general default-constructed iterators are singular and they cannot be used reliably. However, not all iterators behave that way. Pointers, for example, are NULL on default-initialization (which is used in the default constructor of the iterator_range class). I can well have my own iterators that are default-constructible and allow comparison in this state. And I don't understand why an iterator range of these iterators suddenly restricts me from being able to compare these iterators in empty(), for example.

Iterators where default-construction leads to a valid past-the-end iterator for all sequences are a fairly special case of iterators, even if they happen to be quite common. However, that is certainly not guaranteed by the iterator concepts. Therefore, when you deal with iterators in a generic way, you should not assume such a thing. iterator_range being a generic tool, it wants to maintain the invariants which are necessary to make it work whatever its parameters are, even if those invariants happen not to be necessary for some parameters. Maybe if your iterators are so peculiar and you want to be able to rely on that property, you should use something else than iterator_range which is designed for all iterators.

Please cite who you're quoting. See the discussion policy at http://www.boost.org/community/policy.html. On Sat, Nov 22, 2008 at 1:58 PM, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

...

However, that is certainly not guaranteed by the iterator concepts. Therefore, when you deal with iterators in a generic way, you should not assume such a thing.

And we're not.

...

iterator_range being a generic tool, it wants to maintain the invariants which are necessary to make it work whatever its parameters are, even if those invariants happen not to be necessary for some parameters.

But as a "generic" tool, iterator_range is now assuming too much and breaking existing code. Also, currently iterator_range is close to me wanting to say that it doesn't really maintain any invariants, IMHO.

I was about to suggest that if you want to build a generic library that uses ranges, stick to the Range concepts (http://tinyurl.com/5z56n2) and avoid tying yourself to types generated from iterator_range. Tight bundling always causes problems like this. With concepts all of the constraints on a type can be encoded in a concept checking class and automatically verified at compile time (and of course proposed C++0x language extensions could make this even easer/cleaner). Users can rely on the concepts being implemented, and authors can use concept checks to make sure their implementations meet user expectations. Unfortunately, the Range concept checks appear to have been changed about a year ago, apparently in response to the changes in iterator_range. As far as I can tell from looking at the svn history, when iterator_range failed to meet the Range concepts, rather than changing iterator_range, the concept checks were gutted. If you don't pass the test, change the test?!!! :( This entirely defeats the purpose of concepts, which obviously are meant to be independent of particular types, and is contrary to the entire paradigm of generic programming. So, though I wish I could, I can't suggest that you use Range concepts rather than iterator_range, because both were changed without being properly announced or vetted. That's frustrating. Perhaps a procedural solution that could avert this problem in the future is to quarantine the test cases. Authors can maintain commit privileges to their libraries on trunk, but only a select group of independent guardians have commit privileges to the test cases. That way there is a guarantee that libraries pass the same tests from one release to another. If an author would like to make a change that would break a test case, he or she would need to present the change to the list and submit a patch to the test case sentinels. This would be a fairly simple quality assurance protocol: engineers aren't allowed to do their own QA. Daniel Walker

On Sun, Nov 23, 2008 at 1:55 AM, David Abrahams <dave@boostpro.com> wrote:

on Sat Nov 22 2008, "Daniel Walker" <daniel.j.walker-AT-gmail.com> wrote:

...

As far as I can tell from looking at the svn history, when iterator_range failed to meet the Range concepts, rather than changing iterator_range, the concept checks were gutted. If you don't pass the test, change the test?!!! :(

Let's not get ahead of ourselves. That's exactly the right thing to do when the test is wrong. The question is, was it? That depends on the documentation. Did the test match the specification before and/or after this modification? Or, was the specification modified too?

I don't mean to overreact. However, the specification was modified too. The Range concept was defined in the review, and I see no reason that it should have changed. Daniel Walker

on Sun Nov 23 2008, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:

...

Unfortunately, the Range concept checks appear to have been changed about a year ago, apparently in response to the changes in iterator_range. As far as I can tell from looking at the svn history, when iterator_range failed to meet the Range concepts, rather than changing iterator_range,

Is an iterator_range not a range? I don't recall anything like this. Was I the one that changed the test?

You have the tools to answer those questions yourself. It's all there in Trac and SVN. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

I was about to suggest that if you want to build a generic library that uses ranges, stick to the Range concepts (http://tinyurl.com/5z56n2) and avoid tying yourself to types generated from iterator_range. Tight bundling always causes problems like this. With concepts all of the constraints on a type can be encoded in a concept checking class and automatically verified at compile time (and of course proposed C++0x language extensions could make this even easer/cleaner). Users can rely on the concepts being implemented, and authors can use concept checks to make sure their implementations meet user expectations.

Daniel, Thank you for the insightful post. I will change my code to be more in conformance with the range concept rather than with the iterator_range implementation. However, this will still not solve the problem for my users. Even if I make the relevant changes and my users still pass in a default constructed iterator_range, boost::begin() == boost::end() will not work, because iterator_range asserts on the range not being singular in almost all of the member functions. This means that I need to erradicate this class altogether.

If you don't pass the test, change the test?!!!

I am sorry to hear this is the case. Tom

David Abrahams skrev:

on Sat Nov 22 2008, Tomas Puverle <Tomas.Puverle-AT-morganstanley.com> wrote:

...

Anyway, I think a lot of people on this forum are missing the point: I'm not claiming that the old behaviour is in some way better or worse. I am saying the following: 1) Is the behavioural change too much of a diversion from previous expected (documented) functionality that the new change is in fact a defect

We haven't established that, IMO. Unless I missed it, nobody has shown where in the old documentation it was stated that a default-constructed iterator range is empty.

Well, I think the docs stated that if( rng ) was valid, and conversion to bool was based on .empty(). -Thorsten

Andrey Semashev skrev:

On Sat, Nov 22, 2008 at 8:13 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:

...

Andrey Semashev wrote:

Yes, in general default-constructed

...

iterators are singular and they cannot be used reliably. However, not all iterators behave that way. Pointers, for example, are NULL on default-initialization (which is used in the default constructor of the iterator_range class). I can well have my own iterators that are default-constructible and allow comparison in this state. And I don't understand why an iterator range of these iterators suddenly restricts me from being able to compare these iterators in empty(), for example.

Iterators where default-construction leads to a valid past-the-end iterator for all sequences are a fairly special case of iterators, even if they happen to be quite common. However, that is certainly not guaranteed by the iterator concepts. Therefore, when you deal with iterators in a generic way, you should not assume such a thing.

iterator_range being a generic tool, it wants to maintain the invariants which are necessary to make it work whatever its parameters are, even if those invariants happen not to be necessary for some parameters.

I think this is the case when excessive invariant checking does more harm than good. I hate to reiterate, but I think it should be up to user whether to rely on the ability to compare default-constructed iterators or not. The library, being as you rightfully say, a generic tool, must not impose excessive restrictions on the use model of the underlying iterators. Right now the library does so, which basically cancels a considerable set of valid use cases. I would say, it contradicts the term "a generic tool".

Your views have some merits, and I think we should have a more conservative debugging policy in iterator_range. -Thorsten

on Sat Nov 22 2008, Tomas Puverle <Tomas.Puverle-AT-morganstanley.com> wrote:

...

I agree that is_singular is evil.

To be more precise, the new behaviour is evil. Previously it was fine, even though it wasn't very useful.

I disagree. Such a function doesn't make any sense and shouldn't exist. You can't tell at runtime whether an iterator_range is singular for the same reasons that you can't tell whether an iterator is singular. If iterator_range didn't have any constructors that allowed you to pass iterators, it would be a different matter. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On Sun, Nov 23, 2008 at 1:49 AM, David Abrahams <dave@boostpro.com> wrote: <snip>

Frankly, you don't even need to be that explicit: just write the semantics of empty as

begin(r) == end(r)

That was the definition of the semantics of empty(r) before it was (inexplicably) removed from the Range concept. Daniel Walker

Scott McMurray skrev:

On Sun, Nov 23, 2008 at 13:06, Daniel Walker <daniel.j.walker@gmail.com> wrote:

...

On Sun, Nov 23, 2008 at 1:49 AM, David Abrahams <dave@boostpro.com> wrote: <snip>

...

Frankly, you don't even need to be that explicit: just write the semantics of empty as

begin(r) == end(r) That was the definition of the semantics of empty(r) before it was (inexplicably) removed from the Range concept.

And despite not being mentioned in the concept (http://www.boost.org/doc/libs/1_37_0/libs/range/doc/range.html#single_pass_r... and boost/range/concepts.hpp), it's still in the Semantics section of the "Synopsis and Reference" page (http://www.boost.org/doc/libs/1_37_0/libs/range/doc/boost_range.html#Semanti...).

In fact, why does iterator_range have a public empty() method at all? It's modelling a range, so boost::empty will use boost::begin and boost::end, completely ignoring iterator_range<T>::empty. Making ir.empty() just sugar for boost::empty(ir) seems the only reasonable way to avoid consistency problems. (Removing the member altogether would be nice, but it's probably too late for that.)

We are going way to much in detail here. All these matters where settled at the initial design and review. I belive it was for convinience. I suggest that we direct our time at other topics. -Thorsten

Tomas Puverle wrote:

...

It's not an empty range, it's more like a pointer to somewhere random.

This is not the case - there are plenty of iterators which have valid semantics when default constructed, including some in the standard library.

Sure there are, but that's irrelevant. The standard doesn't require iterators that have been constructed to be in a valid state, and that's all there is to it. It's not a matter of choice of design. It's a matter of following the standard. In your specific case it's not a problem, but iterator_range aims at being generic. As I said, if it was just me, I would have designed the iterator concepts differently so as *not* to require default construction, which standard iterator concepts do, and that is bringing the singular states in.

First off, Tom, please cite who you're quoting. It makes the discussion difficult to follow when you respond to quotes that aren't attributed to anyone. Please follow the discussion guidelines at http://www.boost.org/community/policy.html, in particular the section "Use a Readable Quotation Style." On Sat, Nov 22, 2008 at 9:45 PM, Tomas Puverle <Tomas.Puverle@morganstanley.com> wrote:

...

Sure there are, but that's irrelevant. The standard doesn't require iterators that have been constructed to be in a valid state, and that's all there is to it.

By the same logic, we should never be able to build any compound types which have any members which could potentially be in some invalid state.

The point is that iterators are default constructible and may therefore exist in an invalid state. The probable of maintaining the validity of an iterator, or a pointer, is tricky. Actually, this is one of the motivations for ranges; they help maintain the validity of iterators by organizing them in pairs that define the boundaries of a traversable range. The Range concept documentation has always stated that a valid range x is one where boost::end(x) is reachable from boost::begin(x). In your use case, as far as I understand, you do not necessarily have a valid range. <snip>

I gave a demonstrable use case, which, IMHO, is actually very powerful thanks to the generality of iterator_range. Not one of the opponents of what we're saying has come up with a single suggestion of how the current iterator_range can meet my needs or justify why it should be acceptable for boost to change documented behaviour without any notice.

As for undocumented changes, that's unjustifiable. (I'm also aggravated about the changes to the Range concepts, and I wish I had been paying closer attention, 'cause I would have protested.) As for your needs, we're trying to help, if you're willing to listen. I disagree with you that iterator_range is a particularly generic solution. I would suggest writing for the Range concepts in general. As for the actual implementation of a range, I much prefer std::pair, and I would recommend that you use it. If you're code was written specifically for iterator_range, you'll have some searching and replacing and sed and awking ;) and possibly other refactoring to do. If you're code was written generically for any Range, then the transition from iterator_range to std::pair should be trivial and painless. That's one of the points of generic programming: Don't be bound to a particular class or type, be free! :) I'm sorry for any discrepancies between iterator_range documentation and the Range concept documentation and the actual iterator_range implementation in any given release. Apparently, there were changes that probably should not have been made. However, it sounds to me like you want to create invalid ranges. So in that respect, Boost.Range is not broken, your use case is. Now, interestingly, one might ask for a new feature - a function to test if a range is valid. But since range validity is defined in terms of one iterator being reachable from another, range validity testing is actually an instance of the halting problem! So, I guess we can't really implement that one. ;) Anyway, I'm not sure how to untie this knot. I guess we need Thorsten's input. Daniel Walker

On Sun, Nov 23, 2008 at 02:45:48AM +0000, Tomas Puverle wrote:

If instead of arguing about minutia we could actually talk about a real design, we could make progress. At the moment all of the useful brain power is spent on trying to prove that what we're doing is wrong. Your problem domain is different from mine. Physicists call the imaginary number 'j'. In mathematics, we refer to it as 'i'. Does it make one or the other wrong?

Hey! Please don't slander the Physicists: it's Engineers who use 'j'. :-) -S

David Abrahams wrote:

on Sat Nov 22 2008, Tomas Puverle <Tomas.Puverle-AT-morganstanley.com> wrote:

...

At the moment all of the useful brain power is spent on trying to prove that what we're doing is wrong.

Maybe my brain power is useless, but so far it is being spent on trying to get someone to show me the specification that guarantees the old behavior will work. For me, that is still at the heart of the matter.

Correct me if I'm wrong, but hasn't this post been in the thread for almost a day now: Tomas Puverle wrote:

Scott,

...

But what semantics for empty *are* documented?

http://www.boost.org/doc/libs/1_37_0/libs/range/doc/boost_range.html #Semantics empty(x) returns boost::begin(x) == boost::end(x)

Prior to 1.35, the iterator_range<> documentation read the following:

"Recall that many default constructed iterators are singular and hence can only be assigned, but not compared or incremented or anything. However, if one creates a default constructed iterator_range, then one can still call all its member functions. This means that the iterator_range will still be usable in many contexts even though the iterators underneath are not. "

And doesn't this answer your question about whether documented behaviour has changed? Dave

on Sun Nov 23 2008, "Daniel James" <daniel_james-AT-fmail.co.uk> wrote:

2008/11/23 Tomas Puverle <Tomas.Puverle@morganstanley.com>:

...

Hence we need two different implementations. That is exactly what I proposed.

There's no reason that they both have to be in boost. Boost range should let you use your own range class.

That is another option. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Mon Nov 24 2008, "Tomas Puverle" <Tomas.Puverle-AT-morganstanley.com> wrote:

...

There's no reason that they both have to be in boost. Boost range should let you use your own range class.

And you're absolutely right. Having said that, it's not inconceivable that others may have been relying on the same behavour. That's one of the things this discussion was about.

Yes. The library maintainer ought to do something to help those people, by providing the old behavior in code somewhere (even if that code only appears in docs). -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On Wed, Nov 26, 2008 at 4:46 AM, Scott McMurray <me22.ca+boost@gmail.com> wrote:

On Tue, Nov 25, 2008 at 13:31, David Abrahams <dave@boostpro.com> wrote:

...

on Mon Nov 24 2008, "Tomas Puverle" <Tomas.Puverle-AT-morganstanley.com> wrote:

...

...

There's no reason that they both have to be in boost. Boost range should let you use your own range class.

And you're absolutely right. Having said that, it's not inconceivable that others may have been relying on the same behavour. That's one of the things this discussion was about.

Yes. The library maintainer ought to do something to help those people, by providing the old behavior in code somewhere (even if that code only appears in docs).

How about providing code something like this (thanks to Boost.Iterator):

template <class Iter> class nonsingular_default : public boost::iterator_adaptor< node_iter<Value> // Derived , Iter // Base > { private: bool is_default_constructed;

public: node_iter() : node_iter::iterator_adaptor_(), is_default_constructed(true) {}

explicit node_iter(Iter i) : node_iter::iterator_adaptor_(i), is_default_constructed(false) {}

private: friend class boost::iterator_core_access; bool equal(nonsingular_default i) { if (is_default_constructed && i.is_default_constructed) { return true; } if (!is_default_constructed && !i.is_default_constructed) { return base == i.base(); } return false; } };

[ i think you want to change all node_iter to nonsingular_default ]

Allowing recovery of the old semantics using

iterator_range< nonsingular_default<I> >

(at least for Tomas Puverle's use case.)

This, of course, depends on the asserts getting removed, but that behaviour is also replicable using the same technique.

I do not think you can even copy a singular iterator (and at least libstdc++ will assert in debug mode), so I do not think that the above will let you have safe default constructable iterators (in fact I think this is a problem even with the old range implementation, a good reason to have changed it). boost.optional might help, but I have this feeling that it will hinder optimizations. -- gpd

On Wed, Nov 26, 2008 at 09:15, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:

Giovanni Piero Deretta skrev:

...

On Wed, Nov 26, 2008 at 4:46 AM, Scott McMurray <me22.ca+boost@gmail.com> wrote:

...

[...]

[ i think you want to change all node_iter to nonsingular_default ]

Yes, dumb copy-paste mistake on my part.

...

I do not think you can even copy a singular iterator (and at least libstdc++ will assert in debug mode),

Right. you can't even copy a singular iterator (not portably, at least).

Another good point. I think this works, as the iterator_adaptor's copy ctr is never called: template <class Iter> class nonsingular_default : public boost::iterator_adaptor< nonsingular_default<Value> // Derived , Iter // Base > { private: bool is_default_constructed; public: nonsingular_default() : nonsingular_default::iterator_adaptor_(), is_default_constructed(true) {} nonsingular_default(Iter const &i) : nonsingular_default::iterator_adaptor_(i), is_default_constructed(false) {} nonsingular_default(nonsingular_default const &i) { *this = i; } nonsingular_default &operator=(nonsingular_default const &i) { is_default_constructed = i.is_default_constructed; if (!is_default_constructed) { base_reference() = i.base(); } } private: friend class boost::iterator_core_access; bool equal(nonsingular_default const &i) { if (is_default_constructed && i.is_default_constructed) { return true; } if (!is_default_constructed && !i.is_default_constructed) { return base == i.base(); } return false; } };

Tomas Puverle wrote:

By the same logic, we should never be able to build any compound types which have any members which could potentially be in some invalid state.

Obviously, any compound type with a member in an invalid state is in an invalid state too.

When I default construct a string class, it has some internal representation with a char pointer, which doesn't necessarily point to any valid memory.

The default-constructed state of a string class is a perfectly valid state, that's totally unrelated. You can perform most operations on a an empty string.

I really have not idea what you're referring to. There is nothing about iterator_range in the C++ standard. We can choose to define the semantics any way we choose.

iterator_range works with standard iterators. So if the standard says the iterators cannot be used, the range cannot be used either. Hence the asserts.

...

In your specific case it's not a problem, but iterator_range aims at being generic.

Generic means that it's applicable to a wide variety of types. Cutting out support for a subset of valid types for no good reason = less generic.

It's not cutting out specific ranges, it just requires you to explicitly initialize all ranges before using them, to ensure you're not doing something wrong. It might prove verbose however, and that could be a valid reason not to do that checking altogether.

This, what is happening now on this mail topic is very typical of this mailing list and this is what makes it so hard to try be involved. By now, I could have written ten range implementations and fixed all of my code. Instead, I'm spending time trying to get this (IMHO important) component somehow integrated back into boost.

What I've been saying is purely my opinion and doesn't represent that of Boost or anything. It's not like I'm part of Boost anyway. The one that will make the decision of changing Boost.Range to reflect your desires or not is most likely the maintainer of that library and my opinion on this matter matters little. I was just trying to say I personally thought those asserts had their use. Getting rid of asserts is a perfectly valid choice, but reverting to the old behaviour certainly isn't IMHO.

AMDG Tomas Puverle wrote:

...

The default-constructed state of a string class is a perfectly valid state, that's totally unrelated.

My point was that a default constructed range may be in a perfectly valid state, too, depending on its iterators.

Indeed. I think that a default constructed iterator_range should be usable and empty iff default constructed iterators are non-singular and equal. This effectively pushes dealing with default construction onto the iterators. IMO, this is more consistent than the old behavior, where a default constructed iterator_range was "empty", but r.begin() == r.end() could be undefined behavior. In Christ, Steven Watanabe

Andrew Sutton skrev:

...

My point was that a default constructed range may be in a perfectly valid

...

state, too, depending on its iterators.

Indeed. I think that a default constructed iterator_range should be usable and empty iff default constructed iterators are non-singular and equal. This effectively pushes dealing with default construction onto the iterators. IMO, this is more consistent than the old behavior, where a default constructed iterator_range was "empty", but r.begin() == r.end() could be undefined behavior.

I think this is the right answer (and pretty well argued by now). The behavior of the iterator_range should "inherit" (is there a better word for this?) its semantics from the underlying iterator. To do otherwise would impose requirements on iterators that may not (easily) support those semantics, making the concept less generic (as in represents fewer possible implementations).

Well, it is fairly easy to remove some of the debug-checks from the code. Do I understand you correctly in that you want them all removed? -Thorsten

Andrew, On Tue, Nov 25, 2008 at 4:07 PM, Andrew Sutton <andrew.n.sutton@gmail.com>wrote:

...

I think this is the right answer (and pretty well argued by now). The

...

behavior of the iterator_range should "inherit" (is there a better word for this?) its semantics from the underlying iterator. To do otherwise would impose requirements on iterators that may not (easily) support those semantics, making the concept less generic (as in represents fewer possible implementations).

Well, it is fairly easy to remove some of the debug-checks from the code. Do I understand you correctly in that you want them all removed?

No! Definitely no. As I understand it, those debug checks are kind of playing the role of axiomatic preconditions in debug mode, so they're actually reinforcing the correct behavior. I think.

Yes! Definately yes ;-) The checks have all manner of false-positives. They aren't axiomatic preconditions that should apply for all or even most iterator types used with iterator_range. The iterator_range simply cannot reliably determine if the iterator is invalid due to it being singular. Singularity is a property of iterators. If singulairity requires additional debugging infrastructure it should be added to a debugging iterator framework. It's far too restricting upon the typical and valid usages of iterator_range.

I think from a previous post I was considering a kind of checked iterator_range that could provide additional diagnostics in debug mode - something akin to the STLPort checked iterators. Providing something like that as a compile-time replacement for iterator_range would free that class up to be as lean as possible and sans preprocessor. Completely outside the scope of the discussion... sorry.

Andrew Sutton andrew.n.sutton@gmail.com

Neil Groves

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thorsten Ottosen wrote:

Andrew Sutton skrev:

...

I think this is the right answer (and pretty well argued by now). The behavior of the iterator_range should "inherit" (is there a better word for this?) its semantics from the underlying iterator. To do otherwise would impose requirements on iterators that may not (easily) support those semantics, making the concept less generic (as in represents fewer possible implementations).

Well, it is fairly easy to remove some of the debug-checks from the code. Do I understand you correctly in that you want them all removed?

I think, at least these members should not have asserts: empty() begin() end() and maybe: equal() operator== operator!= But I'm less confident about the latter three.

On Sun, Nov 23, 2008 at 1:37 AM, David Abrahams <dave@boostpro.com> wrote:

on Sat Nov 22 2008, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:

...

iterator_range (which is nothing more than a fancy std::pair, I never found the use of it myself)

It's a bit less redundant to write the type name, since both members of the pair have to be the same, and it has a little more communicative power, since after all pair<Iter,Iter> doesn't have to represent a range; it has only been retroactively adapted to model Range when p.second is reachable from p.first.

So, not completely useless, IMO.

This is a good point, and I'm a big fan of expressivity and self-documenting code. iterator_range is a much better name for a range than "pair", and it's also good that iterator_range has only one template parameter for the type of iterator. I guess what turned me off of it was its bulkiness with all those methods sticking out of it in every direction. Daniel Walker

On Sun, Nov 23, 2008 at 2:46 PM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:

Daniel Walker skrev:

...

On Sun, Nov 23, 2008 at 1:37 AM, David Abrahams <dave@boostpro.com> wrote:

...

on Sat Nov 22 2008, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:

...

iterator_range (which is nothing more than a fancy std::pair, I never found the use of it myself)

It's a bit less redundant to write the type name, since both members of the pair have to be the same, and it has a little more communicative power, since after all pair<Iter,Iter> doesn't have to represent a range; it has only been retroactively adapted to model Range when p.second is reachable from p.first.

So, not completely useless, IMO.

This is a good point, and I'm a big fan of expressivity and self-documenting code. iterator_range is a much better name for a range than "pair", and it's also good that iterator_range has only one template parameter for the type of iterator. I guess what turned me off of it was its bulkiness with all those methods sticking out of it in every direction.

Daniel,

Wrt. the new range concepts, then I only changed those so they would match the new concept requirements, after the second version of the library took its form. I think that was the only sensible thing to do.

best regards

-Thorsten

In the documentation, the Range concept definitions (which I believe were reviewed for release in 1.32) included a requirement for empty(r) that I believe would help clear up some of the problems that initiated this discussion. This requirement is independent of any particular class including the classes supplied by Boost.Range, that's the beauty of concepts. Stripping the concepts in response to changes in iterator_range undermines the whole abstraction and has made Boost.Range less usable, IMHO. I think the boost formal review process lead to a higher quality of library concept definitions in release 1.32 than those available in the current release. Daniel Walker

We could introduce boost::range<iterator> with the old behavior, deriving from boost::iterator_range<iterator>. In this case, I need someone to submit code and tests and documentation (I'm way to busy to do that).

-Thorsten

In the future, please be mindful of making and documenting your changes. I am sure you can appreciate we are all very busy. Tom