[utility] question on prior(x,n)
Consider: // A strange way to retrieve my_container.begin(): boost::prior( my_container.end(), my_container.size() ); Is that legal? The second template parameter of boost::prior is deduced to an unsigned(!) type, which IMHO means that -n is undefined, right? Do we need to fix this? Maybe: template <class T> T prior(T x, typename T::difference_type n) { std::advance(x, -n); return x; } or shall we document that it's illegal/undefined to call boost::prior() with an unsigned second parameter? Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey <daniel.frey@aixigo.de> writes:
Consider:
// A strange way to retrieve my_container.begin(): boost::prior( my_container.end(), my_container.size() );
Is that legal? The second template parameter of boost::prior is deduced to an unsigned(!) type, which IMHO means that -n is undefined, right? Do we need to fix this? Maybe:
template <class T> T prior(T x, typename T::difference_type n) { std::advance(x, -n); return x; }
Well, that wouldn't work! How would you call prior(p, 4) when p is int*?
or shall we document that it's illegal/undefined to call boost::prior() with an unsigned second parameter?
Hmm, no I think if it's unsigned we should either deduce an appropriate signed type or implement the "backward advance" ourselves. We could use reverse_iterator to do that, FWIW. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes: | Daniel Frey <daniel.frey@aixigo.de> writes: | | > Consider: | > | > // A strange way to retrieve my_container.begin(): | > boost::prior( my_container.end(), my_container.size() ); | > | > Is that legal? The second template parameter of boost::prior is | > deduced to an unsigned(!) type, which IMHO means that -n is undefined, | > right? Do we need to fix this? Maybe: | > | > template <class T> | > T prior(T x, typename T::difference_type n) | > { | > std::advance(x, -n); | > return x; | > } | | Well, that wouldn't work! | How would you call prior(p, 4) when p is int*? I suppose he wanted to say template<class T> T prior(T x, typename std::iterator_traits<T>::different_type n) ? | > or shall we document that it's illegal/undefined to call | > boost::prior() with an unsigned second parameter? | | Hmm, no I think if it's unsigned we should either deduce an | appropriate signed type or implement the "backward advance" | ourselves. We could use reverse_iterator to do that, FWIW. That would be an isomorphic implementation, indeed. -- Gaby
Gabriel Dos Reis wrote:
David Abrahams <dave@boost-consulting.com> writes:
| Daniel Frey <daniel.frey@aixigo.de> writes: | | > Consider: | > | > // A strange way to retrieve my_container.begin(): | > boost::prior( my_container.end(), my_container.size() ); | > | > Is that legal? The second template parameter of boost::prior is | > deduced to an unsigned(!) type, which IMHO means that -n is undefined, | > right? Do we need to fix this? Maybe: | > | > template <class T> | > T prior(T x, typename T::difference_type n) | > { | > std::advance(x, -n); | > return x; | > } | | Well, that wouldn't work! | How would you call prior(p, 4) when p is int*?
I suppose he wanted to say
template<class T> T prior(T x, typename std::iterator_traits<T>::different_type n)
?
You are obviously correct, thank you (But it's still difference_type, not different_type).
| > or shall we document that it's illegal/undefined to call | > boost::prior() with an unsigned second parameter? | | Hmm, no I think if it's unsigned we should either deduce an | appropriate signed type or implement the "backward advance" | ourselves. We could use reverse_iterator to do that, FWIW.
Should we propose std::regress (the counter-part for std::advance) for standardization (via a DR)? The current definition of std::advance seems to limit the number of elements that can be skipped backwards to signed types, but the container can be larger (OK, in theory, never tried it myself :). This would also nicely solve the implementation issue for us. Since then, the reverse_iterator implementation would be this: template <class T, class Distance> T prior(const T& x, Distance n) { return boost::next( std::reverse_iterator<T>(x), n ).base(); } right? Although I wonder what happens if T is already a reverse iterator. Is it legal to reverse a reverse_iterator? Or do we need a trait and implement both cases separately? Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Gabriel Dos Reis <gdr@integrable-solutions.net> writes:
David Abrahams <dave@boost-consulting.com> writes:
| Daniel Frey <daniel.frey@aixigo.de> writes: | | > Consider: | > | > // A strange way to retrieve my_container.begin(): | > boost::prior( my_container.end(), my_container.size() ); | > | > Is that legal? The second template parameter of boost::prior is | > deduced to an unsigned(!) type, which IMHO means that -n is undefined, | > right? Do we need to fix this? Maybe: | > | > template <class T> | > T prior(T x, typename T::difference_type n) | > { | > std::advance(x, -n); | > return x; | > } | | Well, that wouldn't work! | How would you call prior(p, 4) when p is int*?
I suppose he wanted to say
template<class T> T prior(T x, typename std::iterator_traits<T>::different_type n)
?
| > or shall we document that it's illegal/undefined to call | > boost::prior() with an unsigned second parameter? | | Hmm, no I think if it's unsigned we should either deduce an | appropriate signed type or implement the "backward advance" | ourselves. We could use reverse_iterator to do that, FWIW.
That would be an isomorphic implementation, indeed.
Hey! These implementations using "advance" don't work for non-iterators (e.g. int) the way regular next() and prior() do. I consider this a bug! -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes: | Hey! These implementations using "advance" don't work for | non-iterators (e.g. int) the way regular next() and prior() do. I | consider this a bug! You're right. (To Daniel: yes, I meant to write difference_type, but I can't type). -- Gaby
Gabriel Dos Reis wrote:
David Abrahams <dave@boost-consulting.com> writes:
| Hey! These implementations using "advance" don't work for | non-iterators (e.g. int) the way regular next() and prior() do. I | consider this a bug!
You're right.
I don't see any need to extend the legal use of next/prior to anything else than iterators. I considered the fact that it works/worked for non-iterators an accident as the documentation only speaks about iterators and never bothers to mention non-iterators. Thus, the bug is IMHO that it's not explicitly documented that next/prior's first argument must meet the interator requirements. Regards, Daniel (Gaby: Yes, it's bending the rules. So, agreed, I won't file a DR :) -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey <daniel.frey@aixigo.de> writes:
Gabriel Dos Reis wrote:
David Abrahams <dave@boost-consulting.com> writes: | Hey! These implementations using "advance" don't work for | non-iterators (e.g. int) the way regular next() and prior() do. I | consider this a bug! You're right.
I don't see any need to extend the legal use of next/prior to anything else than iterators.
It was already legal for non-iterators. What made you think otherwise?
I considered the fact that it works/worked for non-iterators an accident
It's not. I wrote it; I meant the spec to say what it says and not impose an iterator requirement.
as the documentation only speaks about iterators and never bothers to mention non-iterators. Thus, the bug is IMHO that it's not explicitly documented that next/prior's first argument must meet the interator requirements.
Sorry, dude, I get final say on original intent, since it was mine. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
I don't see any need to extend the legal use of next/prior to anything else than iterators.
It was already legal for non-iterators. What made you think otherwise?
The documentation and the way I was reading it :)
as the documentation only speaks about iterators and never bothers to mention non-iterators. Thus, the bug is IMHO that it's not explicitly documented that next/prior's first argument must meet the interator requirements.
Sorry, dude, I get final say on original intent, since it was mine.
Of course, but what's wrong with mentioning non-iterators explicitly? Or more generally writing down the requirements then? IIUC, you think that next/prior should work for all types that provide ++ and --, plus using + and - in cases where it's faster, right? (constant time complexity when possible, linear otherwise). Iterators being only one example of types that fulfill these requirements. Providing the implementation for next/prior in the documentation might be sufficient for the one-argument-version, but for the two argument version it's quite hard to help getting the implementation bug-free if I don't know what you intended. Can you write down original intent, please? Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey <daniel.frey@aixigo.de> writes:
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
I don't see any need to extend the legal use of next/prior to anything else than iterators. It was already legal for non-iterators. What made you think otherwise?
The documentation and the way I was reading it :)
as the documentation only speaks about iterators and never bothers to mention non-iterators. Thus, the bug is IMHO that it's not explicitly documented that next/prior's first argument must meet the interator requirements. Sorry, dude, I get final say on original intent, since it was mine.
Of course, but what's wrong with mentioning non-iterators explicitly?
Nothing's wrong with it; I just didn't happen to.
Or more generally writing down the requirements then?
The requirements are clearly implied by the specification of the function. This one is so simple that it's best to just show how it's implemented.
IIUC, you think that next/prior should work for all types that provide ++ and --, plus using + and - in cases where it's faster, right? (constant time complexity when possible, linear otherwise).
That would be best.
Iterators being only one example of types that fulfill these requirements.
Providing the implementation for next/prior in the documentation might be sufficient for the one-argument-version, but for the two argument version it's quite hard to help getting the implementation bug-free if I don't know what you intended. Can you write down original intent, please?
Well, you came up with the 2-arg version. I can only say that the original intent of the 1-arg versions was to operate on anything supporting prefix ++/--, respectively. If the 2-arg version won't do that, I guess we should change the name. Incidentally, it's almost always possible to detect whether the first argument supports operator += or operator-=. That might be a good way to decide whether to advance/regress it. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
Providing the implementation for next/prior in the documentation might be sufficient for the one-argument-version, but for the two argument version it's quite hard to help getting the implementation bug-free if I don't know what you intended. Can you write down original intent, please?
Well, you came up with the 2-arg version.
That was Daniel Wallin (too many Daniels error?). I guess this also explains why I had the feeling we were talking past each other a bit :)
I can only say that the original intent of the 1-arg versions was to operate on anything supporting prefix ++/--, respectively. If the 2-arg version won't do that, I guess we should change the name.
OK, I understand now that I have to distinguish the 1-arg version from the 2-arg version.
Incidentally, it's almost always possible to detect whether the first argument supports operator += or operator-=. That might be a good way to decide whether to advance/regress it.
If is_iterator yields false, this is good to distinguish the rest, yes. But the first question is, whether we want to enhance the 2-arg version of next/prior or if we simply rename them to e.g. advanced/regressed. I'd be happy with the latter. Comments? Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey wrote:
That was Daniel Wallin (too many Daniels error?).
Argh. It was Daniel Walker. #-P -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey wrote:
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
Providing the implementation for next/prior in the documentation might be sufficient for the one-argument-version, but for the two argument version it's quite hard to help getting the implementation bug-free if I don't know what you intended. Can you write down original intent, please?
Well, you came up with the 2-arg version.
That was Daniel Wallin (too many Daniels error?). I guess this also explains why I had the feeling we were talking past each other a bit :)
No it wasn't, must have been be some other Daniel. ;) -- Daniel Wallin
Daniel Frey <daniel.frey@aixigo.de> writes:
Incidentally, it's almost always possible to detect whether the first argument supports operator += or operator-=. That might be a good way to decide whether to advance/regress it.
If is_iterator yields false
There is no is_iterator trait AFAIK. And I wasn't suggesting that. I was suggesting something more like is_+=able and is_-=able traits.
this is good to distinguish the rest, yes. But the first question is, whether we want to enhance the 2-arg version of next/prior or if we simply rename them to e.g. advanced/regressed. I'd be happy with the latter. Comments?
I find those names rather awful for functions; no offense intended. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
Incidentally, it's almost always possible to detect whether the first argument supports operator += or operator-=. That might be a good way to decide whether to advance/regress it.
If is_iterator yields false
There is no is_iterator trait AFAIK. And I wasn't suggesting that. I was suggesting something more like is_+=able and is_-=able traits.
this is good to distinguish the rest,
Sorry, during shortening my previous mail before posting, one sentence got lost :) I was suggesting to add is_iterator, because if it yields true we should IMHO use std::advance. Only if it yields false, we should use your suggestion to distinguish +=able types from ++able types to use an efficient O(1)-implementation when possible, an O(n)-implementation otherwise.
yes. But the first question is, whether we want to enhance the 2-arg version of next/prior or if we simply rename them to e.g. advanced/regressed. I'd be happy with the latter. Comments?
I find those names rather awful for functions; no offense intended.
No problem, the names are not important. The important part is, whether we want to make the 2-arg version iterator-only. Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
Daniel Frey <daniel.frey@aixigo.de> writes:
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
Incidentally, it's almost always possible to detect whether the first argument supports operator += or operator-=. That might be a good way to decide whether to advance/regress it.
If is_iterator yields false There is no is_iterator trait AFAIK. And I wasn't suggesting that. I was suggesting something more like is_+=able and is_-=able traits.
this is good to distinguish the rest,
Sorry, during shortening my previous mail before posting, one sentence got lost :) I was suggesting to add is_iterator,
If you can figure out how to do that, you will be a hero to many.
because if it yields true we should IMHO use std::advance.
Why?
Only if it yields false, we should use your suggestion to distinguish +=able types from ++able types to use an efficient O(1)-implementation when possible, an O(n)-implementation otherwise.
yes. But the first question is, whether we want to enhance the 2-arg version of next/prior or if we simply rename them to e.g. advanced/regressed. I'd be happy with the latter. Comments? I find those names rather awful for functions; no offense intended.
No problem, the names are not important. The important part is, whether we want to make the 2-arg version iterator-only.
No, the names are important. The 2-arg version of a function with the same name shouldn't add major new restrictions on its inputs. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Daniel Frey <daniel.frey@aixigo.de> writes:
Consider:
// A strange way to retrieve my_container.begin(): boost::prior( my_container.end(), my_container.size() );
Is that legal? The second template parameter of boost::prior is deduced to an unsigned(!) type, which IMHO means that -n is undefined, right? Do we need to fix this? Maybe:
template <class T> T prior(T x, typename T::difference_type n) { std::advance(x, -n); return x; }
Well, that wouldn't work! How would you call prior(p, 4) when p is int*?
or shall we document that it's illegal/undefined to call boost::prior() with an unsigned second parameter?
Hmm, no I think if it's unsigned we should either deduce an appropriate signed type or implement the "backward advance" ourselves. We could use reverse_iterator to do that, FWIW.
template <class T> T prior(T x, ptrdiff_t n) would be fine (waves hand) if you ask me. (Blasphemy!! Burn him!)
Peter Dimov wrote:
template <class T> T prior(T x, ptrdiff_t n)
would be fine (waves hand) if you ask me. (Blasphemy!! Burn him!)
FWIW, I like it, too. Doesn't remove the range limitation implied by signed types, but it's the easiest solution until std::regress arrives :) Regards, Daniel -- Daniel Frey aixigo AG - financial solutions & technology Schloß-Rahe-Straße 15, 52072 Aachen, Germany fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
participants (6)
-
Daniel Frey -
Daniel Wallin -
David Abrahams -
Gabriel Dos Reis -
Peter Dimov