473,892 Members | 1,443 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Bidirectional iterators: signed distance?

As an intellectual exercise, I've implemented an STL-esque List<and
List<>::Iterato r. 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.e nd(),
list.begin()), I would get -list.size(). The STL's iterator distance
function amounts to something like this:

distance_type distance(Iterat or 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(i 4, 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(Iterat or 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 butt-ugly 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

Sep 5 '07 #1
9 2328
no************* *******@hotmail .com wrote:
As an intellectual exercise, I've implemented an STL-esque List<and
List<>::Iterato r. 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.e nd(),
list.begin()), I would get -list.size(). The STL's iterator distance
function amounts to something like this:

distance_type distance(Iterat or 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(i 4, 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(Iterat or 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 butt-ugly 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 e-mail
I do not respond to top-posted replies, please don't ask
Sep 5 '07 #2
Find the distance from each of the iterators to the beginning and
then subtract.
Ah, seems obvious now :)

Thanks.

Sep 5 '07 #3
no************* *******@hotmail .com wrote in
news:11******** **************@ r34g2000hsd.goo glegroups.com:
As an intellectual exercise, I've implemented an STL-esque List<and
List<>::Iterato r. 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.e nd(),
list.begin()), I would get -list.size(). The STL's iterator distance
function amounts to something like this:

distance_type distance(Iterat or 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(i 4, 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(Iterat or 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 butt-ugly 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_f rom_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
Sep 5 '07 #4
Victor Bazarov wrote:
no************* *******@hotmail .com wrote:
>As an intellectual exercise, I've implemented an STL-esque List<and
List<>::Iterat or. 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.e nd(),
list.begin() ), I would get -list.size(). The STL's iterator distance
function amounts to something like this:

distance_typ e distance(Iterat or 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(i 4, 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(Iterat or 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 butt-ugly and I don't like the constant checking for
tmp==end(). Can anyone think of a nicer way to implement this
functionalit y? 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
Sep 5 '07 #5
Joe Greer wrote:
no************* *******@hotmail .com wrote in
news:11******** **************@ r34g2000hsd.goo glegroups.com:
>As an intellectual exercise, I've implemented an STL-esque List<and
List<>::Iterat or. 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.e nd(),
list.begin() ), I would get -list.size(). The STL's iterator distance
function amounts to something like this:

distance_typ e distance(Iterat or 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(i 4,
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(Iterat or 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 butt-ugly and I don't like the constant checking for
tmp==end(). Can anyone think of a nicer way to implement this
functionalit y? 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_f rom_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
Mark P wrote:
Victor Bazarov wrote:
>no************* *******@hotmail .com wrote:
>>As an intellectual exercise, I've implemented an STL-esque List<>
and List<>::Iterato r. 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.e nd(),
list.begin()) , I would get -list.size(). The STL's iterator
distance function amounts to something like this:

distance_ty pe distance(Iterat or 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(i 4,
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(Iterat or 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 butt-ugly 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 Big-O 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 e-mail
I do not respond to top-posted replies, please don't ask
Sep 5 '07 #7
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(Iter ator 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
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<>::Iterato r. 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.e nd(),
list.begin() ), I would get -list.size(). The STL's iterator
distance function amounts to something like this:

distance_typ e distance(Iterat or 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(i 4,
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(Iterat or 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 butt-ugly and I don't like the constant checking for
tmp==end() . Can anyone think of a nicer way to implement this
functionalit y? 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 Big-O 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 big-Oh, 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
Sep 5 '07 #9
"Victor Bazarov" <v.********@com Acast.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
Sep 6 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
4009
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, but only those based upon lists. I need reverse iteration for TreeSet!!!! My algorithm searches the sorted set and looks for clustering of values. Implementing this with only a forward iterator is a ridiculous amount of extra work.
2
2388
by: Ney André de Mello Zunino | last post by:
Hello. A non-modifying algorithm I implemented uses two associative containers from STL: set and map. The elements on those containers are supposed to refer to actual elements which lie on another, bigger container. I had the definition of my auxiliary containers based on pointers, but considered using iterators instead. I know iterators might become invalid upon certain operations, but as I said, the algorithm is non-modifying. This...
4
22192
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
0
2258
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 return a foundAt iterator that points to the location in question, but distance() still always returns zero. However reading a chunk of file into a vector and searching the vector produces an iterator that distance() will measure properly. Evidently , it is not possible to measure the distance ...
4
2322
by: fastback66 | last post by:
Evidently per the C++ standard, it is not possible to measure the distance between two stream iterators, because two non-end-of-stream iterators are equal when they are constructed from the same stream. I still don't quite understand why that fact is true. But... I wish to find the first occurance of some sequence in an existing stream. For the moment this stream is a file on disk, but later may be a stream from another process. Anyway,...
8
2450
by: Mateusz Łoskot | last post by:
Hi, I know iterator categories as presented by many authors: Stroustrup, Josuttis and Koenig&Moo: Input <---| |<--- Forward <--- Bidirectional <--- Random Output <---|
19
7571
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 iterators. In theory, a red black tree can do this in O(log K) time. Anyone knows if there is a way to do this in map<> or if map<> can be inherited/modified to do this? Thanks, --j
19
2139
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 problems cropping up in the code thanks to this change. a) With pointer-iterators you could set an iterator to null to mark it as invalid, you can't do that any more. b) You can't use const_cast with iterators.
5
2229
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 bound from the multimap, and having these two iterators I would like to sample one element with uniform distribution. It a way do to this using iterators? I can of course draw an integer and loop over the sequence until I meet the drawn value, but it is not a very nice solution. Can sample...
0
9981
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11241
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10926
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10468
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9644
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
8018
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7172
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5857
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
3
3288
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.