How to implement list::iterator?

Question

I know how to implement a template class.
However, I don't understand how the following list<int>::iterator is implemented internally. Should I make a namespace?
(Basically I want to use the same STL syntax with customized implementation.)

list<int> l;
list<int>::iterator it = l.begin();

In short, what is the simplest way to get the code working without any STL libraries?

Here is a snippet of the custom list implementation: (I omitted most of the methods for readability.)

template <typename T>
struct list {
        struct listNode {
        listNode() : item(0), next(0) {}
                listNode(T x) : item(x), next(0) {}
                T item;
                listNode* next;
        };
        list() : head(0),tail(0) {}     
        listNode* head;
        listNode* tail;
};

Why not look at your STL implementation and see how `list::iterator` is implemented? — PaulMcKenzie, Jul 30 '17 at 02:10
StackOverflow isn't a website to have other people write your code. You need to attempt to write it and if you have problems, post the code that you have and clearly state the specific problem you are having. — xaxxon, Jul 30 '17 at 02:11
I guess I did not state my question clearly. I just don't understand the mechanism of the symbol itself. I don't want people to implement my code either. How is it possible for iterator to have an unknown container? — Peter Hwang, Jul 30 '17 at 02:16
What makes you think you need to have an "unknown container"? — xaxxon, Jul 30 '17 at 02:19
For example, list::iterator and set::iterator. I wonder how :: symbol works internally. — Peter Hwang, Jul 30 '17 at 02:20
do you know how to make a templated class and define a class inside the templated class? — xaxxon, Jul 30 '17 at 02:21
Should I make a static class inside the template class in order to make things work? — Peter Hwang, Jul 30 '17 at 02:24
[already answered](https://stackoverflow.com/questions/8054273/how-to-implement-an-stl-style-iterator-and-avoid-common-pitfalls) — Chris Uzdavinis, Jul 30 '17 at 02:29

xaxxon · Accepted Answer · 2017-07-31T08:21:37.050

2

You can implement the iterator type inside the container type so that it has any information about the container it is iterating.

template<class T>
class SomeContainer {

public:

    class Iterator {
        // You can use SomeContainer and T in here.  
    };
};

edited Jul 31 '17 at 08:21

answered Jul 30 '17 at 02:28

xaxxon

19,189
5
50
80

2

Note that at least some modern STL implementations do not do this: google SCARY iterators if you care. However, this technique is servicible and is how you should start doing this in order to learn. – Yakk - Adam Nevraumont Jul 30 '17 at 02:32
This is the answer I was looking for. I didn't know that the nested class is accessible by using :: operator. Thank you. – Peter Hwang Jul 30 '17 at 02:32
@PeterHwang added "public:" – xaxxon Jul 30 '17 at 02:35

How to implement list::iterator?

1 Answers1