Cheers!

Following scenario: I have a nested list of vectors of Foos[1]. I want to
have an iterator with which I can access all Foos as a sequence. What I'd
like to confirm is that I didn't miss anything in my solution, because I'm
not sure if I really need the third iterator (but I can't seem to find a
way to do without it ...).

Up to now, I have basically the following:

class foo_iterator:
   methods:
     operator++();
   data:
     list::iterator lit;
     list::iterator lit_end;
     vector::iterator vit;

'lit_end' points to the end of the list while 'lit' and 'vit' are normal
iterators to the current position. The method for incrementing an iterator
looks like this:

foo_iterator::operator++():
     ++vit;
     if(vit == lit->end)
         ++lit;
         if(lit!=lit_end)
             vit=lit->begin;

Here was the first time I needed 'lit_end' because I must not dereference
'lit' when it reaches the end but need to set 'vit' to the beginning of the
next element otherwise.

The function for comparing iterators looks like this:

bool operator=(foo_iterator it1, foo_iterator it2):
     // if the two iterators are not from the same sequence they
     // are different [2]
     if(it1.lit_end != it2.lit_end)
         return false;
     // if the current position in the list differs they are different
     if(it1.lit != it2.lit)
         return false;
     // if both positions in the list are at the end (and we know that
     // either both or none of them are) they are equal
     if(it1.lit == it1.lit_end)
         return true;
     // the only possible difference is in the position inside the vector
     return (it1.vit == it2.vit);

Here again, I had to add a special case for the end-iterator because it has
an undefined 'vit'.

The only other way to solve this problem that I could think of was to have a
flag whether 'vit' is valid and only evaluate it in comparisons if that
flag is set and set 'vit' to 'lit->begin' on demand when the foo_iterator
is dereferenced. That solution however requires a test on each
dereferenciation and mutable 'vit' and valid-flag.

Does anyone have a better solution to this problem ?

thank you,
Ulrich Eckhardt

[1] the exact container-types should not matter

[2] writing this, I started wondering how iterators of the stdlib compare
when they come from different containers. Undefined? Container-specific?
Unequal?


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Ulrich Eckhardt" <doomster@knuut.de> wrote in message
news:bgm2ck$q09i1$1@ID-178288.news.uni-berlin.de...
| Following scenario: I have a nested list of vectors of Foos[1]. I 
want to
| have an iterator with which I can access all Foos as a sequence. What 
I'd
| like to confirm is that I didn't miss anything in my solution, 
because I'm
| not sure if I really need the third iterator (but I can't seem to 
find a
| way to do without it ...).
|
| Up to now, I have basically the following:
|
| class foo_iterator:
|    methods:
|      operator++();
|    data:
|      list::iterator lit;
|      list::iterator lit_end;
|      vector::iterator vit;

Let me try to discard lit_end...

| 'lit_end' points to the end of the list while 'lit' and 'vit' are 
normal
| iterators to the current position. The method for incrementing an 
iterator
| looks like this:
|
| foo_iterator::operator++():
|      ++vit;
|      if(vit == lit->end)
|          ++lit;
|          if(lit!=lit_end)
|              vit=lit->begin;

Note that there is a potential bug here: this code seems to
assume that none of the vectors in the list is empty.
Can this assumption be made?

| Here was the first time I needed 'lit_end' because I must not 
dereference
| 'lit' when it reaches the end but need to set 'vit' to the beginning 
of
the
| next element otherwise.

What about postponing the testing of vit==lit->end() until
the iterator is actually dereferenced ?


foo_iterator::operator++():
   if( vit == lit->end() ) // use a 'while()' if a vector may be empty
      vit = (++lit)->begin();
   ++vit;
   return *this;

foo_iterator::operator*():
   if( vit == lit->end() ) // same thing, small overhead...
      vit = (++lit)->begin();
   return *vit;


But now the tricky iterator comparison:

The following would be a nice trick, but leads to
undefined behavior if either a or b is the end iterator:
   return &*a == &*b;

Here's an alternative approach that should work
if the list does not contain any empty vectors:

I will rely on this small utility:
   lit_t successor( lit_t it ) { return ++it; }

bool operator==(a,b):
   if( a.lit == b.lit )
     return a.vit == b.vit;

   if(         a.vit==a.lit->begin()  )
     return    b.vit==b.lit->end()
            && successor(b.lit)==a.lit;

   return      b.vit==b.lit->begin()
            && a.vit==a.lit->end()
            && successor(a.lit)==b.lit;

The 'lit' stored in an iterator is never the end(),
so calls to 'successor' will not lead to undefined behavior.

There is a limitation with this last function though:
If the list can contain empty vectors, the 'successor'
function needs to test if a vector is empty and increment
again -- but this is an illegal operation if the end
of the list has been reached.
AFAICT, it cannot be made to support this situation...

| Does anyone have a better solution to this problem ?

Let me know if the above seems suitable...
Of course, storing the additional list iterator probably
isn't less efficient.

| [2] writing this, I started wondering how iterators of the stdlib 
compare
| when they come from different containers. Undefined? 
Container-specific?
| Unequal?

For iterator ordering ( <, <=, >, >= ), the behavior is definitely
undefined, as it is with pointers that do not point within the same
array.

For equality ( == , != ), I would still say undefined. For example,
an iterator to end() may be common to all containers (e.g. a NULL
pointer, or a default-initialized iterator such as istream_iterator),
while other iterators will not.
If the iterators are known to point to valid objects, comparing
the object addresses instead can be a useful alternative.


Well, I hope this helps,
Ivan

-- 
Ivan Vecerina           <>  http://www.post1.com/~ivec
Brainbench MVP for C++  <>  http://www.brainbench.com

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Hello, Ulrich Eckhardt!

Ulrich Eckhardt schrieb:

> Cheers!
>
> Following scenario: I have a nested list of vectors of Foos[1]. I want 
> to
> have an iterator with which I can access all Foos as a sequence. What 
> I'd
> like to confirm is that I didn't miss anything in my solution, because 
> I'm
> not sure if I really need the third iterator (but I can't seem to find 
> a
> way to do without it ...).

Question: I am not sure concerning the "nested" list of vectors: Do you 
mean a
std::list<std::vector<Foo> > ??
The following discussion depends on this assumption.

And answering on your final point [2]: The requirements on comparisons 
among
iterators of
containers are just a specific case of those on comparisons among 
general
iterators, which are
explained in Chapter 24. One specific requirement is the fact, that two
iterators must be
reachable. This is generally not guaranteed for two independent 
containers:
24.1/p. 6:
"An iterator j is called reachable from an iterator i if and only if 
there is a
finite sequence of applications of
the expression ++i that makes i == j. If j is reachable from i, they 
refer to
the same container."
So, the corresponding behaviour is undefined.

And my general advice for your specific problem is: You could consider 
to take
advantage of
your knowledge concerning the general container types your foo iterator 
is
acting on, because a
container provides much more information concerning the actual sequence 
than the
iterators
themselves. Since you are traversing on an iterator of iterators, and a 
single
iterator is not selfdescribing
the sequence it is acting on, you have to store the end iterator of the 
list in
your example or you use
other member functions of the referenced list to get the same 
information.

> Up to now, I have basically the following:
>
> class foo_iterator:
>    methods:
>      operator++();
>    data:
>      list::iterator lit;
>      list::iterator lit_end;
>      vector::iterator vit;
>
> 'lit_end' points to the end of the list while 'lit' and 'vit' are 
> normal
> iterators to the current position. The method for incrementing an 
> iterator
> looks like this:
>
> foo_iterator::operator++():

>
>      ++vit;
>      if(vit == lit->end)
>          ++lit;
>          if(lit!=lit_end)
>              vit=lit->begin;
>
> Here was the first time I needed 'lit_end' because I must not 
> dereference
> 'lit' when it reaches the end but need to set 'vit' to the beginning 
> of the
> next element otherwise.
>

Probably you mean:

      ++vit;
      while(vit == lit->end() && ++lit != lit_end) { // This ensures, 
that you
skip all empty vectors
          vit=lit->begin();
     }


>
> The function for comparing iterators looks like this:
>
> bool operator=(foo_iterator it1, foo_iterator it2):

bool operator==(foo_iterator it1, foo_iterator it2) ;-))

>
>      // if the two iterators are not from the same sequence they
>      // are different [2]
>      if(it1.lit_end != it2.lit_end)
>          return false;

This test is unnecessary since it is UB to compare non-reachable
iterators.

>
>      // if the current position in the list differs they are different
>      if(it1.lit != it2.lit)
>          return false;
>      // if both positions in the list are at the end (and we know that
>      // either both or none of them are) they are equal
>      if(it1.lit == it1.lit_end)
>          return true;

This test is unnecessary since the position of vit should be defined. 
It is
either equal to the last vector<Foo>::end() or has its initial value 
(whatever
it is)

>
>      // the only possible difference is in the position inside the 
> vector
>      return (it1.vit == it2.vit);
>
> Here again, I had to add a special case for the end-iterator because 
> it has
> an undefined 'vit'.
>
> The only other way to solve this problem that I could think of was to 
> have a
> flag whether 'vit' is valid and only evaluate it in comparisons if that
> flag is set and set 'vit' to 'lit->begin' on demand when the 
> foo_iterator
> is dereferenced. That solution however requires a test on each
> dereferenciation and mutable 'vit' and valid-flag.
>

You don't need this test for validity. You just have to ensure, that 
vit is
always initialized
with a defined value. You can at least use the default-constructed 
iterator,
which should
be done like:

vit = std::vector<Foo>::iterator();

during assignement or

vit(std::vector<Foo>::iterator())

during initialization.

This calls the default constructor and works even in case of pointer 
iterators
implementations
of std::vector (quite often found), since it evaluates to the null 
pointer
constant in this case.

Hope that helps,

Daniel


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Daniel Spangenberg" <dsp@bdal.de> wrote in message
news:3F2FC258.F8C7C27A@bdal.de...
.....
> You don't need this test for validity. You just have to ensure, that
> vit is
> always initialized
> with a defined value. You can at least use the default-constructed
> iterator, which should be done like:
>
> vit = std::vector<Foo>::iterator();
>
> during assignement or
>
> vit(std::vector<Foo>::iterator())
>
> during initialization.
>
> This calls the default constructor and works even in case of pointer
> iterators implementations
> of std::vector (quite often found), since it evaluates to the null
> pointer constant in this case.

Question: are default-constructed iterators guaranteed
          to compare equal ?

..... or could a default constructor chose to not care,
    and leave fields uninitialized even though they may
    be involved in a comparison ?


Regards,
Ivan
-- 
http://www.post1.com/~ivec



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Ivan Vecerina" <ivecATmyrealboxDOTcom@swissonline.ch> wrote in message 
news:<3f31593b@news.swissonline.ch>...

{unnecessary quote snipped -mod/fwg}

 >
 > Question: are default-constructed iterators guaranteed
 >           to compare equal ?

No.  See 24.1/5.  All we are allowed to do with an uninitialized
iterator is to assign a value to it.

 >
 > .... or could a default constructor chose to not care,
 >     and leave fields uninitialized even though they may
 >     be involved in a comparison ?

Yes, this could certainly be the case since such a comparison is not
allowed.

Randy.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Daniel Spangenberg wrote:
 > Ulrich Eckhardt schrieb:
 >> Following scenario: I have a nested list of vectors of Foos[1]. I want
 >> to have an iterator with which I can access all Foos as a sequence. What
 >> I'd like to confirm is that I didn't miss anything in my solution,
 >> because I'm not sure if I really need the third iterator (but I can't
 >> seem to find a way to do without it ...).
 >
 > Question: I am not sure concerning the "nested" list of vectors: Do you
 > mean a std::list<std::vector<Foo> > ??
 > The following discussion depends on this assumption.

Your assumption was right, I meant basically container<container<foo> >, any
ones from the stdlib.

 >> foo_iterator::operator++():
 >>
 >>      ++vit;
 >>      if(vit == lit->end)
 >>          ++lit;
 >>          if(lit!=lit_end)
 >>              vit=lit->begin;
 >>
 >> Here was the first time I needed 'lit_end' because I must not
 >> dereference 'lit' when it reaches the end but need to set 'vit' to the
 >> beginning of the next element otherwise.
 >>
 >
 > Probably you mean:
 >
 >       ++vit;
 >       while(vit == lit->end() && ++lit != lit_end) { // This ensures,
 > that you
 > skip all empty vectors
 >           vit=lit->begin();
 >      }

*slaps himself*
Yes, thanks for pointing it out. I do not have empty vectors usually, but
just last week we had some nice bughunting just because an empty one
slipped by ....

 > bool operator==(foo_iterator it1, foo_iterator it2) ;-))
 >
 >>
 >>      // if the two iterators are not from the same sequence they
 >>      // are different [2]
 >>      if(it1.lit_end != it2.lit_end)
 >>          return false;
 >
 > This test is unnecessary since it is UB to compare non-reachable
 > iterators.

OK. It possibly merits an assert.

 >>
 >>      // if the current position in the list differs they are different
 >>      if(it1.lit != it2.lit)
 >>          return false;
 >>      // if both positions in the list are at the end (and we know that
 >>      // either both or none of them are) they are equal
 >>      if(it1.lit == it1.lit_end)
 >>          return true;
 >
 > This test is unnecessary since the position of vit should be defined.
 > It is either equal to the last vector<Foo>::end() or has its initial
 > value (whatever it is)

Setting it to the last vector's end() wont work if there is no such thing
(i.e. the list is empty).

  The only way to 'create' a value for it would be to set it like 'vit =
vector::iterator()'. However, I'm not sure that that wont lead to UB again.
Can I 'assert(iterator()==iterator())' ?

Uli


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]