435,425 Members | 2,549 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,425 IT Pros & Developers. It's quick & easy.

Bidirectional iterators: signed distance?

 P: n/a As an intellectual exercise, I've implemented an STL-esque List::Iterator. Now, I would like a signed distance between two iterators which corresponds to their relative position in the list. For instance, if I did something like distance(list.end(), list.begin()), I would get -list.size(). The STL's iterator distance function amounts to something like this: distance_type distance(Iterator first, Iterator last) { distance_type n = 0; while (first != last) { ++first; ++n; } return n; } So, if my list has ten elements, and i4 is an iterator at the 4th node and i2 is an iterator at the 2nd node, then std::distance(i4, i2) is 9. That's meaningless to me. What I want is distance(i4, i2) == -2. So I implemented distance as a method of List
9 Replies

 P: n/a no********************@hotmail.com wrote: As an intellectual exercise, I've implemented an STL-esque List::Iterator. Now, I would like a signed distance between two iterators which corresponds to their relative position in the list. For instance, if I did something like distance(list.end(), list.begin()), I would get -list.size(). The STL's iterator distance function amounts to something like this: distance_type distance(Iterator first, Iterator last) { distance_type n = 0; while (first != last) { ++first; ++n; } return n; } So, if my list has ten elements, and i4 is an iterator at the 4th node and i2 is an iterator at the 2nd node, then std::distance(i4, i2) is 9. That's meaningless to me. What I want is distance(i4, i2) == -2. So I implemented distance as a method of List

 P: n/a Find the distance from each of the iterators to the beginning and then subtract. Ah, seems obvious now :) Thanks. Sep 5 '07 #3

 P: n/a no********************@hotmail.com wrote in news:11**********************@r34g2000hsd.googlegr oups.com: As an intellectual exercise, I've implemented an STL-esque List::Iterator. Now, I would like a signed distance between two iterators which corresponds to their relative position in the list. For instance, if I did something like distance(list.end(), list.begin()), I would get -list.size(). The STL's iterator distance function amounts to something like this: distance_type distance(Iterator first, Iterator last) { distance_type n = 0; while (first != last) { ++first; ++n; } return n; } So, if my list has ten elements, and i4 is an iterator at the 4th node and i2 is an iterator at the 2nd node, then std::distance(i4, i2) is 9. That's meaningless to me. What I want is distance(i4, i2) == -2. So I implemented distance as a method of List

 P: n/a Victor Bazarov wrote: no********************@hotmail.com wrote: >As an intellectual exercise, I've implemented an STL-esque List::Iterator. Now, I would like a signed distance between twoiterators which corresponds to their relative position in the list.For instance, if I did something like distance(list.end(),list.begin()), I would get -list.size(). The STL's iterator distancefunction amounts to something like this:distance_type distance(Iterator first, Iterator last){ distance_type n = 0; while (first != last) { ++first; ++n; } return n;}So, if my list has ten elements, and i4 is an iterator at the 4th nodeand i2 is an iterator at the 2nd node, then std::distance(i4, i2) is9. That's meaningless to me. What I want is distance(i4, i2) == -2.So I implemented distance as a method of List

 P: n/a Joe Greer wrote: no********************@hotmail.com wrote in news:11**********************@r34g2000hsd.googlegr oups.com: >As an intellectual exercise, I've implemented an STL-esque List::Iterator. Now, I would like a signed distance between twoiterators which corresponds to their relative position in the list.For instance, if I did something like distance(list.end(),list.begin()), I would get -list.size(). The STL's iterator distancefunction amounts to something like this:distance_type distance(Iterator first, Iterator last){ distance_type n = 0; while (first != last) { ++first; ++n; } return n;}So, if my list has ten elements, and i4 is an iterator at the 4thnode and i2 is an iterator at the 2nd node, then std::distance(i4,i2) is9. That's meaningless to me. What I want is distance(i4, i2) == -2.So I implemented distance as a method of List for (Iterator it = i; it != begin() && it !=j; --it, --d); if (it !=j) throw iterators_not_from_same_list(); return d; Actually the second loop is better in terms of 'i' and 'j' reversed: d = 0; // did you forget this? for (Iterator it = j; it != end(); ++it, --d) { if (it == i) return d; } throw iterators_not ... I've not tried to run this code, but it should mostly do what you want and I think it's reasonably clear. Of course, Victor's solution is cleaner, but will always pay the cost of counting to each of the iterators. How it is actually used will determine which mechanism is better. joe V -- Please remove capital 'A's when replying by e-mail I do not respond to top-posted replies, please don't ask Sep 5 '07 #6

 P: n/a Mark P wrote: Victor Bazarov wrote: >no********************@hotmail.com wrote: >>As an intellectual exercise, I've implemented an STL-esque List<>and List<>::Iterator. Now, I would like a signed distance betweentwo iterators which corresponds to their relative position in thelist. For instance, if I did something like distance(list.end(),list.begin()), I would get -list.size(). The STL's iteratordistance function amounts to something like this:distance_type distance(Iterator first, Iterator last){ distance_type n = 0; while (first != last) { ++first; ++n; } return n;}So, if my list has ten elements, and i4 is an iterator at the 4thnode and i2 is an iterator at the 2nd node, then std::distance(i4,i2) is 9. That's meaningless to me. What I want is distance(i4, i2) ==-2. So I implemented distance as a method of List

 P: n/a If you incorporate the comparison and return into the loop body, it would be just a tad faster, I believe: int d = 0; for (Iterator it = i; it != end(); ++it, ++d) { if (it == j) return d; } d = 0; // did you forget this? for (Iterator it = j; it != end(); ++it, --d) { if (it == i) return d; } Actually, this code breaks when i or j == end(). I decided on the following: int difference(Iterator i, Iterator j) { int d = 0; Iterator it = i; for ( ; it!=j && it!=end(); ++it, ++d); if (it == j) return d; d = 0; for (it=j; it!=i; ++it, --d); return d; } I'm saving a comparison in the second loop under the assumption that i and j are from the same container. I think that's fair. Thanks everybody for your input! Sep 5 '07 #8

 P: n/a Victor Bazarov wrote: Mark P wrote: >Victor Bazarov wrote: >>no********************@hotmail.com wrote:As an intellectual exercise, I've implemented an STL-esque List<>and List<>::Iterator. Now, I would like a signed distance betweentwo iterators which corresponds to their relative position in thelist. For instance, if I did something like distance(list.end(),list.begin()), I would get -list.size(). The STL's iteratordistance function amounts to something like this:distance_type distance(Iterator first, Iterator last){ distance_type n = 0; while (first != last) { ++first; ++n; } return n;}So, if my list has ten elements, and i4 is an iterator at the 4thnode and i2 is an iterator at the 2nd node, then std::distance(i4,i2) is 9. That's meaningless to me. What I want is distance(i4, i2) ==-2. So I implemented distance as a method of List

 P: n/a "Victor Bazarov" d = 0; // did you forget this? Yep, I sure did. (I did say that I didn't actually run it. :) ) It just shows that I shouldn't do coding in a rush when posting. Thanks for correcting this. for (Iterator it = j; it != end(); ++it, --d) { if (it == i) return d; } throw iterators_not ... joe Sep 6 '07 #10

This discussion thread is closed

Replies have been disabled for this discussion. 