#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
friendclass LinkedList;
public:
// Default Constructor
const_iterator(): current{ nullptr }
{ }
// Returns element pointed by current
constint & 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
booloperator== ( const const_iterator &rhs ) const
{ return current == rhs.current; }
// Compare two const_iterator objects
booloperator!= ( 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
friendclass 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( constauto &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?
> 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;
