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(const SortedList&); // Copy constructor
virtual ~SortedList(); // Destructor

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

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

friend bool operator==(_SortedListIterator&, _SortedListIterator&);
friend bool operator!=(_SortedListIterator&, _SortedListIterator&);
};

typedef _SortedListIterator 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 _SotredListIterator as a template class, or if I did so, how it
would effect the _SortedListIterator typedef (AFAIK, typedef's cannot be
used with template typenames). Also, would I have establish friendship
between SortedList and _SortedListIterator so _SortedListIterator could
access SortedLists private members?

Thanks,

Chris Schadl

 

[Adriano Dal Bosco]

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(const SortedList&); // Copy constructor
virtual ~SortedList(); // Destructor

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

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

friend bool operator==(_SortedListIterator&, _SortedListIterator&);
friend bool operator!=(_SortedListIterator&, _SortedListIterator&);
};

typedef _SortedListIterator 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==(const _SortedListIterator&, const
_SortedListIterator&);
friend bool operator!=(const _SortedListIterator&, const
_SortedListIterator&);

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==(const _SortedListIterator&) const;
bool operator!=(const _SortedListIterator&) const;

I'm not entierly certian if I should declare _SotredListIterator as a

template class, or if I did so, how it

would effect the _SortedListIterator 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 _SotredListIterator there is no reason to declare it as a
template. Unless, of course, you declare _SotredListIterator 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 ? :

_SortedListIterator<T> iterator;

Why not?

Also, would I have establish friendship between SortedList and

_SortedListIterator so _SortedListIterator could

access SortedLists private members?

Again, it depens on wether _SotredListIterator 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]

try
friend bool operator==(const _SortedListIterator&, const
_SortedListIterator&);
friend bool operator!=(const _SortedListIterator&, const
_SortedListIterator&);

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]

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 _SortedListIterator 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 _SortedListIterator.

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_category).
Then it must lend itself to be used in certain expressions, the exact list
of which varies according to the category defined by iterator_category
(although your class seems to be fine as a forward iterator).

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 _SotredListIterator as a template class, or if I did so, how it
would effect the _SortedListIterator 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 _SortedListIterator so _SortedListIterator could
access SortedLists private members?

Strictly speaking, SortedList has to declare _SortedListIterator a
friend if _SortedListIterator 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 _SortedListIterator(ListNode *pos) : cur(pos) { }
private (it is of no relevance to the user) and declare SortedList a friend
of _SortedListIterator.

Denis

 

[Michiel Salters]

[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