Question about Ranged For-Loop and Linked List

I've created a doubly linked list for practice. I've implemented const_iterator and iterator as well.

Here's the code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include <iostream>
#include <algorithm>

/*
    Create a simple doubly LinkedList class
    Implement const_iterator and iterator interfaces to allow list traversal
*/
class LinkedList
{
private:
    // LinkedList Node
    struct Node
    {
        int data = 0;
        Node* next = nullptr;
        Node* prev = nullptr;

        Node( int data ): next{ nullptr } , prev{ nullptr } , data{ data }
        { }
    };

public:
    // const_iterator interface to allow traversal
    class const_iterator
    {
    protected:
        Node* current;

        // protected constructor that accepts Node*
        // It is protected to prevent user from calling it explicitly
        const_iterator( Node* c ): current{ c }
        { }

        int & retrieve() const
        { return current->data; }

        // LinkedList class needs to be able to access protected constructor
        friend class LinkedList;

    public:
        // Default Constructor
        const_iterator(): current{ nullptr }
        { }

        // Returns element pointed by current
        const int & operator* () const
        { return retrieve(); }

        // Pre-increment operator
        const_iterator & operator++ ()
        {
            if( current != nullptr ) {
                current = current->next;
                return *this;
            }
        }

        // Post-increment operator
        const_iterator operator++ ( int )
        {
            const_iterator old = *this;
            ++( *this );
            return old;
        }

        // Pre-decrement operator
        const_iterator & operator-- ()
        {
            if( current != nullptr ) {
                current = current->prev;
                return *this;
            }
        }

        // Post-decrement operator
        const_iterator operator-- ( int )
        {
            const_iterator old = *this;
            --( *this );
            return old;
        }

        // Compare two const_iterator objects
        bool operator== ( const const_iterator &rhs ) const
        { return current == rhs.current; }

        // Compare two const_iterator objects
        bool operator!= ( const const_iterator &rhs ) const
        { return current != rhs.current; }
    };

    // iterator interface
    class iterator: public const_iterator
    {
    public:
        // Default Constructor
        iterator() {}

        // Allow read/write access to the data
        int & operator* ()
        { return const_iterator::retrieve(); }

        // Pre-increment operator
        iterator & operator++ ()
        {
            if( current != nullptr ) {
                current = current->next;
                return *this;
            }
        }

        // Post-increment operator
        iterator operator++ ( int )
        {
            iterator old = *this;
            ++( *this );
            return old;
        }

    private:
        // Prevent user from calling this constructor explicitly
        iterator( Node* c ): const_iterator{ c }
        { }

        // Allow LinkedList class to access private constructor
        friend class LinkedList;
    };

public:
    // Default Constructor
    LinkedList() {}

    // Copy Constructor
    LinkedList( const LinkedList &rhs )
    {
        Node* temp = rhs.head;

        while( temp != nullptr ) {
            push_back( temp->data );
            temp = temp->next;
        }
    }

    // Assignment Operator
    LinkedList & operator= ( const LinkedList &rhs )
    {
        LinkedList copy = rhs;
        std::swap( *this , copy );
        return *this;
    }

    // Destructor
    ~LinkedList()
    {
        while( head != nullptr ) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void push_front( int x )
    {
        if( head == nullptr ) {
            head = new Node{ x };
            tail = head;
            theSize++;
        }
        else {
            Node* temp = head;
            head = new Node{ x };
            head->next = temp;
            temp->prev = head;
            theSize++;
        }
    }

    void push_back( int x )
    {
        if( tail == nullptr ) {
            tail = new Node{ x };
            head = tail;
            theSize++;
        }
        else {
            Node* temp = tail;
            tail = new Node{ x };
            temp->next = tail;
            tail->prev = temp;
            theSize++;
        }
    }

    void pop_front()
    {
        if( head != nullptr ) {
            Node* temp = head;
            head = temp->next;
            head->prev = nullptr;

            delete temp;
            theSize--;
        }
    }

    void pop_back()
    {
        if( tail != nullptr ) {
            Node* temp = tail;
            tail = temp->prev;
            tail->next = nullptr;

            delete temp;
            theSize--;
        }
    }

    int size()
    { return theSize; }

    const_iterator begin() const
    { return const_iterator{ head }; }

    const_iterator end() const
    { return const_iterator{ tail->next }; }

    iterator begin()
    { return iterator{ head }; }

    iterator end()
    { return iterator{ tail->next }; }

private:
    Node *head = nullptr;
    Node *tail = nullptr;
    int theSize = 0;
};

// Test Driver to test operations of LinkedList
int main()
{
    LinkedList list;
    list.push_back( 1 );
    list.push_back( 2 );
    list.push_back( 3 );
    list.push_back( 4 );
    list.push_back( 5 );

    list.pop_back();
    list.pop_front();

    LinkedList::iterator itr;

    for( itr = list.begin() ; itr != list.end() ; itr++ ) {
        std::cout << *itr << std::endl;
    }
    std::cout << std::endl;

    LinkedList list2 = list;
    list2.push_front( 100 );

    for( const auto &x : list2 ) {
        std::cout << x << std::endl;
    }

    std::cout << "\nThe size of list is " << list.size() << std::endl;
}


Now, near the end of the main function, I've tested my linked list with ranged for-loop. At first, I expected it to print a bunch of memory addresses, but to my surprise, it actually printed legit values. I know that the ranged for-loop requires begin(), end(), and operator++ of the container. But how did it know to use operator* to get the value?

Thanks in advance for the help.
> But how did it know to use operator* to get the value?

The standard specifies that the range-based for loop must use the unary operator *

The range-based for statement for ( for-range-declaration : for-range-initializer ) statement

is equivalent to
1
2
3
4
5
6
7
8
9
10
11
{
    auto &&__range = for-range-initializer ;
    auto __begin = begin-expr ;
    auto __end = end-expr ;
    for ( ; __begin != __end; ++__begin ) {

        for-range-declaration = *__begin;

        statement
    }
}
where ...
- C++17

C++11 is slightly different (the types of the begin-expression and the end-expression must be the same prior to C++17) , but it too has for-range-declaration = *__begin;
Last edited on
@JLBorges
Thank you. It makes sense.

Topic archived. No new replies allowed.