Implementing custom iterators

[Chris Schadl]

Hi,

I've written a simple sorted linked list class that I'm trying to
implement an iterator for. I'm trying to make the interface to the
iterator simmilar to the STL's iterator interface, so one could do:

SortedList<int> sl;
SortedList<int> ::iterator i;

for (i = sl.begin() ; i != sl.end() ; ++) { /* ... */ }

Right now I'm kind of stuck with the following code:

template <typename T>
class SortedList
{
private:
// To make life easier, our sorted list will be doubly-linked
struct ListNode {
ListNode *next;
ListNode *prev;

T data;

ListNode() { next = prev = NULL; }
} *head, *tail;

int size;

protected:
ListNode* _find(const T&) const;

public:
SortedList(); // Default constructor
SortedList(cons t SortedList&); // Copy constructor
virtual ~SortedList(); // Destructor

// ... Other methods (insert(), remove(), etc...

class _SortedListIter ator {
private:
ListNode *cur; // Current element in list
public:
_SortedListIter ator() : cur(NULL) { }
_SortedListIter ator(ListNode *pos) : cur(pos) { }
T& operator*();
void operator++(); // Prefix
void operator++(int) ;// Postfix

friend bool operator==(_Sor tedListIterator &, _SortedListIter ator&);
friend bool operator!=(_Sor tedListIterator &, _SortedListIter ator&);
};

typedef _SortedListIter ator iterator;

iterator begin() { iterator iter(head); return iter; }
iterator end() {iterator iter(NULL); return iter; }
};

Now, of course this dosen't even compile, but hopefully it kind of
illustrates what I'm trying to do. I'm not entierly certian if I should
declare _SotredListIter ator as a template class, or if I did so, how it
would effect the _SortedListIter ator typedef (AFAIK, typedef's cannot be
used with template typenames). Also, would I have establish friendship
between SortedList and _SortedListIter ator so _SortedListIter ator could
access SortedLists private members?

Thanks,

Chris Schadl

[Adriano Dal Bosco]

"Chris Schadl" <cs*****@satan. blah.org.uk> wrote in message
news:pa******** *************** *****@satan.bla h.org.uk...

Hi,

I've written a simple sorted linked list class that I'm trying to
implement an iterator for. I'm trying to make the interface to the
iterator simmilar to the STL's iterator interface, so one could do:

SortedList<int> sl;
SortedList<int> ::iterator i;

for (i = sl.begin() ; i != sl.end() ; ++) { /* ... */ }

Right now I'm kind of stuck with the following code:

template <typename T>
class SortedList
{
private:
// To make life easier, our sorted list will be doubly-linked
struct ListNode {
ListNode *next;
ListNode *prev;

T data;

ListNode() { next = prev = NULL; }
} *head, *tail;

int size;

protected:
ListNode* _find(const T&) const;

public:
SortedList(); // Default constructor
SortedList(cons t SortedList&); // Copy constructor
virtual ~SortedList(); // Destructor

// ... Other methods (insert(), remove(), etc...

class _SortedListIter ator {
private:
ListNode *cur; // Current element in list
public:
_SortedListIter ator() : cur(NULL) { }
_SortedListIter ator(ListNode *pos) : cur(pos) { }
T& operator*();
void operator++(); // Prefix
void operator++(int) ;// Postfix

friend bool operator==(_Sor tedListIterator &, _SortedListIter ator&); friend bool operator!=(_Sor tedListIterator &, _SortedListIter ator&); };

typedef _SortedListIter ator iterator;

iterator begin() { iterator iter(head); return iter; }
iterator end() {iterator iter(NULL); return iter; }
};

Now, of course this dosen't even compile,
try
friend bool operator==(cons t _SortedListIter ator&, const
_SortedListIter ator&);
friend bool operator!=(cons t _SortedListIter ator&, const
_SortedListIter ator&);

It should compile (it worked to me) and besides, this is what you mean, I
guess. If you are only comparing two objects, you don't mean to change any
of them. I don't understand why you are making these operators friends,
since you are declaring them iside the class SortedList. You might as well
declare them like this:

bool operator==(cons t _SortedListIter ator&) const;
bool operator!=(cons t _SortedListIter ator&) const;

I'm not entierly certian if I should declare _SotredListIter ator as a template class, or if I did so, how it would effect the _SortedListIter ator typedef
I am sorry, I don't know the answer for this one. I will leave it to
someone else to answer. But I think that if you are not using a type other
than T in _SotredListIter ator there is no reason to declare it as a
template. Unless, of course, you declare _SotredListIter ator out of
SortedList, which for some reason (I don't know why) is more common.

(AFAIK, typedef's cannot be used with template typenames).
You mean something like this ? :

_SortedListIter ator<T> iterator;

Why not?
Also, would I have establish friendship between SortedList and _SortedListIter ator so _SortedListIter ator could access SortedLists private members?

Again, it depens on wether _SotredListIter ator belongs or not to SortedList.
If not, you should need to declare it as a friend so that it can access cur.

I am sorry for not having any strait and clear answer to your questions. I
only gave my opinion. I hope someone else can clarify this for us.

Regards

Adriano

[Chris Schadl]

On Wed, 05 May 2004 09:42:18 +0900, Adriano Dal Bosco wrote:

"Chris Schadl" <cs*****@satan. blah.org.uk> wrote in message
news:pa******** *************** *****@satan.bla h.org.uk...

Hi,

I've written a simple sorted linked list class that I'm trying to
implement an iterator for. I'm trying to make the interface to the
iterator simmilar to the STL's iterator interface, so one could do:
<snip>
Now, of course this dosen't even compile,

try
friend bool operator==(cons t _SortedListIter ator&, const
_SortedListIter ator&);
friend bool operator!=(cons t _SortedListIter ator&, const
_SortedListIter ator&);

It should compile (it worked to me) and besides, this is what you mean, I
guess. If you are only comparing two objects, you don't mean to change any
of them. I don't understand why you are making these operators friends,
since you are declaring them iside the class SortedList. You might as well
declare them like this:

Yup, you're right. I forgot to declare the arguments as const, and I
don't know what the hell I was smoking when I decided to make them friend
functions. Once I fixed that (along with a couple of implementation details)
everything worked fine.

Thanks!

Chris Schadl

[Denis Remezov]

Chris Schadl wrote:

I've written a simple sorted linked list class that I'm trying to
implement an iterator for. I'm trying to make the interface to the
iterator simmilar to the STL's iterator interface, so one could do: SortedList<int> sl;
SortedList<int> ::iterator i; for (i = sl.begin() ; i != sl.end() ; ++) { /* ... */ } [snip]

Though you may be able to use a _SortedListIter ator in some limited
ways (e.g. as above), it does not yet integrate into the framework of
the standard library.
For example, the algorithms from the standard library (or any algorithms
that follow the STL conventions) may not (many will likely not) work
with _SortedListIter ator.

There are certain requirements that an iterator class must satisfy in
order to be "compliant" . First, an iterator needs to define several types
(the essential ones are value_type, difference_type and iterator_catego ry).
Then it must lend itself to be used in certain expressions, the exact list
of which varies according to the category defined by iterator_catego ry
(although your class seems to be fine as a forward iterator).

Luckily, there is a class template std::iterator<> . If you derive
from it properly you will get all the necessary typedefs.

iterator end() {iterator iter(NULL); return iter; }
I don't think the above will work (the end() is supposed to be something
you arrive at by incrementing an iterator pointing to the last valid element).

Now, of course this dosen't even compile, but hopefully it kind of
illustrates what I'm trying to do. I'm not entierly certian if I should
declare _SotredListIter ator as a template class, or if I did so, how it
would effect the _SortedListIter ator typedef (AFAIK, typedef's cannot be
used with template typenames).
I'm not sure I understand; if what you meant were typedef templates,
then they are presently not allowed. (typedef-name (what is being defined)
can of course be a dependent name, the associated (defining) type can, in
addition, be a template).

Also, would I have establish friendship
between SortedList and _SortedListIter ator so _SortedListIter ator could
access SortedLists private members?

Strictly speaking, SortedList has to declare _SortedListIter ator a
friend if _SortedListIter ator wants to access SortedList's private parts.
[OT] There is a C++ Language Defect Report #45 that says that inner classes
should have friend privileges in respect to the containing class. Many
compilers support this rule already; I happily abuse this fact. Hopefully
the rule will make into the next revision of the standard [/OT].

Nitpicking:
I would make _SortedListIter ator(ListNode *pos) : cur(pos) { }
private (it is of no relevance to the user) and declare SortedList a friend
of _SortedListIter ator.

Denis

[Michiel Salters]

Denis Remezov <RE************ *********@yahoo .removethis.ca> wrote in message news:<40******* ********@yahoo. removethis.ca>. ..

[OT] There is a C++ Language Defect Report #45 that says that inner classes
should have friend privileges in respect to the containing class. Many
compilers support this rule already; I happily abuse this fact. Hopefully
the rule will make into the next revision of the standard [/OT].

It's in the working paper for C++0x.

Regards
Michiel Salters