Comparing an iterator to a NULL value

[andreas]

Hello,

I have a problem with iterators in a fairly complex polygonal mesh data
structure which is implemented using lists of geometric entities.
However, the problem in itself is fairly simple:

I need to define special iterator values. In particular, I want a null
iterator. This is different from end() which means the end of this
list. I want an iterator value that is known to just not correspond to
any element. It must be possible to compare using == and != and, of
course, this special value must be invariant to changes to the data
structure.

Say the type is

list<int>

and my special iterator is NULL_INT_LIST_ITERATOR

I want to compare like this

a == NULL_INT_LIST_ITERATOR

and this comparison should return true only if a has previously been
assigned my null value. Previously, I did this using

----------------------------------------------
typedef list<int>::iterator IntIter;
IntIter NULL_INT_LIST_ITER(0);
----------------------------------------------

This just defines an iterator with an internal null pointer. That works
fine in g++ but it is not documented that it should work. Arguably it
is ugly. A different solution is this

----------------------------------------------
inline IntIter get_null_int_iter()
{
static list<int> l;
return l.end();
}
#define NULL_INT_LIST_ITER get_null_int_iter()
-----------------------------------------------

However, this solution does not work in recent version of Microsoft
visual studio. The reason *appears* to be that when I compare this
iterator value to a different iterator value it is detected that
NULL_INT_LIST_ITER belongs to a different list.

It seems you can make it work by defining HAS_ITERATOR_DEBUGGING=0.
However, the program still does not work - but possibly for different
reasons.

If you have a better solution, I'd be grateful to hear about it.

Thanks

Andreas

[Stefan Näwe]

andreas wrote:

Hello,

I have a problem with iterators in a fairly complex polygonal mesh data
structure which is implemented using lists of geometric entities.
However, the problem in itself is fairly simple:

I need to define special iterator values. In particular, I want a null
iterator. This is different from end() which means the end of this
list. I want an iterator value that is known to just not correspond to
any element. It must be possible to compare using == and != and, of
course, this special value must be invariant to changes to the data
structure.

Say the type is

list<int>

and my special iterator is NULL_INT_LIST_ITERATOR

I want to compare like this

a == NULL_INT_LIST_ITERATOR

Why would one want to do BS like that?

Compare your iterator to yourlist.end() and nothing else. PERIOD.
/S
--
Stefan Naewe
naewe.s_AT_atlas_DOT_de

[Victor Bazarov]

andreas wrote:

I need to define special iterator values. In particular, I want a null
iterator. This is different from end() which means the end of this
list. I want an iterator value that is known to just not correspond to
any element. It must be possible to compare using == and != and, of
course, this special value must be invariant to changes to the data
structure.
[...]

Could you try to justify why you need that thing?

An iterator serves a particular purpose: to iterate. So, as such, it
should always be initialised (to the beginning of the sequence), used
(by increment, usually), and then discarded when the sequence is exhausted
(and that's determined by comparing the iterator to 'end()'). If you just
need to identify something in a collection, you're allowed to keep any
pointers, references, sometimes indices. Those can become invalid, but so
can iterators. IOW, I am unclear what you're going to accomplish by
letting iterators to become "NULL". Perhaps if you explain what problem
you're trying to solve, we could suggest a better solution...

V

[peter steiner]

andreas wrote:

Hello,

I have a problem with iterators in a fairly complex polygonal mesh data
structure which is implemented using lists of geometric entities.
However, the problem in itself is fairly simple:

I need to define special iterator values. In particular, I want a null
iterator. This is different from end() which means the end of this
list. I want an iterator value that is known to just not correspond to
any element. It must be possible to compare using == and != and, of
course, this special value must be invariant to changes to the data
structure.

Say the type is

list<int>

and my special iterator is NULL_INT_LIST_ITERATOR

I want to compare like this

a == NULL_INT_LIST_ITERATOR

and this comparison should return true only if a has previously been
assigned my null value. Previously, I did this using

----------------------------------------------
typedef list<int>::iterator IntIter;
IntIter NULL_INT_LIST_ITER(0);
----------------------------------------------

This just defines an iterator with an internal null pointer. That works
fine in g++ but it is not documented that it should work. Arguably it
is ugly.
yes, and definitely not portable. the standard does not guarantee any
iterator constructors besides default and copy initializers. for
non-trivial iterators, positions are only meant to be assigned
internally by the corresponding container class functions.
A different solution is this

----------------------------------------------
inline IntIter get_null_int_iter()
{
static list<int> l;
return l.end();
}
#define NULL_INT_LIST_ITER get_null_int_iter()
-----------------------------------------------

However, this solution does not work in recent version of Microsoft
visual studio. The reason *appears* to be that when I compare this
iterator value to a different iterator value it is detected that
NULL_INT_LIST_ITER belongs to a different list.

It seems you can make it work by defining HAS_ITERATOR_DEBUGGING=0.
However, the program still does not work - but possibly for different
reasons.
i would not rely on the result of comparing iterators from different
container instances. the standard is unclear in that regard. besides,
HAS_ITERATOR_DEBUGGING is your friend :)

If you have a better solution, I'd be grateful to hear about it.

wrap the standard iterators in your own iterator class with support for
the additional state if you want to implement this at iterator level.
the required interface is pretty simple.

i would recommend to use boost::iterator, which provides helpers to
create fully standard compliant iterators in very short time.

see http://boost.org/libs/iterator/doc/index.html

-- peter

[andreas]

Hello,

wrap the standard iterators in your own iterator class with support for
the additional state if you want to implement this at iterator level.
the required interface is pretty simple.

i would recommend to use boost::iterator, which provides helpers to
create fully standard compliant iterators in very short time.

see http://boost.org/libs/iterator/doc/index.html

That might be a good solution. The only thing that detracts is the fact
that added state will make the custom iterators larger, but that might
be a necessary evil.

Meanwhile, it seems that some of you find my use of the STL slightly
frivolous :-), so I'll explain why I need this unusual construct.

I have three types (Face, HalfEdge, Vertex) and corresponding lists of
objects belonging to these classes.

A HalfEdge needs iterators to elements in the Vertex and Face and even
HalfEdge lists (the last also required an unusual but quite portable
template construct). It must be iterators, because I need to be able to
remove, say, a Face list element indicated by an iterator in an element
of the halfedge list.

(Digression: That is also why I do not use vectors instead of lists. It
would simplify a number of things, and I could use index values of -1
to indicate a NULL element. However, you know the problems with random
deletion and vectors.)

Now, the face iterator stored in a halfedge does not always correspond
to a valid face. The data structure is for polygonal meshes, and it is
quite possible to have holes which are indicated by an iterator in the
halfedge being set to NULL_FACE_ITER.

Ok. So arguably I might be caught up in thinking in terms of pointers,
and I could of course simply add state to the halfedge class to
indicate that it is a boundary halfedge whose face is not defined.
It would however add some code here and there and make the data
structure fatter.

Solution number 2 would be to add this state to custom iterators. That
solution might indeed be prettier. However, if all iterators grow one
byte plus alignment, the data structure will really become a bit large
- after all the mesh can easily contain hundreds of thousands of faces,
edges and vertices.

At any rate, you all seem to suggest that I should solve the problem by
adding state, so that might well be what I end up doing.

Thanks so far :-)

Andreas

[andreas]

Hello,

wrap the standard iterators in your own iterator class with support for
the additional state if you want to implement this at iterator level.
the required interface is pretty simple.

i would recommend to use boost::iterator, which provides helpers to
create fully standard compliant iterators in very short time.

see http://boost.org/libs/iterator/doc/index.html

That might be a good solution. The only thing that detracts is the fact
that added state will make the custom iterators larger, but that might
be a necessary evil.

Meanwhile, it seems that some of you find my use of the STL slightly
frivolous :-), so I'll explain why I need this unusual construct.

I have three types (Face, HalfEdge, Vertex) and corresponding lists of
objects belonging to these classes.

A HalfEdge needs iterators to elements in the Vertex and Face and even
HalfEdge lists (the last also required an unusual but quite portable
template construct). It must be iterators, because I need to be able to
remove, say, a Face list element indicated by an iterator in an element
of the halfedge list.

(Digression: That is also why I do not use vectors instead of lists. It
would simplify a number of things, and I could use index values of -1
to indicate a NULL element. However, you know the problems with random
deletion and vectors.)

Now, the face iterator stored in a halfedge does not always correspond
to a valid face. The data structure is for polygonal meshes, and it is
quite possible to have holes which are indicated by an iterator in the
halfedge being set to NULL_FACE_ITER.

Ok. So arguably I might be caught up in thinking in terms of pointers,
and I could of course simply add state to the halfedge class to
indicate that it is a boundary halfedge whose face is not defined.
It would however add some code here and there and make the data
structure fatter.

Solution number 2 would be to add this state to custom iterators. That
solution might indeed be prettier. However, if all iterators grow one
byte plus alignment, the data structure will really become a bit large
- after all the mesh can easily contain hundreds of thousands of faces,
edges and vertices.

At any rate, you all seem to suggest that I should solve the problem by
adding state, so that might well be what I end up doing.

Thanks so far :-)

Andreas

[Victor Bazarov]

andreas wrote:

[...]
I have three types (Face, HalfEdge, Vertex) and corresponding lists of
objects belonging to these classes.

A HalfEdge needs iterators to elements in the Vertex and Face and even
HalfEdge lists (the last also required an unusual but quite portable
template construct). It must be iterators, because I need to be able to
remove, say, a Face list element indicated by an iterator in an element
of the halfedge list.
[..]
Now, the face iterator stored in a halfedge does not always correspond
to a valid face. The data structure is for polygonal meshes, and it is
quite possible to have holes which are indicated by an iterator in the
halfedge being set to NULL_FACE_ITER.
IIRC, the usual way is to actually have a valid face, and to designate it
as a _hole_. It makes for more consistent data structure and algorithms
become more straight-forward. This is OT, of course. You need to consult
with 'comp.graphics.algorithms' for more recommendations on how to manage
your topology better.
[..]

V

[Michiel.Salters]

andreas wrote:

Hello,

I have a problem with iterators in a fairly complex polygonal mesh data
structure which is implemented using lists of geometric entities.
However, the problem in itself is fairly simple:

I need to define special iterator values. In particular, I want a null
iterator. Previously, I did this using

----------------------------------------------
typedef list<int>::iterator IntIter;
IntIter NULL_INT_LIST_ITER(0);
----------------------------------------------

Try

typedef boost::optional<list<int>::iterator> IntIter;

HTH,
Michiel Salters