As an intellectual exercise, I've implemented an STLesque List<and
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<like so:
int distance(Iterator i, Iterator j)
{
Iterator tmp = i;
int d = 0;
while (tmp != j) {
if (tmp == end()) {
// oops, try the other way
tmp = i; d = 0;
while (tmp != j) {
tmp; d;
}
return d;
}
++tmp; ++d;
}
return d;
}
But this is buttugly and I don't like the constant checking for
tmp==end(). Can anyone think of a nicer way to implement this
functionality? Has it been done somewhere else that I can have a look
at?
Thanks 9 2189 no********************@hotmail.com wrote:
As an intellectual exercise, I've implemented an STLesque List<and
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<like so:
int distance(Iterator i, Iterator j)
{
Iterator tmp = i;
int d = 0;
while (tmp != j) {
if (tmp == end()) {
// oops, try the other way
tmp = i; d = 0;
while (tmp != j) {
tmp; d;
}
return d;
}
++tmp; ++d;
}
return d;
}
But this is buttugly and I don't like the constant checking for
tmp==end(). Can anyone think of a nicer way to implement this
functionality? Has it been done somewhere else that I can have a look
at?
Find the distance from each of the iterators to the beginning and
then subtract. I.e.
distance(a, b) == distance(begin(), b)  distance(begin(), a)
V

Please remove capital 'A's when replying by email
I do not respond to topposted replies, please don't ask
Find the distance from each of the iterators to the beginning and
then subtract.
Ah, seems obvious now :)
Thanks. no********************@hotmail.com wrote in
news:11**********************@r34g2000hsd.googlegr oups.com:
As an intellectual exercise, I've implemented an STLesque List<and
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<like so:
int distance(Iterator i, Iterator j)
{
Iterator tmp = i;
int d = 0;
while (tmp != j) {
if (tmp == end()) {
// oops, try the other way
tmp = i; d = 0;
while (tmp != j) {
tmp; d;
}
return d;
}
++tmp; ++d;
}
return d;
}
But this is buttugly and I don't like the constant checking for
tmp==end(). Can anyone think of a nicer way to implement this
functionality? Has it been done somewhere else that I can have a look
at?
I would break this up into two loops and do some more checking than you
do.
I would start with:
int d = 0;
for (Iterator it = i; it != j && it != end(); ++it, ++d);
if (it == j)
return d;
for (Iterator it = i; it != begin() && it !=j; it, d);
if (it !=j)
throw iterators_not_from_same_list();
return d;
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
Victor Bazarov wrote:
no********************@hotmail.com wrote:
>As an intellectual exercise, I've implemented an STLesque List<and 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<like so:
int distance(Iterator i, Iterator j) { Iterator tmp = i; int d = 0; while (tmp != j) { if (tmp == end()) { // oops, try the other way tmp = i; d = 0; while (tmp != j) { tmp; d; } return d; } ++tmp; ++d; } return d; }
But this is buttugly and I don't like the constant checking for tmp==end(). Can anyone think of a nicer way to implement this functionality? Has it been done somewhere else that I can have a look at?
Find the distance from each of the iterators to the beginning and
then subtract. I.e.
distance(a, b) == distance(begin(), b)  distance(begin(), a)
V
Nothing wrong with this solution but of course the worst case
performance is O(n) where n is the length of the list. You can achieve
O(d), where d is the distance between the two iterators, if you
alternately advance the two iterators until one reaches the original
position of the other. Naturally this won't be as compact as Victor's
solution.
Mark
Joe Greer wrote:
no********************@hotmail.com wrote in
news:11**********************@r34g2000hsd.googlegr oups.com:
>As an intellectual exercise, I've implemented an STLesque List<and 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<like so:
int distance(Iterator i, Iterator j) { Iterator tmp = i; int d = 0; while (tmp != j) { if (tmp == end()) { // oops, try the other way tmp = i; d = 0; while (tmp != j) { tmp; d; } return d; } ++tmp; ++d; } return d; }
But this is buttugly and I don't like the constant checking for tmp==end(). Can anyone think of a nicer way to implement this functionality? Has it been done somewhere else that I can have a look at?
I would break this up into two loops and do some more checking than
you do.
I would start with:
int d = 0;
for (Iterator it = i; it != j && it != end(); ++it, ++d);
if (it == j)
return d;
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;
}
>
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 email
I do not respond to topposted replies, please don't ask
Mark P wrote:
Victor Bazarov wrote:
>no********************@hotmail.com wrote:
>>As an intellectual exercise, I've implemented an STLesque List<> and 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<like so:
int distance(Iterator i, Iterator j) { Iterator tmp = i; int d = 0; while (tmp != j) { if (tmp == end()) { // oops, try the other way tmp = i; d = 0; while (tmp != j) { tmp; d; } return d; } ++tmp; ++d; } return d; }
But this is buttugly and I don't like the constant checking for tmp==end(). Can anyone think of a nicer way to implement this functionality? Has it been done somewhere else that I can have a look at?
Find the distance from each of the iterators to the beginning and then subtract. I.e.
distance(a, b) == distance(begin(), b)  distance(begin(), a)
V
Nothing wrong with this solution but of course the worst case
performance is O(n) where n is the length of the list. You can
achieve O(d), where d is the distance between the two iterators, if
you alternately advance the two iterators until one reaches the
original position of the other. Naturally this won't be as compact
as Victor's solution.
I am by no means the master of the BigO notation, but it seems that
O(n) and O(d) are the same terms. The worst case scenario with my
original suggestion is when 'a'=='end()' && 'b'=='end()'. Then the
number of comparisons is 2*N. The worst case scenario with counting
in both directions is when 'a'=='end()' && 'b'=='begin()', i.e. the
distance is N, in which case the number of comparisons is N, still.
So, you get about 50% savings on iterator comparisons with going in
two directions.
V

Please remove capital 'A's when replying by email
I do not respond to topposted replies, please don't ask
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!
Victor Bazarov wrote:
Mark P wrote:
>Victor Bazarov wrote:
>>no********************@hotmail.com wrote: As an intellectual exercise, I've implemented an STLesque List<> and 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<like so:
int distance(Iterator i, Iterator j) { Iterator tmp = i; int d = 0; while (tmp != j) { if (tmp == end()) { // oops, try the other way tmp = i; d = 0; while (tmp != j) { tmp; d; } return d; } ++tmp; ++d; } return d; }
But this is buttugly and I don't like the constant checking for tmp==end(). Can anyone think of a nicer way to implement this functionality? Has it been done somewhere else that I can have a look at? Find the distance from each of the iterators to the beginning and then subtract. I.e.
distance(a, b) == distance(begin(), b)  distance(begin(), a)
V
Nothing wrong with this solution but of course the worst case performance is O(n) where n is the length of the list. You can achieve O(d), where d is the distance between the two iterators, if you alternately advance the two iterators until one reaches the original position of the other. Naturally this won't be as compact as Victor's solution.
I am by no means the master of the BigO notation, but it seems that
O(n) and O(d) are the same terms. The worst case scenario with my
original suggestion is when 'a'=='end()' && 'b'=='end()'. Then the
number of comparisons is 2*N. The worst case scenario with counting
in both directions is when 'a'=='end()' && 'b'=='begin()', i.e. the
distance is N, in which case the number of comparisons is N, still.
So, you get about 50% savings on iterator comparisons with going in
two directions.
This is true, but this is simply a reflection of the fact that d can be
as large as n. The flip side of the coin is that d may be much less
than n, which is where my algorithm pays off.
Turning first to the subject of bigOh, one can be creative with the
terms used within these expressions. I could have "done you a favor"
and declared your algorithm to be O( distance( begin, a) + distance(
begin, b)) which is arguably better than O(n). But while this is
mathematically true, it's probably not very interesting. (Though it
could be if one is working in a regime where one expects the iterators
to typically point to the beginning of the list.)
However it's fairly conventional to specify to complexity in terms of
input size and output size (or value), which is why I draw the
distinction between O(n) and O(d). For example, a good algorithm for
determining all intersection points between n segments in the plane has
complexity O(n lg n + k) where k is the number of intersection points.
Yet if one only references the input size, one would have to quote the
complexity as O(n^2) since, in the worst case, there can be n^2
intersections between n segments. But this obscures the fact that the
algorithm is in fact much more clever than simple brute force pairwise
testing of all segments, which is also O(n^2).
Still your question underscores an important point, namely that what
makes an algorithm good depends very much on the context in which it
will be applied (which in turn dictates how one should characterize the
complexity).
Returning to the linked lists, here's another way to look at it.
Observe that my algorithm "dominates" yours in the sense that, for all
inputs, my run time is always less than a constant multiple of your run
time. However your run time is not always less than *any* constant
multiple of my run time. This is not surprising since d <= n and d
may be smaller than n by an arbitrarily large factor.
Mark
"Victor Bazarov" <v.********@comAcast.netwrote in news:fb**********@news.datemas.de:
>
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Wiseguy 
last post by:
It seems very short sighted and silly that the bidirectional capabilities
of ListIterator have not been implemented for collections based upon sets,...

by: Ney André de Mello Zunino 
last post by:
Hello.
A nonmodifying algorithm I implemented uses two associative containers
from STL: set and map. The elements on those containers are...

by: pmatos 
last post by:
Hi all,
How can I compute the size of vector<int> given iterators to it. Can I
do :
int size = itEnd  itBegin;
???
Cheers,
Paulo Matos

by: gary_dr 
last post by:
What's so special about istream_iterator that prevents me from determining the distance between two of them.
In the code below, search() does...

by: fastback66 
last post by:
Evidently per the C++ standard, it is not possible to measure the
distance between two stream iterators, because two nonendofstream
iterators...

by: Mateusz Ĺoskot 
last post by:
Hi,
I know iterator categories as presented
by many authors: Stroustrup, Josuttis and Koenig&Moo:
Input <
< Forward <...

by: John 
last post by:
In STL's map implementation, the distance between two
iterators it1, it2 takes O(K) to compute where K is the
actual distance between the two...

by: fungus 
last post by:
I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of...

by: Leon 
last post by:
using
multimap<int,int>::iterator itlow = pq.lower_bound (x);
multimap<int,int>::iterator itup = pq.upper_bound (y);
I obtain lower and upper...

by: concettolabs 
last post by:
In today's business world, businesses are increasingly turning to PowerApps to develop custom business applications. PowerApps is a powerful tool...

by: better678 
last post by:
Question:
Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct?
Answer:
Java is an objectoriented...

by: teenabhardwaj 
last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...

by: Kemmylinns12 
last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...

by: Naresh1 
last post by:
What is WebLogic Admin Training?
WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...

by: jalbright99669 
last post by:
Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made...

by: AndyPSV 
last post by:
HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable...

by: WisdomUfot 
last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific...

by: Matthew3360 
last post by:
Hi,
I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web...
 