Hi, iterator_range returns a signed size. Is this correct? IMO it should return size_t. boost\range\iterator_range_core.hpp: difference_type size() const { return m_End - m_Begin; } Olaf
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
boost\range\iterator_range_core.hpp: difference_type size() const { return m_End - m_Begin; }
Random thought: It seems like advance_begin and advance_end could be used to create a strictly negative size. Returning difference_type allows this to be detected while a size_type does not. - Rhys
On Wed, Oct 19, 2011 at 1:45 AM, Rhys Ulerich <rhys.ulerich@gmail.com> wrote:
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
boost\range\iterator_range_core.hpp: difference_type size() const { return m_End - m_Begin; }
Random thought: It seems like advance_begin and advance_end could be used to create a strictly negative size. Returning difference_type allows this to be detected while a size_type does not.
Sounds like a very weak reason. Especially since: If an instance of iterator_range is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end). If that's the rationale, it'd be better to add is_valid() or so. Olaf
On Wed, Oct 19, 2011 at 1:46 AM, Olaf van der Spek <ml@vdspek.org> wrote:
On Wed, Oct 19, 2011 at 1:45 AM, Rhys Ulerich <rhys.ulerich@gmail.com> wrote:
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
boost\range\iterator_range_core.hpp: difference_type size() const { return m_End - m_Begin; }
Random thought: It seems like advance_begin and advance_end could be used to create a strictly negative size. Returning difference_type allows this to be detected while a size_type does not.
Sounds like a very weak reason. Especially since: If an instance of iterator_range is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end).
If that's the rationale, it'd be better to add is_valid() or so.
What are the requirements on an iterator's difference_type, exactly? Specifically, are you even guaranteed that it is always convertible to *some* unsigned integral type, much less specifically std::size_t? And, if so, how would you deduce such an unsigned integral type? - Jeff
On Wed, Oct 19, 2011 at 4:22 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
Sounds like a very weak reason. Especially since: If an instance of iterator_range is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end).
If that's the rationale, it'd be better to add is_valid() or so.
What are the requirements on an iterator's difference_type, exactly?
I don't know.
Specifically, are you even guaranteed that it is always convertible to *some* unsigned integral type, much less specifically std::size_t? And, if so, how would you deduce such an unsigned integral type?
Good questions. But I don't think I know the answer. However, given a valid range, end() - begin() can't be negative. Right? Most other size() return an unsigned type. Returning a signed type results in signed/unsigned mismatches. Olaf
On Wednesday, October 19, 2011 16:44:25 Olaf van der Spek wrote:
On Wed, Oct 19, 2011 at 4:22 PM, Jeffrey Lee Hellrung, Jr.
<jeffrey.hellrung@gmail.com> wrote:
Sounds like a very weak reason. Especially since: If an instance of iterator_range is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end).
If that's the rationale, it'd be better to add is_valid() or so.
What are the requirements on an iterator's difference_type, exactly?
I don't know.
Specifically, are you even guaranteed that it is always convertible to *some* unsigned integral type, much less specifically std::size_t? And, if so, how would you deduce such an unsigned integral type?
Good questions. But I don't think I know the answer. However, given a valid range, end() - begin() can't be negative. Right? Most other size() return an unsigned type. Returning a signed type results in signed/unsigned mismatches.
There are some points in the Standard, like this for instance (24.2.1/1): ... For every iterator type X for which equality is defined, there is a corresponding signed integer type called the difference type of the iterator. However, that's not really relevant, because there is no requirement that size() returns the difference type. Obtaining size type from difference type is quite doable with type traits such as make_unsigned.
Olaf wrote on Wednesday, October 19, 2011 at 1:30:03:
Hi,
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
given two arbitrary valid random access iterators (from one range) let you know the distance between them it is either positive or negative (or 0) dependent on the order of the given iterators i'd say difference type should be ptrdiff_t in the general case -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
On Wed, Oct 19, 2011 at 7:01 PM, pavel <paul.cpprules@gmail.com> wrote:
Olaf wrote on Wednesday, October 19, 2011 at 1:30:03:
Hi,
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
given two arbitrary valid random access iterators (from one range) let you know the distance between them
it is either positive or negative (or 0) dependent on the order of the given iterators
i'd say difference type should be ptrdiff_t in the general case
We're not talking about difference_type. We're talking about the return type of size(). Olaf
Olaf wrote on Wednesday, October 19, 2011 at 21:03:25:
On Wed, Oct 19, 2011 at 7:01 PM, pavel <paul.cpprules@gmail.com> wrote:
Olaf wrote on Wednesday, October 19, 2011 at 1:30:03:
Hi,
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
given two arbitrary valid random access iterators (from one range) let you know the distance between them
it is either positive or negative (or 0) dependent on the order of the given iterators
i'd say difference type should be ptrdiff_t in the general case
We're not talking about difference_type. We're talking about the return type of size().
Olaf
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
sorry, i misread the initial message if the definition of size is how many times one need to ++begin to reach end then it's clearly must be something like size_t but if size is (end - begin) for random access iterators it well may be a signed integer, e.g. ptrdiff_t -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
On Thu, Oct 20, 2011 at 8:15 PM, pavel <paul.cpprules@gmail.com> wrote:
sorry, i misread the initial message
if the definition of size is how many times one need to ++begin to reach end then it's clearly must be something like size_t
but if size is (end - begin) for random access iterators it well may be a signed integer, e.g. ptrdiff_t
Why? Are you trying to imply end - begin can be negative for a valid range? Olaf
Olaf wrote on Friday, October 21, 2011 at 0:34:29:
On Thu, Oct 20, 2011 at 8:15 PM, pavel <paul.cpprules@gmail.com> wrote:
sorry, i misread the initial message
if the definition of size is how many times one need to ++begin to reach end then it's clearly must be something like size_t
but if size is (end - begin) for random access iterators it well may be a signed integer, e.g. ptrdiff_t
Why? Are you trying to imply end - begin can be negative for a valid range?
its natural for me that the result of (rand_iter - rand_iter) is returned without type conversion, which is a signed integer so, to convert or not to convert to unsigned is then the user's responsibility but if you state that in any way size() is the number of (++begin)'s to reach end, then regardless of the implementation it may return size_t (involving type conversion in case of random access iterators) it's mere a "politics" question, a matter of definition of size() -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
On Fri, Oct 21, 2011 at 4:57 PM, pavel <paul.cpprules@gmail.com> wrote:
Olaf wrote on Friday, October 21, 2011 at 0:34:29:
On Thu, Oct 20, 2011 at 8:15 PM, pavel <paul.cpprules@gmail.com> wrote:
sorry, i misread the initial message
if the definition of size is how many times one need to ++begin to reach end then it's clearly must be something like size_t
but if size is (end - begin) for random access iterators it well may be a signed integer, e.g. ptrdiff_t
Why? Are you trying to imply end - begin can be negative for a valid range?
its natural for me that the result of (rand_iter - rand_iter) is returned without type conversion, which is a signed integer
Isn't that just an implementation detail? The interface should not be driven by implementation details.
so, to convert or not to convert to unsigned is then the user's responsibility
but if you state that in any way size() is the number of (++begin)'s to reach end, then regardless of the implementation it may return size_t (involving type conversion in case of random access iterators)
it's mere a "politics" question, a matter of definition of size()
-- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Olaf
On Tuesday, October 18, 2011 23:30:03 Olaf van der Spek wrote:
Hi,
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
+1 I too stumbled upon this more than once. The common understanding of a valid range is that end() must be reachable by incrementing begin() finite times. Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
On Wed, Oct 19, 2011 at 11:38 AM, <andrey.semashev@gmail.com> wrote:
On Tuesday, October 18, 2011 23:30:03 Olaf van der Spek wrote:
Hi,
iterator_range returns a signed size. Is this correct? IMO it should return size_t.
+1
I too stumbled upon this more than once. The common understanding of a valid range is that end() must be reachable by incrementing begin() finite times. Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
How would that be possible? Doesn't that violate the conditions on difference_type that it is able to represent the (signed) distance between any two iterators within the same range? Also, assuming that size() should return an unsigned integer type (I'm not debating the merits of this), *what* unsigned integer type should that be? I don't know of any general way to go from difference_type to a "compatible" unsigned integer type. I suspect this will end up being filed away as "nice to have but ultimately unimplementable generically" given current range interfaces. - Jeff
On Wednesday, October 19, 2011 11:50:06 Jeffrey Lee Hellrung, Jr. wrote:
Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
How would that be possible? Doesn't that violate the conditions on difference_type that it is able to represent the (signed) distance between any two iterators within the same range?
That is only true for random access iterators. See std::distance reference (24.4.4/4): Effects: If InputIterator meets the requirements of random access iterator, returns (last - first); otherwise, returns the number of increments needed to get from first to last. So bidirectional iterators, for instance, may denote a valid range that exceeds difference_type capacity. This is actually a little caveat in the Standard.
Also, assuming that size() should return an unsigned integer type (I'm not debating the merits of this), *what* unsigned integer type should that be? I don't know of any general way to go from difference_type to a "compatible" unsigned integer type. I suspect this will end up being filed away as "nice to have but ultimately unimplementable generically" given current range interfaces.
I think the following would do: typedef typename make_unsigned< difference_type >::type size_type;
On Wed, Oct 19, 2011 at 12:09 PM, <andrey.semashev@gmail.com> wrote:
On Wednesday, October 19, 2011 11:50:06 Jeffrey Lee Hellrung, Jr. wrote:
Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
How would that be possible? Doesn't that violate the conditions on difference_type that it is able to represent the (signed) distance between any two iterators within the same range?
That is only true for random access iterators. See std::distance reference (24.4.4/4):
Effects: If InputIterator meets the requirements of random access iterator, returns (last - first); otherwise, returns the number of increments needed to get from first to last.
So bidirectional iterators, for instance, may denote a valid range that exceeds difference_type capacity. This is actually a little caveat in the Standard.
A bit surprising, but I'll take your word for it. In any case, it's some irrelevant for non-random-access iterators as iterator_range::size() is only defined for random access iterators, no?
Also, assuming that size() should return an unsigned integer type (I'm not debating the merits of this), *what* unsigned integer type should that be? I don't know of any general way to go from difference_type to a "compatible" unsigned integer type. I suspect this will end up being filed away as "nice to have but ultimately unimplementable generically" given current range interfaces.
I think the following would do:
typedef typename make_unsigned< difference_type >::type size_type;
I was under the impression that most of the traits in Boost.TypeTraits of this nature are only defined for builtin types. - Jeff
On Wednesday, October 19, 2011 12:27:31 Jeffrey Lee Hellrung, Jr. wrote:
So bidirectional iterators, for instance, may denote a valid range that exceeds difference_type capacity. This is actually a little caveat in the Standard.
A bit surprising, but I'll take your word for it. In any case, it's some irrelevant for non-random-access iterators as iterator_range::size() is only defined for random access iterators, no?
No, iterator_range can be used with any iterators.
I think the following would do: typedef typename make_unsigned< difference_type >::type size_type;
I was under the impression that most of the traits in Boost.TypeTraits of this nature are only defined for builtin types.
See one of my previous replies, difference type should be a signed integer type.
On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev@gmail.com> wrote:
On Wednesday, October 19, 2011 12:27:31 Jeffrey Lee Hellrung, Jr. wrote:
[...]
I think the following would do: typedef typename make_unsigned< difference_type >::type size_type;
I was under the impression that most of the traits in Boost.TypeTraits of this nature are only defined for builtin types.
See one of my previous replies, difference type should be a signed integer type.
Ah, indeed. Then I agree make_unsigned would be a legitimate solution. - Jeff
Jeffrey Lee Hellrung, Jr. wrote:
On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev@gmail.com> wrote:
On Wednesday, October 19, 2011 12:27:31 Jeffrey Lee Hellrung, Jr. wrote:
[...]
I think the following would do: typedef typename make_unsigned< difference_type >::type size_type;
I was under the impression that most of the traits in Boost.TypeTraits of this nature are only defined for builtin types.
See one of my previous replies, difference type should be a signed integer type.
Ah, indeed. Then I agree make_unsigned would be a legitimate solution.
This will break if difference_type is a UDT without a make_unsigned specialization. Is that a good idea? Bo Persson
On Thu, Oct 20, 2011 at 8:32 AM, Bo Persson <bop@gmb.dk> wrote:
Jeffrey Lee Hellrung, Jr. wrote:
On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev@gmail.com> wrote:
On Wednesday, October 19, 2011 12:27:31 Jeffrey Lee Hellrung, Jr. wrote:
[...]
I think the following would do: typedef typename make_unsigned< difference_type >::type size_type;
I was under the impression that most of the traits in Boost.TypeTraits of this nature are only defined for builtin types.
See one of my previous replies, difference type should be a signed integer type.
Ah, indeed. Then I agree make_unsigned would be a legitimate solution.
This will break if difference_type is a UDT without a make_unsigned specialization.
Is that a good idea?
The wording of the standard says that difference_type is a "signed integer type", seeming to imply that it shouldn't be a UDT. - Jeff
On Wednesday, October 19, 2011 12:27:31 Jeffrey Lee Hellrung, Jr. wrote:
In any case, it's some irrelevant for non-random-access iterators as iterator_range::size() is only defined for random access iterators, no?
Sorry, I was a bit hasty in my previous reply. Yes, I'm surprised to say that iterator_range::size() is implemented for random access iterators only. Nevertheless, there's still no reason to make its return type signed.
On Wednesday, October 19, 2011 21:34:58 Olaf van der Spek wrote:
On Wed, Oct 19, 2011 at 9:09 PM, <andrey.semashev@gmail.com> wrote:
So bidirectional iterators, for instance, may denote a valid range that exceeds difference_type capacity. This is actually a little caveat in the Standard.
Is the type of std::distance unspecified then?
It's specified as difference_type. However the returned value of std::distance for this case is not covered by the Standard, AFAICT.
On Wed, Oct 19, 2011 at 8:50 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
I too stumbled upon this more than once. The common understanding of a valid range is that end() must be reachable by incrementing begin() finite times. Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
How would that be possible? Doesn't that violate the conditions on difference_type that it is able to represent the (signed) distance between any two iterators within the same range?
Also, assuming that size() should return an unsigned integer type (I'm not debating the merits of this), *what* unsigned integer type should that be?
How about using make_unsigned from type_traits?
I don't know of any general way to go from difference_type to a "compatible" unsigned integer type. I suspect this will end up being filed away as "nice to have but ultimately unimplementable generically" given current range interfaces.
Isn't this problem caused by iterator_traits missing size_type? What would the problem be of just using std::size_t? -- Olaf
On Wed, Oct 19, 2011 at 12:21 PM, Olaf van der Spek <ml@vdspek.org> wrote:
On Wed, Oct 19, 2011 at 8:50 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
I too stumbled upon this more than once. The common understanding of a valid range is that end() must be reachable by incrementing begin() finite times. Making the size signed makes little sense to me and it also introduces a problem (rather theoretical, however) when iterator_range is constructed from a very large valid range, whose size exceeds numeric_limits<difference_type>::max().
How would that be possible? Doesn't that violate the conditions on difference_type that it is able to represent the (signed) distance between any two iterators within the same range?
Also, assuming that size() should return an unsigned integer type (I'm not debating the merits of this), *what* unsigned integer type should that be?
How about using make_unsigned from type_traits?
See my reply to Andrey. Note that I'm not confident that make_unsigned *wouldn't* work, necessarily.
I don't know of any general way to go from difference_type to a "compatible"
unsigned integer type. I suspect this will end up being filed away as "nice to have but ultimately unimplementable generically" given current range interfaces.
Isn't this problem caused by iterator_traits missing size_type?
Yes. Changing iterator_traits (specifically, the collection of types associated with an iterator) is where I'm leaning, if you really want an unsigned iterator_range::size().
What would the problem be of just using std::size_t?
Well, likewise, what would be the problem of always using std::ptrdiff_t for difference_type? And, aside from whether std::size_t would be wide enough, I don't think there are any requirements that std::size_t be constructable from difference_type. - Jeff
On Wed, Oct 19, 2011 at 9:31 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
Yes. Changing iterator_traits (specifically, the collection of types associated with an iterator) is where I'm leaning, if you really want an unsigned iterator_range::size().
If you've got another / better solution for the signed/unsigned mismatches that result from a signed size() I'd be happy to hear it from you.
What would the problem be of just using std::size_t?
Well, likewise, what would be the problem of always using std::ptrdiff_t for difference_type? And, aside from whether std::size_t would be wide enough,
How is difference_type relevant?
I don't think there are any requirements that std::size_t be constructable from difference_type.
-- Olaf
On Wed, Oct 19, 2011 at 12:40 PM, Olaf van der Spek <ml@vdspek.org> wrote:
On Wed, Oct 19, 2011 at 9:31 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
Yes. Changing iterator_traits (specifically, the collection of types associated with an iterator) is where I'm leaning, if you really want an unsigned iterator_range::size().
If you've got another / better solution for the signed/unsigned mismatches that result from a signed size() I'd be happy to hear it from you.
I don't, and, indeed, I wasn't aware that difference_type was restricted to be a builtin signed integral type. So make_unsigned seems to work.
What would the problem be of just using std::size_t?
Well, likewise, what would be the problem of always using std::ptrdiff_t for difference_type? And, aside from whether std::size_t would be wide enough,
How is difference_type relevant?
I was just making an analogy... Honestly, I'd be surprised if there were any practical problems with using std::size_t, but likewise I'd be surprised if there were any practical problems with always using std::ptrdiff_t for difference_type. - Jeff
On Wed, Oct 19, 2011 at 10:29 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
How is difference_type relevant?
I was just making an analogy... Honestly, I'd be surprised if there were
Ah
any practical problems with using std::size_t, but likewise I'd be surprised if there were any practical problems with always using std::ptrdiff_t for difference_type.
Probably not, but as there's iterator_traits<>::difference_type, there's no need to always use std::ptrdiff_t. Maybe size_type should be added in TR2? :p Olaf
On Wednesday, October 19, 2011 21:21:00 Olaf van der Spek wrote:
On Wed, Oct 19, 2011 at 8:50 PM, Jeffrey Lee Hellrung, Jr.
Isn't this problem caused by iterator_traits missing size_type?
Well, the lack of size_type is rather understandable since iterators are not ranges and there's nothing to be sized with an iterator. An unsigned distance_type would be more expected though. But what's more important, std::distance in that case could be formulated the similar way for all iterator types (i.e. returns the number of increments required for begin to reach the end).
What would the problem be of just using std::size_t?
In 99% of cases I assume this would suffice. But I'd still prefer a make_unsigned-synthesized type.
participants (6)
-
andrey.semashev＠gmail.com -
Bo Persson -
Jeffrey Lee Hellrung, Jr. -
Olaf van der Spek -
pavel -
Rhys Ulerich