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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 1:45 AM, Rhys Ulerich <rhys.ulerich <at> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 1:46 AM, Olaf van der Spek <ml <at> vdspek.org> wrote:
> On Wed, Oct 19, 2011 at 1:45 AM, Rhys Ulerich <rhys.ulerich <at> 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?
(Continue reading)On Wed, Oct 19, 2011 at 4:22 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung <at> 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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 <at> 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(Continue reading)
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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 7:01 PM, pavel <paul.cpprules <at> 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
Olaf wrote on Wednesday, October 19, 2011 at 21:03:25: > On Wed, Oct 19, 2011 at 7:01 PM, pavel <paul.cpprules <at> 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(Continue reading)
On Thu, Oct 20, 2011 at 8:15 PM, pavel <paul.cpprules <at> 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Olaf wrote on Friday, October 21, 2011 at 0:34:29: > On Thu, Oct 20, 2011 at 8:15 PM, pavel <paul.cpprules <at> 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(Continue reading)
On Fri, Oct 21, 2011 at 4:57 PM, pavel <paul.cpprules <at> 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 <at> 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() > > --(Continue reading)
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(). _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 11:38 AM, <andrey.semashev <at> 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.(Continue reading)
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:(Continue reading)
On Wed, Oct 19, 2011 at 12:09 PM, <andrey.semashev <at> 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?(Continue reading)
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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev <at> 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Jeffrey Lee Hellrung, Jr. wrote: > On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev <at> 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(Continue reading)
On Thu, Oct 20, 2011 at 8:32 AM, Bo Persson <bop <at> gmb.dk> wrote: > Jeffrey Lee Hellrung, Jr. wrote: > > On Wed, Oct 19, 2011 at 12:38 PM, <andrey.semashev <at> 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?(Continue reading)
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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 9:09 PM, <andrey.semashev <at> 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? Olaf _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wednesday, October 19, 2011 21:34:58 Olaf van der Spek wrote: > On Wed, Oct 19, 2011 at 9:09 PM, <andrey.semashev <at> 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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 8:50 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung <at> 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? -- --(Continue reading)
On Wed, Oct 19, 2011 at 12:21 PM, Olaf van der Spek <ml <at> vdspek.org> wrote: > On Wed, Oct 19, 2011 at 8:50 PM, Jeffrey Lee Hellrung, Jr. > <jeffrey.hellrung <at> 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.(Continue reading)
On Wed, Oct 19, 2011 at 9:31 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung <at> 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 19, 2011 at 12:40 PM, Olaf van der Spek <ml <at> vdspek.org> wrote: > On Wed, Oct 19, 2011 at 9:31 PM, Jeffrey Lee Hellrung, Jr. > <jeffrey.hellrung <at> 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(Continue reading)
On Wed, Oct 19, 2011 at 10:29 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung <at> 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RSS Feed