null or nil or initialised std::list iterator?

[sandwich_eater]

I want to know how to set an std::list iterator variable to make it
null or nil. If this is not possible what is the value of an
uninitialised std::list iterator and is it ok to assign this value to a
std::list iterator variable (or is it better to use a seperate bool
variable as a "null flag" ?)

e.g.
struct mystru
{
std::string nm;
int qty;
}

std::list<mystru>::iterator i;

// what is the value of i ?
....
i = somelist.begin();
// do things with i
....
i = NULL_VALUE?

 

[Alipha]

I want to know how to set an std::list iterator variable to make it
null or nil. If this is not possible what is the value of an
uninitialised std::list iterator and is it ok to assign this value to a
std::list iterator variable (or is it better to use a seperate bool
variable as a "null flag" ?)

e.g.
struct mystru
{
std::string nm;
int qty;
}

std::list<mystru>::iterator i;

// what is the value of i ?

unspecified. you CAN'T use i without giving it a value

...
i = somelist.begin();
// do things with i
...
i = NULL_VALUE?

i = somelist.end(); // the end iterator of a container is one-past the
end of the container

 

[sandwich_eater]

unspecified. you CAN'T use i without giving it a value

I think that is the point, I want to know when it does not
have a value or does that count as using it too?

what about iterator(NULL) ?

 

[Marc Mutz]

I think that is the point, I want to know when it does
not have a value or does that count as using it too?

what about iterator(NULL) ?

Use a pointer to iterator, set it to 0 to signal absence.
iterators don't have a Null State.

Marc

 

[Andrew Koenig]

I want to know how to set an std::list iterator variable to make it
null or nil.

You can't.

If this is not possible what is the value of an
uninitialised std::list iterator and is it ok to assign this value to a
std::list iterator variable (or is it better to use a seperate bool
variable as a "null flag" ?)

If you try to copy an uninitialized std::list iterator, the effect is
undefined.

Here's one way to do what I think you want:

std::list<T> marker;
marker.push_back(T());

Now you have a list named marker that has a single element.

The value of marker.begin() is therefore an iterator that refers to that
element. No other iterator will ever be equal to that value.

So you can write

std::list<T>::iterator nulliterator = marker.begin();

and then use the value of nulliterator as if it were a null iterator.

You will have to repeat this process for each distinct type T you intend to
use. Of course you can use templates to simplify this repetition.

 

[Pete Becker]

I think that is the point, I want to know when it does not
have a value or does that count as using it too?

what about iterator(NULL) ?

Nope. Learn the iterator idioms: a pair of iterators designates a range
of values. Lone iterators aren't very useful.

What is the actual problem that you're trying to solve?

 

[sandwich_eater]

Use a pointer to iterator, set it to 0 to signal absence.

iterators don't have a Null State.

Thanks for your help, although not the answer I wanted to hear.
That is so annoying, I am going to rant now. Lots of algorithms that
use lists, graphs, trees etc are implemented with "nil" or "null"
pointer states thus avoiding source code clutter. Who designed these
delicate STL iterators anyway? In many cases I guess it would be
better to use a traditional pointer based implementation instead of the
STL.

 

[sandwich_eater]

I want to store a reference to a std::list node.

 

[sandwich_eater]

... that could be null.

 

[Ivan Vecerina]

I want to store a reference to a std::list node.
.. that could be null.

Then you may use a pointer to the list node - not an iterator.

Ivan

 

[sandwich_eater]

Then you may use a pointer to the list node - not an iterator.

But how do I do that, isnt the node implementation hidden from me.

 

[Ivan Vecerina]

But how do I do that, isnt the node implementation hidden from me.

Any iterator can be converted to a pointer by taking the address
of the dereferenced iterator. Given (based on your OP):
std::list<mystru>::iterator i = ...;
the address of the item pointed to by 'i' can be obtained with:
mystru* p = &*i; // or &(*i) if you prefer

Of course, you cannot use p to iterate through the container,
and you cannot (easily) convert it back to an iterator.
But this solution is the easiest if you only need to later
access that one item.

Cheers, Ivan

 

[sandwich_eater]

Looking at the algorithm I would want to convert it back. Now I
realise I should be using a graph instead of a double linked list
because I need a custom pointer as well as "next".

 

[Pete Becker]

I want to store a reference to a std::list node.

That's not the actual problem, it's your attempt at a solution. Pop up a
level and talk about what your code is supposed to do, rather than how
it tries to do it. Why do you need to store a possibly null reference to
a list node?

Ultimately, if you're fighting with the design of the library that
you're using, you need to either change the approach that you're taking
or change the library.

 

[Ivan Vecerina]

Looking at the algorithm I would want to convert it back. Now I
realise I should be using a graph instead of a double linked list
because I need a custom pointer as well as "next".

Note: as a courtesy to others, please quote relevant parts of
the post you are replying -- to provide context.

If you only have one collection of items, the end() iterator
is the invalid value you are looking for. Additionally,
Andrew Koenig has provided a solution if you really need an
'invalid' iterator independent of a container instance.

But as it appears you are not sure what container you should
be using, you should consider describing the algorithm that
you are trying to implement. This will allow others to provide
high-level advice instead of answers to naively focused
questions.

Cheers,
Ivan

 

[cipherpunk]

Using "nil" to denote "nothing left" is an implementation detail. C++
has a different implementation, usually .end().

STL iterators are hardly delicate. I often find myself wishing other
languages supported C++-style iterators.

As an example of how to turn a nil-terminated list algorithm into a
..end()-terminated list algorithm, I submit a (reimplementation) of the
classic merge algorithm, compared to an SML/NJ version.

===== SML/NJ merge algorithm =====
fun merge(x::xs, y::ys) = if (x < y) then x::merge(xs, y::ys) else
y::merge(x::xs, ys) |
merge(nil, y::ys) = y::ys |
merge(x::xs, nil) = x::xs |
merge(nil, nil) = nil;
===== end SML/NJ =====


===== Full C++ for a merge example =====
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <list>

using std::cout;
using std::endl;
using std::copy;
using std:stream_iterator;
using std::vector;
using std::list;
using std::back_inserter;

template <typename T1, typename T2, typename T3>
void my_merge(T1 begin1, T1 end1, T2 begin2, T2 end2, T3 copy_to)
{
while (begin1 != end1 and begin2 != end2) {
if (*begin1 < *begin2)
*copy_to++ = *begin1++;
else
*copy_to++ = *begin2++;
}
if (begin1 != end1)
copy(begin1, end1, copy_to);
if (begin2 != end2)
copy(begin2, end2, copy_to);
}

int main(void)
{
const int FOO[] = { 0, 2, 4, 6 };
const int BAR[] = { 1, 3, 5, 7 };
vector<int> foo(FOO, FOO + 4);
list<int> bar(BAR, BAR + 4);
vector<int> result;
my_merge(foo.begin(), foo.end(), bar.begin(), bar.end(),
back_inserter(result));
copy(result.begin(), result.end(), ostream_iterator<int>(cout, "\t"));
cout << endl;
return 0;
}
===== end C++ =====


.... As you can tell, it's the same algorithm in both instances. The
differences are purely in implementation, not in conception. That's
good news for you, because implementation differences are almost always
surmountable. Conceptual differences are much, much harder.