A forward iterator need not be default-constructible
== Problem == The following code fails to compile: #include <vector> #include <boost/iterator/transform_iterator.hpp> #include <boost/range/algorithm.hpp> #include <boost/range/adaptor/transformed.hpp> static inline void trigger (::std:: vector < int > const &p_v) { /* i: p_v [i] + 0 >= 0 */ ::boost:: lower_bound (p_v | ::boost:: adaptors:: transformed (::std:: bind1st (::std:: plus < int > (), 0)), 0); } Details: See [[#Evidence]]. == Workaround == The following definition causes the code to compile successfully, as of GNU C++ 4.6: #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0 Disadvantages and risks: * The macro BOOST_RANGE_ENABLE_CONCEPT_ASSERT is undocumented. * It disables concept checking altogether, which may be a good thing or a bad thing, depending on your needs. The official motivation for concept checking is that it makes error messages more readable; in this particular case, I am not convinced. == Background == TL;DR: If all you can say is that such an iterator does not meet the requirements imposed by the standard, I am not interested. If you are willing not to treat the standard as the ultimate and unquestionable oracle, you may read on :-) The standard C++ library defined iterators to serve and additional task to serve as abstract pointers that may be singular, i.e. not corresponding to any object and distinct from any other iterator. To this end, the standard requires that interators may be constructed out of thin air, and that such an iterator is singular. This requirement is only useful iterators that do not correspond to containers like the standard input stream iterator which you can use to find something in it, and even then the end iterator, which is singular, is created explicitly by the calling code and not by library code. Requiring conformance to this particular requirement in Boost is counterproductive, as it causes perfectly valid and obvious code to fail to compile for no reason at all except for respecting the letter of the standard. == Conclusions == 1. The macro BOOST_RANGE_ENABLE_CONCEPT_ASSERT should be documented, as it is necessary to keep the concepts BS at bay. 2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding. == Note == I believe that it is possible to design algorithms so that they do not construct singular iterators anywhere; moreover, I believe that doing so would be beneficial to the library implementation, as evidenced in GNU libstdc++ Bug #45488. (My similar report against Plauger’s library was declined by Microsoft, which means I have to use a replacement algorithm fixed by myself.) == Evidence == g++ -g doit.cpp -o doit In file included from doit.cpp:4:0: /usr/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = std::binder1st<std::plus<int>
, Iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >, Reference = boost::use_default, Value = boost::use_default]’: /usr/include/boost/concept_check.hpp:130:10: instantiated from ‘boost::DefaultConstructible<TT>::~DefaultConstructible() [with TT = boost::transform_iterator<std::binder1st<std::plus<int> >, __gnu_cxx::__normal_iterator<const int*, std::vector<int> >, boost::use_default, boost::use_default>]’ /usr/include/boost/range/concepts.hpp:148:16: instantiated from ‘static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::range_detail::ForwardIteratorConcept< boost::transform_iterator<std::binder1st<std::plus<int> >, __gnu_cxx::__normal_iterator<const int*, std::vector<int> >, boost::use_default, boost::use_default> >]’ /usr/include/boost/range/concepts.hpp:264:1: instantiated from ‘boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > >’ /usr/include/boost/concept/detail/has_constraints.hpp:42:5: instantiated from ‘const bool boost::concepts::not_satisfied<boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > > >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:45:31: instantiated from ‘boost::concepts::not_satisfied<boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > > >’ /usr/include/boost/mpl/if.hpp:67:11: instantiated from ‘boost::mpl::if_ <boost::concepts::not_satisfied<boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > > >, boost::concepts::constraint<boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > > >, boost::concepts::requirement<boost::concepts::failed************ boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > >::************> >’ /usr/include/boost/concept/detail/general.hpp:50:8: instantiated from ‘boost::concepts::requirement_<void (*)(boost::ForwardRangeConcept<const boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> > >)>’ /usr/include/boost/range/algorithm/lower_bound.hpp:45:1: instantiated from ‘typename boost::range_iterator<const ForwardRange>::type boost::range::lower_bound(const ForwardRange&, Value) [with ForwardRange = boost::range_detail::transform_range<std::binder1st<std::plus<int> >, const std::vector<int> >, Value = int, typename boost::range_iterator<const ForwardRange>::type = boost::transform_iterator<std::binder1st<std::plus<int> >, __gnu_cxx::__normal_iterator<const int*, std::vector<int> >, boost::use_default, boost::use_default>]’ doit.cpp:8:114: instantiated from here /usr/include/boost/iterator/transform_iterator.hpp:99:26: error: no matching function for call to ‘std::binder1st<std::plus<int> >::binder1st()’ /usr/include/boost/iterator/transform_iterator.hpp:99:26: note: candidates are: /usr/include/c++/4.6/backward/binders.h:109:7: note: std::binder1st<_Operation>::binder1st(const _Operation&, const typename _Operation::first_argument_type&) [with _Operation = std::plus<int>, typename _Operation::first_argument_type = int] /usr/include/c++/4.6/backward/binders.h:109:7: note: candidate expects 2 arguments, 0 provided /usr/include/c++/4.6/backward/binders.h:100:11: note: std::binder1st<std::plus<int> >::binder1st(const std::binder1st<std::plus<int> >&) /usr/include/c++/4.6/backward/binders.h:100:11: note: candidate expects 1 argument, 0 provided Kompilacja nie powiodła się make: *** [doit] Błąd 1
Sorry, not going any further with this; the premise is wrong. All iterators must be default constructible. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
I'm not going to comment on the issue of forward iterator default constructibility, but I do agree with this:
1. The macro BOOST_RANGE_ENABLE_CONCEPT_ASSERT should be documented, as it is necessary to keep the concepts BS at bay.
From time to time, often by no fault of our own (e.g. because we are using someone else's non-conformant library), we are forced to use components (e.g. iterators) that are not Standard-conformant. I think Boost should not stand in the way of using such components in cases where their non-conformance does not detract from the task in an essential way. In the OP's example, concept checking was used to check for a requirement that was not necessary for correct operation of the algorithm. To avoid this, Boost should provide the option to disable such concept checking, and of course this option should be documented.
Regards, Nate
2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding.
I think the Boost authors are unlikely to decide to ignore a part of the standard just because one person believes it is obnoxious and misguided and promotes sloppy coding. I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here. Regards, Nate
on Wed Sep 28 2011, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding.
I think the Boost authors are unlikely to decide to ignore a part of the standard just because one person believes it is obnoxious and misguided and promotes sloppy coding.
I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here.
I'd also like to point out that there's no rule saying default-constructed iterators must be singular. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
on Wed Sep 28 2011, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding.
I think the Boost authors are unlikely to decide to ignore a part of the standard just because one person believes it is obnoxious and misguided and promotes sloppy coding.
I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here.
I'd also like to point out that there's no rule saying default-constructed iterators must be singular.
A default-constructed iterator must be singular not because the government says so but because of logic. You usually get wet when it rains, although there is no rule saying that you must. Standard iterators are all singular by default. An exception would be an iterator to a singleton container or an iterator defined in a closure; those are, however, edge cases. IMHO, Chris
on Thu Sep 29 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
on Wed Sep 28 2011, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding.
I think the Boost authors are unlikely to decide to ignore a part of the standard just because one person believes it is obnoxious and misguided and promotes sloppy coding.
I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here.
I'd also like to point out that there's no rule saying default-constructed iterators must be singular.
A default-constructed iterator must be singular not because the government says so but because of logic.
No. Well, we have to say what we mean by "is singular." Because the concept "singular" only contains two operations (assign and destroy), every valid iterator is-a singular iterator in some sense. But I suspect you mean "minimally singular," and there's no reason at all that a default-constructed iterator need be minimally singular. You usually can't make it usefully dereferenceable (would you want to?) but you can make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Thu, Sep 29, 2011 at 9:50 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Sep 29 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
on Wed Sep 28 2011, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:
2. The concept mechanism used by Boost should not require singular iterators to exist; the standard is obnoxious and misguided here and promotes sloppy coding.
I think the Boost authors are unlikely to decide to ignore a part of
the
standard just because one person believes it is obnoxious and misguided and promotes sloppy coding.
I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here.
I'd also like to point out that there's no rule saying default-constructed iterators must be singular.
A default-constructed iterator must be singular not because the government says so but because of logic.
No. Well, we have to say what we mean by "is singular." Because the concept "singular" only contains two operations (assign and destroy), every valid iterator is-a singular iterator in some sense. But I suspect you mean "minimally singular," and there's no reason at all that a default-constructed iterator need be minimally singular. You usually can't make it usefully dereferenceable (would you want to?) but you can make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular.
I'm sorry - but regarding the statement "every valid iterator is-a singular iterator in some sense"... I thought the Standard (2003) explicitly stated that *singular *values for an iterator had all but one operation as Undefined Behavior, and the only defined operation on an iterator with a singular value was to assign it a non-singular value. (24.1, para 5) *Results of most expressions are undefined for singular values; the only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable values are always nonsingular.* Doesn't the last sentence make it true that "every valid iterator is-a *non*singular iterator"? I also thought it was the case that the latest standard defines *singular *to be the same as *uninitialized *with respect to iterators? If that's the case then we cannot call a valid iterator a singular iterator in any sense. "I am but an egg", but it seem that there's no need to create a new term when the old one is well-defined and sufficient. regards, Brian
on Thu Sep 29 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
On Thu, Sep 29, 2011 at 9:50 AM, Dave Abrahams <dave@boostpro.com> wrote:
I'm sorry - but regarding the statement "every valid iterator is-a singular iterator in some sense"... I thought the Standard (2003) explicitly stated that singular values for an iterator had all but one operation as Undefined Behavior, and the only defined operation on an iterator with a singular value was to assign it a non-singular value. (24.1, para 5)
Yes; this is a problem with negative requirements statements. Just like you can't decrement a forward iterator, you can't dereference a singular iterator. However, a bidirectional iterator, which you can decrement, is-a forward iterator. In the same way, a valid iterator is-a singular iterator.
Results of most expressions are undefined for singular values; the only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable values are always nonsingular. Doesn't the last sentence make it true that "every valid iterator is-a nonsingular iterator"?
(it doesn't, even by logic, since some valid iterators are not dereferenceable, but that aside...). In the sense I'm using is-a, a nonsingular iterator is-a singular iterator. How's that for fun logic? :-) When the standard says "that's a singular iterator" it's saying you can only assume it supports two operations. That doesn't mean it can't support more operations. It's a constraint on the user, not on the iterator.
I also thought it was the case that the latest standard defines singular to be the same as uninitialized with respect to iterators?
There's still no definition of singular other than the text you cited.
If that's the case then we cannot call a valid iterator a singular iterator in any sense.
In the sense of concept requirements, you can. Any valid iterator supports a superset of the requirements on singular iterators The point is that the OP claimed every default-constructed iterator is singular. The only way that could be true is if you take the term "is-a" in the sense I'm using it here. That is, I can easily create an iterator that, when default-constructed, supports a strict superset of the required operations for singular iterators. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Yes; this is a problem with negative requirements statements. Just like you can't decrement a forward iterator, you can't dereference a singular iterator.
The characterization "just like" is a little off. Trying to decrement a forward iterator is a conceptual error. Trying to dereference an iterator with a singular value is a logic error. I think we get into trouble when we talk about "valid iterators". I don't think there's such really such a thing at all. There may be cases where it's valid to decrement an iterator, but not dereference it. There may be cases where it's valid to dereference an iterator but not decrement. A PTE iterator is well-formed, but both incrementing and dereferencing is invalid.
The point is that the OP claimed every default-constructed iterator is singular. The only way that could be true is if you take the term "is-a" in the sense I'm using it here. That is, I can easily create an iterator that, when default-constructed, supports a strict superset of the required operations for singular iterators.
Without any strong guarantees about the state of default constructed iterators in general, I don't think I'd try to use them in a generic algorithm. This is just begging for trouble: template<typename I> auto f() { I i; assert(*i); } // worst algorithm ever If I know that the iterator has valid operations after being default constructed, then I'll do as I like -- whatever the concept does or does not say. counting_iterator<int> i(0); cout << *i <<; // should work just fine
Andrew Sutton wrote:
template<typename I> auto f() { I i; assert(*i); } // worst algorithm ever
If I know that the iterator has valid operations after being default constructed, then I'll do as I like -- whatever the concept does or does not say.
OTOH, if I know that a singular iterator of some type would have no valid operations, and the iterator is only meant to be used by algorithms, the benefit of being unable to create a singular iterator (like when the iterator in question holds a reference to supporting data used in its operation) outweighs the benefit of being able to do so. IMHO, Chris
template<typename I> auto f() { I i; assert(*i); } // worst algorithm ever
OTOH, if I know that a singular iterator of some type would have no valid operations, and the iterator is only meant to be used by algorithms, the benefit of being unable to create a singular iterator (like when the iterator in question holds a reference to supporting data used in its operation) outweighs the benefit of being able to do so.
I think I've lost the thread of the argument. Are you saying that you should *not* be able to default construct iterators?
Andrew Sutton wrote:
template<typename I> auto f() { I i; assert(*i); } // worst algorithm ever
OTOH, if I know that a singular iterator of some type would have no valid operations, and the iterator is only meant to be used by algorithms, the benefit of being unable to create a singular iterator (like when the iterator in question holds a reference to supporting data used in its operation) outweighs the benefit of being able to do so.
I think I've lost the thread of the argument. Are you saying that you should *not* be able to default construct iterators?
What I am saying is that iterators that are not default-constructible are sometimes more robust because an attempt to create them out of thin air results in a compile-time error. I am not saying that all iterators are like that (I agree with Dave regarding his the interpretation of NULL). Moreover, such iterators sometimes come up naturally from standard components (and not some shady third-party ones, as has been suggested), as evidenced in my code that fails to compile with Boost concepts. Being a singular iterator is not a concept, it is a run-time property. The compiler cannot check whether an operator is singular, it is equivalent to the halting problem. IMHO, Chris
on Sat Oct 01 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Andrew Sutton wrote:
template<typename I> auto f() { I i; assert(*i); } // worst algorithm ever
OTOH, if I know that a singular iterator of some type would have no valid operations, and the iterator is only meant to be used by algorithms, the benefit of being unable to create a singular iterator (like when the iterator in question holds a reference to supporting data used in its operation) outweighs the benefit of being able to do so.
I think I've lost the thread of the argument. Are you saying that you should *not* be able to default construct iterators?
What I am saying is that iterators that are not default-constructible are sometimes more robust because an attempt to create them out of thin air results in a compile-time error.
Yes... except that they are not iterators.
I am not saying that all iterators are like that (I agree with Dave regarding his the interpretation of NULL). Moreover, such iterators sometimes come up naturally from standard components (and not some shady third-party ones, as has been suggested), as evidenced in my code that fails to compile with Boost concepts.
Sorry, which code was that?
Being a singular iterator is not a concept, it is a run-time property. The compiler cannot check whether an operator is singular, it is equivalent to the halting problem.
It can't check whether an iterator is random-access either. All (good) concepts have semantic constraints that can't be checked by the compiler. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
on Sat Oct 01 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
What I am saying is that iterators that are not default-constructible are sometimes more robust because an attempt to create them out of thin air results in a compile-time error.
Yes... except that they are not iterators.
Let’s call them concrete quasi-iterators then. It is less important how you call them than what you can do with them.
I am not saying that all iterators are like that (I agree with Dave regarding his the interpretation of NULL). Moreover, such iterators sometimes come up naturally from standard components (and not some shady third-party ones, as has been suggested), as evidenced in my code that fails to compile with Boost concepts.
Sorry, which code was that?
In the opening post.
Being a singular iterator is not a concept, it is a run-time property. The compiler cannot check whether an operator is singular, it is equivalent to the halting problem.
It can't check whether an iterator is random-access either. All (good) concepts have semantic constraints that can't be checked by the compiler.
An algorithm using a bidirectional iterator for a random-access iterator will still work, only it will take longer to accomplish. An algorithm using a singular iterator is likely to crash, which is much more serious. Also, being a singular iterator is independent of type, while being a random-access iterator is determined by type. IMHO, Chris
on Sun Oct 02 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
on Sat Oct 01 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
What I am saying is that iterators that are not default-constructible are sometimes more robust because an attempt to create them out of thin air results in a compile-time error.
Yes... except that they are not iterators.
Let’s call them concrete quasi-iterators then. It is less important how you call them than what you can do with them.
I am not saying that all iterators are like that (I agree with Dave regarding his the interpretation of NULL). Moreover, such iterators sometimes come up naturally from standard components (and not some shady third-party ones, as has been suggested), as evidenced in my code that fails to compile with Boost concepts.
Sorry, which code was that?
In the opening post.
*rewinds to opening post* Lack of documentation aside, what's the underlying problem there? Oh, the result of bind1st is not default-constructible? Well, that's what you get for using deprecated components ;-) More seriously... I understand the problem. What's obnoxious is that the standard doesn't have a consistent view of the importance of Regular Types (c.f. Stepanov). Those binders are not Regular since they don't have a default-constructor... well, neither are many iterators because they don't all have a total ordering, but I think the notion of Regular may have been expanded since '98... but anyway, yeah, let's just say the standard's inconsistent view of default construction causes an interoperability problem. For the record, I'm torn about the whole "Regular Types" thing. I can see the argument for it, but it also forces weaker invariants. Now, I *think* what you want is for the Range library to "degrade gracefully" when you don't satisfy its concept requirements, and the appropriate thing to do there is shut off concept checking. If the Range library were to put its "concept checking stamp of approval" on a nonconforming iterator it would be failing to provide an assurance I want: that the resulting iterator can be used with *any* algorithm requiring iterators. If I can get an error later by passing the resulting iterator to some algorithm that happens to use default construction, then I have a right to complain that concept checking is broken.
Being a singular iterator is not a concept, it is a run-time property. The compiler cannot check whether an operator is singular, it is equivalent to the halting problem.
It can't check whether an iterator is random-access either. All (good) concepts have semantic constraints that can't be checked by the compiler.
An algorithm using a bidirectional iterator for a random-access iterator will still work, only it will take longer to accomplish.
No. A bidirectional iterator can provide different semantics (or invoke undefined behavior) for random-access iterator operations that are not part of the bidirectional iterator concept.
Also, being a singular iterator is independent of type, while being a random-access iterator is determined by type.
No again. Objects of this type are not singular iterators: struct nonsingular { private: void operator=(nonsingular const&); }; Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Also, being a singular iterator is independent of type, while being a random-access iterator is determined by type.
No again. Objects of this type are not singular iterators:
struct nonsingular { private: void operator=(nonsingular const&); };
Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero.
I'm sorry. This is completely wrong. 0 is value -- a state of an numeric type -- just like singularity is the state of some iterators. In fact, I think you actually prove Chris' point, here; you've just extended the notion of singularity from iterators to integers. I would take that to mean that singularity is independent of type.
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
Also, being a singular iterator is independent of type, while being a
random-access iterator is determined by type.
No again. Objects of this type are not singular iterators:
struct nonsingular { private: void operator=(nonsingular const&); };
Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero.
I'm sorry. This is completely wrong. 0 is value -- a state of an numeric type -- just like singularity is the state of some iterators.
Yes. I don't see that as a contradiction.
In fact, I think you actually prove Chris' point, here; you've just extended the notion of singularity from iterators to integers.
It's not like I just did something new, here!
I would take that to mean that singularity is independent of type.
Although many types have singular values with respect to certain operations (NULL is singular with respect to pointer dereference), - Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type. I suspect this situation is less one of "you're completely wrong" than "you and I are understanding the same words in different ways." Cheers, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
No again. Objects of this type are not singular iterators:
Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero.
I'm sorry. This is completely wrong. 0 is value -- a state of an numeric type -- just like singularity is the state of some iterators.
Yes. I don't see that as a contradiction.
It sounded to me like you were equating the state of singularity with a type. This explanation makes your meaning more clear.
- Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values
I think this discussion that confirms my original claim that talking about valid iterators is troublesome -- I think, singular iterators, by extension. With such a vaguely defined notion of singularity we need more concrete properties to reason about the validity of operations on such iterators. What are the properties of an iterator that could cause operations on it to result in undefined behavior? It's position in a valid range. I think discussing the validity of iterators without the context of some "source" range is not meaningful. This is also EoP's approach; I don't recall reading about singular iterators there (but I don't have the book in front of me so I can't check).
I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type. I suspect this situation is less one of "you're completely wrong" than "you and I are understanding the same words in different ways."
Independent as in, not bound to any specific type, but also dependent as in, a type might define its own notion of singularity. You're right. Same thing, different words :)
Dave Abrahams wrote:
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I would take that to mean that singularity is independent of type.
Although many types have singular values with respect to certain operations (NULL is singular with respect to pointer dereference),
- Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values
I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type.
It means iterators of the same type can be singular but need not, whereas all (valid) iterators of the same type either must support random access operations or must not, depending on the type in question. Of course, the result of subtraction may be undefined, but it will not fail to compile. If you insist that random access iterators are things you can universally subtract, it will be a concept that applies to pairs, not to individual objects.
I suspect this situation is less one of "you're completely wrong" than "you and I are understanding the same words in different ways."
Probably :-( Best regards, Chris
On Mon, 3 Oct 2011, Krzysztof Żelechowski wrote:
Dave Abrahams wrote:
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I would take that to mean that singularity is independent of type.
Although many types have singular values with respect to certain operations (NULL is singular with respect to pointer dereference),
- Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values
I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type.
It means iterators of the same type can be singular but need not, whereas all (valid) iterators of the same type either must support random access operations or must not, depending on the type in question.
Of course, the result of subtraction may be undefined, but it will not fail to compile. If you insist that random access iterators are things you can universally subtract, it will be a concept that applies to pairs, not to individual objects.
Another complicating issue is that an iterator is singular or non-singular with respect to a particular container. For example, given the following declarations: int a[5], b[5]; and assuming a and b are contiguous in memory, &a[5] is a singular iterator for the array a, while &b[0] is non-singular for the array b, even though those two pointers will have exactly the same value and are not distinguishable by C++ code. -- Jeremiah Willcock
on Mon Oct 03 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> wrote:
Another complicating issue is that an iterator is singular or non-singular with respect to a particular container. For example, given the following declarations:
int a[5], b[5];
and assuming a and b are contiguous in memory, &a[5] is a singular iterator for the array a
It's a PTE iterator, which is not minimally singular. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Mon, 3 Oct 2011, Dave Abrahams wrote:
on Mon Oct 03 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> wrote:
Another complicating issue is that an iterator is singular or non-singular with respect to a particular container. For example, given the following declarations:
int a[5], b[5];
and assuming a and b are contiguous in memory, &a[5] is a singular iterator for the array a
It's a PTE iterator, which is not minimally singular.
Yes, I forgot that, although the issue of dereferenceability is similar, and &a[5] + 1 (== &b[1]) has a similar issue with singularity. -- Jeremiah Willcock
on Mon Oct 03 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I would take that to mean that singularity is independent of type.
Although many types have singular values with respect to certain operations (NULL is singular with respect to pointer dereference),
- Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values
I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type.
It means iterators of the same type can be singular but need not, whereas all (valid) iterators of the same type either must support random access operations or must not, depending on the type in question.
Not so, and I can think of a counterexample, but I'm getting tired of arguing about it. I don't think this is really relevant to the discussion in the end, is it? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
on Mon Oct 03 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I would take that to mean that singularity is independent of type.
Although many types have singular values with respect to certain operations (NULL is singular with respect to pointer dereference),
- Not every type has singular values - Some types have multiple singular values - In general, one type's singular values are distinct from another type's singular values
I don't know what you and Chris mean by "independent of type," but to me this sounds like singularity is highly dependent on type.
It means iterators of the same type can be singular but need not, whereas all (valid) iterators of the same type either must support random access operations or must not, depending on the type in question.
Not so, and I can think of a counterexample, but I'm getting tired of arguing about it. I don't think this is really relevant to the discussion in the end, is it?
I understand that you may be tired of my questions, and I appreciate your answering them :-) Thank you very much anyway. Chris
on Tue Oct 04 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
I can think of a counterexample, but I'm getting tired of
arguing about it. I don't think this is really relevant to the discussion in the end, is it?
I understand that you may be tired of my questions, and I appreciate your answering them :-) Thank you very much anyway.
To clarify: I'm not tired of your questions; I'm tired of arguing about whether singularity is dependent on type. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero.
I'm sorry. This is completely wrong. 0 is value -- a state of an numeric type -- just like singularity is the state of some iterators. In fact, I think you actually prove Chris' point, here; you've just extended the notion of singularity from iterators to integers. I would take that to mean that singularity is independent of type.
I should amend my previous statements. Maybe singularity is best viewed as a property of an expression. 0 is certainly a valid integral value. Unfortunately, there are no general named iterator values. What's a singular state for one may not be a singular state for another. I think an interesting question is, "what are the general properties of iterators that causes operations on them to result in singularity?". When is *i defined?
on Sun Oct 02 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I think an interesting question is, "what are the general properties of iterators that causes operations on them to result in singularity?". When is *i defined?
Two separate questions. PTE iterators are "nonsingular" (i.e. support a superset of the operations required of singular iterators) but you can't dereference them. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
*rewinds to opening post*
Lack of documentation aside, what's the underlying problem there? Oh, the result of bind1st is not default-constructible? Well, that's what you get for using deprecated components ;-)
It would help if you could offer a replacement that does the same thing, compiles in traditional mode and does not involve defining a dedicated iterator class.
More seriously... I understand the problem. What's obnoxious is that the standard doesn't have a consistent view of the importance of Regular Types (c.f. Stepanov). Those binders are not Regular since they don't have a default-constructor... well, neither are many iterators because they don't all have a total ordering, but I think the notion of Regular may have been expanded since '98... but anyway, yeah, let's just say the standard's inconsistent view of default construction causes an interoperability problem.
For the record, I'm torn about the whole "Regular Types" thing. I can see the argument for it, but it also forces weaker invariants.
Now, I *think* what you want is for the Range library to "degrade gracefully" when you don't satisfy its concept requirements, and the appropriate thing to do there is shut off concept checking.
Do not switch all concept checking off if it fails; switch default constructibility check off always.
If the Range library were to put its "concept checking stamp of approval" on a nonconforming iterator it would be failing to provide an assurance I want: that the resulting iterator can be used with *any* algorithm requiring iterators. If I can get an error later by passing the resulting iterator to some algorithm that happens to use default construction, then I have a right to complain that concept checking is broken.
My point is, I am unable to imagine an algorithm that requires constructing iterators out of thin air. Some algorithms do that, for no other reason than the programmer did not know better, and they can be fixed to avoid this construct, and when they get fixed, the code gets better. So requiring default construction of iterators leads to looser library code. If you happen to know such an algorithm, please share it with us.
Being a singular iterator is not a concept, it is a run-time property. The compiler cannot check whether an operator is singular, it is equivalent to the halting problem.
It can't check whether an iterator is random-access either. All (good) concepts have semantic constraints that can't be checked by the compiler.
An algorithm using a bidirectional iterator for a random-access iterator will still work, only it will take longer to accomplish.
No. A bidirectional iterator can provide different semantics (or invoke undefined behavior) for random-access iterator operations that are not part of the bidirectional iterator concept.
But I can use the operations defined on a bidirectional iterator to simulate the operations of a random access iterator, can’t I?
Also, being a singular iterator is independent of type, while being a random-access iterator is determined by type.
No again. Objects of this type are not singular iterators:
struct nonsingular { private: void operator=(nonsingular const&); };
Why do you call this thing an iterator?
Singular values crop up in all kinds of contexts, BTW. Do ints support division? Well, yes, unless the denominator is zero.
Best regards, Chris
on Mon Oct 03 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
*rewinds to opening post*
Lack of documentation aside, what's the underlying problem there? Oh, the result of bind1st is not default-constructible? Well, that's what you get for using deprecated components ;-)
It would help if you could offer a replacement that does the same thing, compiles in traditional mode and does not involve defining a dedicated iterator class.
You could pass it through boost::function. I'm not sure if boost::bind makes default-constructible things... nor am I sure about phoenix/lambda.
Now, I *think* what you want is for the Range library to "degrade gracefully" when you don't satisfy its concept requirements, and the appropriate thing to do there is shut off concept checking.
Do not switch all concept checking off if it fails; switch default constructibility check off always.
Yes, but that would be wrong, if the library is going to advertise that it checks for the standard iterator concepts. On the other hand, if the library doesn't advertise its checks, then that's up to the author.
If the Range library were to put its "concept checking stamp of approval" on a nonconforming iterator it would be failing to provide an assurance I want: that the resulting iterator can be used with *any* algorithm requiring iterators. If I can get an error later by passing the resulting iterator to some algorithm that happens to use default construction, then I have a right to complain that concept checking is broken.
My point is, I am unable to imagine an algorithm that requires constructing iterators out of thin air. Some algorithms do that, for no other reason than the programmer did not know better, and they can be fixed to avoid this construct, and when they get fixed, the code gets better. So requiring default construction of iterators leads to looser library code. If you happen to know such an algorithm, please share it with us.
I don't. It doesn't matter whether the requirement was wrong, though.
An algorithm using a bidirectional iterator for a random-access iterator will still work, only it will take longer to accomplish.
No. A bidirectional iterator can provide different semantics (or invoke undefined behavior) for random-access iterator operations that are not part of the bidirectional iterator concept.
But I can use the operations defined on a bidirectional iterator to simulate the operations of a random access iterator, can’t I?
No; you can't measure the distance between two arbitrary bidirectional iterators unless you know which one comes first. But my point is that if the iterator is truly bidirectional but it advertises itself to be random-access, you have no way of knowing to use multiple ++ invocations instead of one +=, and += could do something arbitrarily horrible.
Also, being a singular iterator is independent of type, while being a random-access iterator is determined by type.
No again. Objects of this type are not singular iterators:
struct nonsingular { private: void operator=(nonsingular const&); };
Why do you call this thing an iterator?
Exactly my point; I don't. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
on Thu Sep 29 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
Yes; this is a problem with negative requirements statements. Just like you can't decrement a forward iterator, you can't dereference a singular iterator.
The characterization "just like" is a little off. Trying to decrement a forward iterator is a conceptual error. Trying to dereference an iterator with a singular value is a logic error.
Meh. They're both programming errors. The first one can be caught at compile time, so they're different in that way, but that doesn't really affect my point.
I think we get into trouble when we talk about "valid iterators". I don't think there's such really such a thing at all. There may be cases where it's valid to decrement an iterator, but not dereference it. There may be cases where it's valid to dereference an iterator but not decrement. A PTE iterator is well-formed, but both incrementing and dereferencing is invalid.
The point is that the OP claimed every default-constructed iterator is singular. The only way that could be true is if you take the term "is-a" in the sense I'm using it here. That is, I can easily create an iterator that, when default-constructed, supports a strict superset of the required operations for singular iterators.
Without any strong guarantees about the state of default constructed iterators in general, I don't think I'd try to use them in a generic algorithm.
No, of course not. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Thu, Sep 29, 2011 at 3:59 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Sep 29 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
On Thu, Sep 29, 2011 at 9:50 AM, Dave Abrahams <dave@boostpro.com> wrote:
I'm sorry - but regarding the statement "every valid iterator is-a singular iterator in some sense"... I thought the Standard (2003) explicitly stated that singular values for an iterator had all but one operation as Undefined Behavior, and the only defined operation on an iterator with a singular value was to assign it a non-singular value. (24.1, para 5)
Yes; this is a problem with negative requirements statements. Just like you can't decrement a forward iterator, you can't dereference a singular iterator. However, a bidirectional iterator, which you can decrement, is-a forward iterator. In the same way, a valid iterator is-a singular iterator.
Your ontology seems to have no basis in the ontology of the standard. The last sentence I quoted: *Dereferenceable values are always nonsingular.* This sentence doesn't leave room for a statement like "every valid iterator is-a singular iterator in some sense", given that dereferenceable iterators are valid, and the standard explicitly states that they are non-singular. Your definition of "in a sense" and "in teh same way" are then in contradiction to the standard. You can't modify that requirement of the standard to behave as a parent class acts in a type algebra, where a subclass can override the superclass - unless there is another part of the standard which allows such a replacement [is there?]. Rather, this particular definition seems to set "singular" values apart from defined (whether or not they're safe to dereference) values. If we want to map the concepts to a type algebra, then a singular value would correspond to a "final" type that prohibits subclassing. If we want to be precise about the three partitions of iterators, we should use "singular" in the way that the standard uses it. We could easily use two more terms: Dereferenceable & Nonsingular, where the former is a proper subset of the latter. But the standard seems to explicitly make Singular iterators a non-intersecting set with the Nonsingular set, and all iterators must belong to exactly one of Singular or Nonsingular.
Results of most expressions are undefined for singular values; the only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable values are always nonsingular. Doesn't the last sentence make it true that "every valid iterator is-a nonsingular iterator"?
(it doesn't, even by logic, since some valid iterators are not dereferenceable, but that aside...). In the sense I'm using is-a, a nonsingular iterator is-a singular iterator. How's that for fun logic? :-)
Your ontology seems to require an overriding of the standard - which part of the standard allows for that overriding?
When the standard says "that's a singular iterator" it's saying you can only assume it supports two operations. That doesn't mean it can't support more operations. It's a constraint on the user, not on the iterator.
But when it says "*Dereferenceable values are always nonsingular.*", that seems to be a constraint on the iterator. Being X or Non-X are mutually exclusive.
In the sense of concept requirements, you can. Any valid iterator supports a superset of the requirements on singular iterators
If you're only concerned with the positive requirements of a concept, then yes. But we must be concerned with both positive and negative requirements - since the standard explicitly excludes dereferenceable values from being singular, then being "singular" doesnt' really map well to concept requirements [if I understand your contextual use of the term].
The point is that the OP claimed every default-constructed iterator is singular. The only way that could be true is if you take the term "is-a" in the sense I'm using it here. That is, I can easily create an iterator that, when default-constructed, supports a strict superset of the required operations for singular iterators.
But I could make an iterator type whose constructor would throw() if it were not to a valid member. A contrived example, but then there would be a type which would refute OP's claim while adhering to the standard. Hence, the OP's claim is in error. Curiosity: why are you trying to form an algebra in which the OP's claim is correct?
on Thu Sep 29 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
On Thu, Sep 29, 2011 at 3:59 PM, Dave Abrahams <dave@boostpro.com> wrote:
Your ontology seems to have no basis in the ontology of the standard. The last sentence I quoted:
Dereferenceable values are always nonsingular.
This sentence doesn't leave room for a statement like "every valid iterator is-a singular iterator in some sense", given that dereferenceable iterators are valid, and the standard explicitly states that they are non-singular. Your definition of "in a sense" and "in teh same way" are then in contradiction to the standard.
Not if a nonsingular iterator is-a singular iterator. That way of using is-a is the only sense that makes the OP's claim true. Either you have to accept that way of using is-a or you have to reject the OP's claim. I'm able to use and think about "is-a" that way, and if you chafe at the idea that a nonsingular iterator is-a singular iterator, that's fine with me. I think that means you have to reject the claim that all default-constructed iterators are singular, which is also fine with me.
When the standard says "that's a singular iterator" it's saying you can only assume it supports two operations. That doesn't mean it can't support more operations. It's a constraint on the user, not on the iterator.
But when it says "Dereferenceable values are always nonsingular.", that seems to be a constraint on the iterator. Being X or Non-X are mutually exclusive.
That's the crux of the issue. If you believe that, there's no way the OP's claim can be true.
In the sense of concept requirements, you can. Any valid iterator supports a superset of the requirements on singular iterators
If you're only concerned with the positive requirements of a concept, then yes. But we must be concerned with both positive and negative requirements - since the standard explicitly excludes dereferenceable values from being singular, then being "singular" doesnt' really map well to concept requirements [if I understand your contextual use of the term].
OK, that's another way to say it.
The point is that the OP claimed every default-constructed iterator is singular. The only way that could be true is if you take the term "is-a" in the sense I'm using it here. That is, I can easily create an iterator that, when default-constructed, supports a strict superset of the required operations for singular iterators.
But I could make an iterator type whose constructor would throw() if it were not to a valid member.
Sure. That's actually a valid (if perverse) iterator. But then, you could make an iterator where every operation throws unconditionally.
A contrived example, but then there would be a type which would refute OP's claim while adhering to the standard.
Refuting the OP's claim while adhering to the standard doesn't require such contortions: // untested struct charp : boost::iterator_adaptor<char*> { charp() : charp::super_t(0) {} // <== voilà charp(charp const& rhs) : charp::super_t(rhs) {} }; charp() == charp(); // defined behavior charp() != charp(); // defined behavior charp() < charp(); // defined behavior charp() > charp(); // defined behavior charp() > charp(); // defined behavior charp x, y = x; // defined behavior
Curiosity: why are you trying to form an algebra in which the OP's claim is correct?
My point is that even if such an algebra exists, it doesn't mean what the OP thinks it means. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Fri, Sep 30, 2011 at 11:22 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Sep 29 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
On Thu, Sep 29, 2011 at 3:59 PM, Dave Abrahams <dave@boostpro.com> wrote:
Your ontology seems to have no basis in the ontology of the standard. The last sentence I quoted:
Dereferenceable values are always nonsingular.
This sentence doesn't leave room for a statement like "every valid iterator is-a singular iterator in some sense", given that dereferenceable iterators are valid, and the standard explicitly states that they are non-singular. Your definition of "in a sense" and "in teh same way" are then in contradiction to the standard.
Not if a nonsingular iterator is-a singular iterator. That way of using is-a is the only sense that makes the OP's claim true. Either you have to accept that way of using is-a or you have to reject the OP's claim. I'm able to use and think about "is-a" that way, and if you chafe at the idea that a nonsingular iterator is-a singular iterator, that's fine with me. I think that means you have to reject the claim that all default-constructed iterators are singular, which is also fine with me.
It's not an issue of chafing, but accepting the OPs claim to be true requires the quoted sentence to be nonsensical. I'm not sure of any useful algebra where a member can be both X and non-X simultaneously. If there is one, please share? However, refuting the OPs claim has not even an apparent contradiction either to the standard or to my own understanding of fundamental logic.
on Fri Sep 30 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
It's not an issue of chafing, but accepting the OPs claim to be true requires the quoted sentence to be nonsensical.
No
I'm not sure of any useful algebra where a member can be both X and non-X simultaneously. If there is one, please share?
"Singular" defines a concept: Saying it is "Singular" doesn't say anything else meaningful about an iterator beyond what's in that concept: self-assignment and destruction. It doesn't even guarantee that the other operations will compile, since the compiler is allowed to detect them as an expression of undefined behavior. All nonsingular iterators conform to a concept that refines "Singular." This is no less a "useful algebra" (whatever that means) than any other concept refinement relationship.
However, refuting the OPs claim has not even an apparent contradiction either to the standard or to my own understanding of fundamental logic.
I don't know what that means either. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular.
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence? Chris
2011/9/30 Krzysztof Żelechowski <giecrilj@stegny.2a.pl>
Dave Abrahams wrote:
make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular.
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
That's not what he said. As an aside though, recall that *char foo[0]; *is a valid declaration of a zero-length aray.
on Fri Sep 30 2011, Brian Allison <brian.w.allison-AT-gmail.com> wrote:
That's not what he said.
As an aside though, recall that char foo[0]; is a valid declaration of a zero-length aray.
Not in C++98, IIRC. Did that change, or am I mistaken? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
2011/9/30 Krzysztof Żelechowski <giecrilj@stegny.2a.pl>
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
I believe this code is valid: #include <vector> int main() { const int *begin = 0, *end = 0; std::vector<int> v(begin, end); } NULL pointer is a valid pass-the-end iterator here. Roman Perepelitsa.
2011/9/30 Krzysztof Żelechowski <giecrilj@stegny.2a.pl>:
Dave Abrahams wrote:
make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular.
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
You don't need to allocate anything if your sequence is of length 0, since a NULL pointer is comparable, destroyable and copyable. It can't be dereferenced nor incremented but if the sequence has length 0 you can't anyway.
Chris
-- Felipe Magno de Almeida
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
Actually, every iterator (singular, initialized, pointing to viable memory or not) defines its own empty range. That is, for every i, [i, i) is an empty range, which means that, if all you know is that you have that range, then it is not valid to increment, decrement, or dereference. You can certainly construct an empty range on nullptr.
On Fri, Sep 30, 2011 at 11:24 AM, Andrew Sutton <asutton.list@gmail.com> wrote:
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
Actually, every iterator (singular, initialized, pointing to viable memory or not) defines its own empty range. That is, for every i, [i, i) is an empty range, which means that, if all you know is that you have that range, then it is not valid to increment, decrement, or dereference. You can certainly construct an empty range on nullptr.
You can't equally-compare a singular iterator. -- Felipe Magno de Almeida
On Fri, Sep 30, 2011 at 12:06 PM, Andrew Sutton <asutton.list@gmail.com> wrote:
You can't equally-compare a singular iterator.
Why not? Isn't an object equal to itself?
Because a singular iterator can be a uninitialized variable and you can't equally-compare a uninitialized variable, nor copy it. All you can do is assign and destroy it. Regards, -- Felipe Magno de Almeida
Why not? Isn't an object equal to itself?
Because a singular iterator can be a uninitialized variable and you can't equally-compare a uninitialized variable, nor copy it. All you can do is assign and destroy it.
I know what the standard says, but shouldn't this always return true? int* i; assert(i == i); Regardless of the actual value? It seems to me that this is a pretty fundamental property: an object is always equal to itself*. If you believe it, then you're allowed to construct empty bounded ranges of singular values [i, i). * Excluding volatile objects.
On Fri, Sep 30, 2011 at 12:31 PM, Andrew Sutton <asutton.list@gmail.com> wrote:
Why not? Isn't an object equal to itself?
Because a singular iterator can be a uninitialized variable and you can't equally-compare a uninitialized variable, nor copy it. All you can do is assign and destroy it.
I know what the standard says, but shouldn't this always return true?
It should what the standard says. If it says anything can happen, then anything can happen. Including crashing. It is perfectly possible for a CPU to trap on uninitialized variables for example.
int* i; assert(i == i);
Regardless of the actual value? It seems to me that this is a pretty fundamental property: an object is always equal to itself*. If you believe it, then you're allowed to construct empty bounded ranges of singular values [i, i).
* Excluding volatile objects.
Regards, -- Felipe Magno de Almeida
It should what the standard says. If it says anything can happen, then anything can happen. Including crashing. It is perfectly possible for a CPU to trap on uninitialized variables for example.
int* i; assert(i == i);
Alas, back to the standard. I find the standard's limitations unfortunate; equality comparison of uninitialized values should be allowed. I doubt that allowing that such comparisons would have any significant impact on real programs. More importantly, it lets you draw a direct relationship between an iterator with a singular value (say, i) and an empty range [i, i). The reason why dereferencing a singular iterator is invalid is that you are dereferencing past the end. It's also the same reason why ++ is invalid; you're past the end.
On Fri, Sep 30, 2011 at 11:06 AM, Andrew Sutton <asutton.list@gmail.com>wrote:
You can't equally-compare a singular iterator.
Why not? Isn't an object equal to itself?
There's nothing in the standard to say that an uninitialized variable must be equal to itself. Especially since the standard states that the only defined operation on a singular iterator is ... assignment. If a clever compiler computed the lifespan of all memory usage, is there anything in the standard which would keep it from using the memory of Singular Iterators as temporary storage? Or randomly bit-twiddling the bits in them while they are Singular?
There's nothing in the standard to say that an uninitialized variable must be equal to itself.
Especially since the standard states that the only defined operation on a singular iterator is ... assignment.
Again, I'm not talking about the standard. I'm talking about basic expectations.
If a clever compiler computed the lifespan of all memory usage, is there anything in the standard which would keep it from using the memory of Singular Iterators as temporary storage? Or randomly bit-twiddling the bits in them while they are Singular?
I think any argument that starts with the phrase "If a clever..." is automatically suspect. There are lots of clever things that might be done, but I wonder at what cost. Would you trust your hypothetical compiler to get lifetime right? Do you really want this compiler to modify values behind your back?
On Fri, Sep 30, 2011 at 12:08 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
There's nothing in the standard to say that an uninitialized variable must be equal to itself.
Especially since the standard states that the only defined operation on a singular iterator is ... assignment.
Again, I'm not talking about the standard. I'm talking about basic expectations.
If your basic expectations do not take the standard into account then your expectations may lead you to Undefined-Behavior-Land.
If a clever compiler computed the lifespan of all memory usage, is there anything in the standard which would keep it from using the memory of Singular Iterators as temporary storage? Or randomly bit-twiddling the bits in them while they are Singular?
I think any argument that starts with the phrase "If a clever..." is automatically suspect. There are lots of clever things that might be done, but I wonder at what cost. Would you trust your hypothetical compiler to get lifetime right? Do you really want this compiler to modify values behind your back?
Optimizations are clever, and used to be viewed with suspicion.
If your basic expectations do not take the standard into account then your expectations may lead you to Undefined-Behavior-Land.
Again, the standard is too strict with this limitation; it can be relaxed. Objects of regular types should always be equal to themselves even when they are uninitialized or have singular value.
Optimizations are clever, and used to be viewed with suspicion.
I don't think that this is an unreasonable position.
On Fri, Sep 30, 2011 at 12:45 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
If your basic expectations do not take the standard into account then your expectations may lead you to Undefined-Behavior-Land.
Again, the standard is too strict with this limitation; it can be relaxed. Objects of regular types should always be equal to themselves even when they are uninitialized or have singular value.
When discussing what is allowed on a type T, you're intrinsically discussing the standard. When discussing what a compiler allows, you're not. When discussing what you'd *like *to be allowed, you're not. I had thought we were discussing what was allowed on type T.
Optimizations are clever, and used to be viewed with suspicion.
I don't think that this is an unreasonable position.
Yet "any sentence that starts with 'a clever compiler' should be viewed with suspicion" contradicts the very position you think is reasonable, and was stated as an answer to an example of an optimization a clever compiler might make.
I had thought we were discussing what was allowed on type T.
Sure, but that doesn't invalidate my statement that the standard's limitations are too strict. I'm just thinking ahead.
Yet "any sentence that starts with 'a clever compiler' should be viewed with suspicion" contradicts the very position you think is reasonable, and was stated as an answer to an example of an optimization a clever compiler might make.
I think you may have misunderstood. I think that it is a reasonable position to view some optimizations as suspicious.
I read that as a comment about a hypothetical perfect compiler. One that completely complied with The Standard, and had perfect optimization. Such a compiler would nevertheless be allowed to fiddle with the iterator and be compliant. While providing an iterator that could not be compared to itself (not releiably). Probably, Richard.
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Andrew Sutton Sent: 30 September 2011 18:09 To: boost-users@lists.boost.org Subject: Re: [Boost-users] A forward iterator need not be default-constructible
I had thought we were discussing what was allowed on type T.
Sure, but that doesn't invalidate my statement that the standard's limitations are too strict. I'm just thinking ahead.
Yet "any sentence that starts with 'a clever compiler' should be viewed with suspicion" contradicts the very position you think is reasonable, and was stated as an answer to an example of an optimization a clever compiler might make.
I think you may have misunderstood. I think that it is a reasonable position to view some optimizations as suspicious. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, Sep 30, 2011 at 1:15 PM, Kerry, Richard <richard.kerry@atos.net>wrote:
I read that as a comment about a hypothetical perfect compiler.
One that completely complied with The Standard, and had perfect optimization.
Such a compiler would nevertheless be allowed to fiddle with the iterator and be compliant. While providing an iterator that could not be compared to itself (not releiably).
Yes - that's what I intended.
on Fri Sep 30 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
If your basic expectations do not take the standard into account then your expectations may lead you to Undefined-Behavior-Land.
Again, the standard is too strict with this limitation; it can be relaxed.
Not if you want pointers to be iterators, and we do. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
on Fri Sep 30 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
Actually, every iterator (singular, initialized, pointing to viable memory or not) defines its own empty range.
No, I don't believe that's quite correct. There are lots of things one can do with iterators in a range that one cannot do with a minimally-singular iterator. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Actually, every iterator (singular, initialized, pointing to viable memory or not) defines its own empty range.
No, I don't believe that's quite correct. There are lots of things one can do with iterators in a range that one cannot do with a minimally-singular iterator.
Well, two anyways: == and !=. Given that the standard doesn't allow those on singular-valued iterators, you're right. I think the standard is a little too strict, here.
On Fri, Sep 30, 2011 at 12:29 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
Actually, every iterator (singular, initialized, pointing to viable memory or not) defines its own empty range.
No, I don't believe that's quite correct. There are lots of things one can do with iterators in a range that one cannot do with a minimally-singular iterator.
Well, two anyways: == and !=. Given that the standard doesn't allow those on singular-valued iterators, you're right. I think the standard is a little too strict, here.
More than that, you can't do any comparisons, and the only mutation is to set it to a Non-Singular value.
On Sep 30, 2011, at 12:29 PM, Andrew Sutton wrote:
Well, two anyways: == and !=. Given that the standard doesn't allow those on singular-valued iterators, you're right. I think the standard is a little too strict, here.
The underlying values that would need to be compared are potentially "trap" values (c.f. C++99/6.2.6/5). Present commodity hardware typically leads toward different representation requirements for explicitly capturing things like the existance of uninitialized data, resulting in runtime distinctions between normal and debug iterators, for example. However, there has existed (and may still, or may again in the future) hardware implementations which provided direct support for this sort of thing, potentially giving one improved error checking directly by, for example, producing a hardware exception any time a trap value is read. This sort of thing might even be accomplished with present commodity hardware, by doing things like fiddling with parity bits. The standard even alludes to such an approach; see C++99 footnote 44. I would guess that the standard is written the way it is in the area under discussion specifically to support various error checking approaches such as these, and disagree that the standard is too strict in this area.
On Sep 30, 2011, at 1:44 PM, Kim Barrett wrote:
On Sep 30, 2011, at 12:29 PM, Andrew Sutton wrote:
Well, two anyways: == and !=. Given that the standard doesn't allow those on singular-valued iterators, you're right. I think the standard is a little too strict, here.
The underlying values that would need to be compared are potentially "trap" values (c.f. C++99/6.2.6/5).
A bit of an oops here; I had both C++ and C standards open on my screen; and referenced sections are from C. But the argument is still the same.
on Fri Sep 30 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:
Dave Abrahams wrote:
make it copyable, for example. A wrapper over a plain pointer could initialize the pointer to 0. Now it's a valid past-the-end iterator into an array of length zero. Such an iterator is also comparable with other iterators into the same sequence. That's actually far from being minimally singular.
I doubt there may be a sequence of length 0 at NULL. How would you allocate such a sequence?
It already exists. char* p = 0; p == p; // defined behavior p - p; // defined behavior p + 0; // defined behavior -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Nathan Ridge wrote:
I would suggest making your case about the default constructibility of forward iterators at comp.std.c++. If you gain consensus there that this requirement is indeed misguided, then your request will carry more weight here.
Greater minds than mine did and failed (by being ignored); who am I to confront such a valiant enemy? My only hope is to smuggle common sense under the radar ;-) Chris
Hi, W dniu 26 września 2011 19:48 użytkownik Krzysztof Żelechowski < giecrilj@stegny.2a.pl> napisał: [snip]
The standard C++ library defined iterators to serve and additional task to serve as abstract pointers that may be singular, i.e. not corresponding to any object and distinct from any other iterator. To this end, the standard requires that interators may be constructed out of thin air, and that such an iterator is singular.
Chris, if I understand correctly, you claim that default-constructed iterators are required by the standard to be singular? W dniu 29 września 2011 11:02 użytkownik Krzysztof Żelechowski < giecrilj@stegny.2a.pl> napisał:
Dave Abrahams wrote:
I'd also like to point out that there's no rule saying default-constructed iterators must be singular.
A default-constructed iterator must be singular not because the government says so but because of logic. You usually get wet when it rains, although there is no rule saying that you must. Standard iterators are all singular by default.
I disagree. I think requiring default-constructed iterstors to be singular would make plain old pointers not meet the requirements. For example: vector<int>::iterator a; // (1) vector<int>::iterator b = a; // (2) Correct me if I'm wrong: line (1) is legal, and the value of a may be singular, or a may be uninitialized. Therefore line (2) is undefined behavior. However, if we change the example a bit to make a value-initialized: vector<int>::iterator a = vector<int>::iterator(); // (3) vector<int>::iterator b = a; // (4) Now for vactor<int>::iterator == int* the value of a is guaranteed to be singular: NULL, and so line (4) is ok. But my question is, does the standard require singularity for iterators value-initialized like on line (3)? If I understand Dave's point correctly, there's no such requirement in the standard. So Chris, in my opinion you may have a point there, that it could make sense to: 1) add a requirement, that value-initialized default-constructed iterators be singular; 2) allow using such singular-value iterators to compare, but not dereference -- just like vector<int>::end() may be used. - Note, that I'm *not* suggesting to make vector<int>::end() to return a value equal to vector<int>::iterator(). Regards, Kris
2011/9/29 Krzysztof Czainski <1czajnik@gmail.com>
I disagree. I think requiring default-constructed iterstors to be singular would make plain old pointers not meet the requirements. For example: vector<int>::iterator a; // (1) vector<int>::iterator b = a; // (2)
Correct me if I'm wrong: line (1) is legal, and the value of a may be singular, or a may be uninitialized. Therefore line (2) is undefined behavior.
However, if we change the example a bit to make a value-initialized: vector<int>::iterator a = vector<int>::iterator(); // (3) vector<int>::iterator b = a; // (4)
In C++11 singular means what you call uninitialized. iterator.requirements.general p5 Iterators can also have singular values that are not associated with any sequence. [ Example: After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer. — end example ] Results of most expressions are undefined for singular values; the only exceptions are destroying an iterator that holds a singular value, the assignment of a non-singular value to an iterator that holds a singular value, and, for iterators that satisfy the DefaultConstructible requirements, using a value-initialized iterator as the source of a copy or move operation. [ Note: This guarantee is not offered for default initialization, although the distinction only matters for types with trivial default constructors such as pointers or aggregates holding pointers. — end note ] In these cases the singular value is overwritten the same way as any other value. Dereferenceable values are always non-singular. Roman Perepelitsa.
participants (11)
-
Andrew Sutton -
Brian Allison -
Dave Abrahams -
Felipe Magno de Almeida -
Jeremiah Willcock -
Kerry, Richard -
Kim Barrett -
Krzysztof Czainski -
Krzysztof Żelechowski -
Nathan Ridge -
Roman Perepelitsa