C++11 -> Implementing const_interator in 'STL' like fashion (pre and post C++11)

Desktop Programming > C/C++ & Visual C++

(1/3) > >>

David:
Update:

you can contact me via this link ...

https://sites.google.com/site/andeveryeyeshallseehim/

(my/editor gmail link is on the 2nd page)

C++ 11 has been here for awhile ... so it's time to 'open the books' and start to use some of the nice coding features like auto and lamda's ...

Also, time to tackle the tricky code needed to add const_iterator to a simple single linked-list ... a list that already works pretty well with just an iterator ...

The approach taken here, will be as follows:

Firstly, let's look at a very simple SLList, and see if we can get that working. It will be just two files, a test .cpp file and a template class list .h file

Here we will use 'nested classes' ...all the List code is in the one .h file.

The list here is pretty 'bare bones' ... but that's ok ... because we just want to see the code for the nested iterator and const_iterator classes.

Note! This first example will be done using a C++11 compiler.

Secondly, we will take ... what I recently read ... was a 'more STL like approach' and use separate files for the parts needed ... 1) Node, 2) iterator, 3) const_iterator, 4) SLList ... and 5) a little test file

Note the use of typedef here to 'import/nest' the iterator and const_iterator classes 'inside' the SLList class.
Also note the frequent use of friend classes and forward declarations of these classes before they are defined, to facilitate them being 'friends' ...

Note! This second example will be done using a PRE-C++11 compiler ... (i.e. ISO C++)

The third example, will be done using a C++11 compiler ...

Just a short test file,

and two .h files ...

one for the node class
and
one for the single linked list class

This single linked list is a little more 'embellished' ...

for example it demos/uses move copy and move assignment

The methods defined here are mostly just the ones you might want to have ... i.e. ... if you wanted to derive a STACK class from this single linked list class ... which is also shown next ...

And then ... a little demo program, that uses that (derived) STACK class ... to solve a palindrome type student problem.

Note here, the iterator and const_iterator classes are 'nested' in side the single linked list class.

I would suggest that you follow this development sequence ...

from an easy 'bare-bones' list ...

to a little more functional single linked list ...

because we want to focus here,

not on all the functions,

but rather on how to get the const_iterator parts merged in the list ...

It may take a while for you to 'see' the several key coding changes/additions ...

to make the transition for just having an iterator ...

to ALSO having a const_iteratoer ... in your list class.

It took me much 'digging' and 'thinking' and 'trying' ... to finally get it (all?) to work ...the way I 'expected' it should work.

Enjoy ... but be prepared for taking some time to dig in ... read all the comments ... make some code 'changes/edits/errors' ... and read the error messages ... and add some tests and see the code working (or not?)

Shalom shalom,

David

David:
Ok ... here is the little test program for the C++11 very simple single linked list that has iterator and const_iterator classes nested in side the list class. (The ONE list class file will follow.)

--- Code: ---// test_SLList.h.cpp // // 2014-08-13 //

// compile with C++11 compiler //

#include "SLList.h"

int main()
{
List< int > myLst;

myLst.push_front( 1 );
myLst.push_front( 2 );
myLst.push_front( 3 );

myLst.push_front( 9 );
myLst.push_front( 7 );
myLst.push_front( 6 );

myLst.push_back( 4 );
myLst.push_back( 5 );
myLst.push_back( 0 );

myLst.push_back( 8 );

myLst.print();

cout << "\nNote ... here ... testing post ++ increment ...\n";
for( auto &e : myLst ) cout << e++ << ' ';

cout << '\n';
List< int >::iterator i = myLst.begin(), end = myLst.end();
List< int >::const_iterator it = myLst.begin();

cout << "\nTesting iter's ... \n";
if( it == i ) cout << "iter's (addresses) are equal ...\n";
if( i == it ) cout << "iter's (addresses) are equal ...\n";
if( !(it != i) ) cout << "iter's (addresses) are equal ...\n";
if( !(i != it) ) cout << "iter's (addresses) are equal ...\n";

bubble_sort( i, end, MyCmpAscending<int>() );

cout << "\nAfter post ++ increment and then a bubble_sort... \n";
// NOTE: using const_iterator here ...
for( ; it != myLst.end() ; it++ )
cout << *it << ' ';

cout << "\nPress 'Enter' to continue/exit ... ";
cin.get();
}

--- End code ---

David:
Now the include file ... for the list tested above :

--- Code: ---// SLList.h // // 2014-08-13 //

// compile with C++11 compiler //

#ifndef SSLIST_H
#define SSLIST_H

#include <iostream>
#include <algorithm> // re. list std::swap ...

using namespace std;

template< typename T >
class List
{
struct Node
{
T val;
Node* next;

Node( const T& x, Node* next ) : val(x), next(next) {}
Node( const T& x ) : val(x), next(nullptr) {}
// implicit copy constructor, copy assignment and destructor
} ;

Node* head;
Node* tail;
size_t len;

public:

List() : head( nullptr ), tail(nullptr), len(0) {}
~List() { clear(); }
void clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next;
delete cur;
}
}

void push_front( const T& val )
{
Node* newNode = new Node( val, head );
head = newNode;
if( !len ) tail = head;
++len;
}
void push_back( const T& val )
{
Node* newNode = new Node( val, nullptr );
if( len ) tail->next = newNode;
else head = newNode;
tail = newNode;
++len;
}

void print() const
{
const Node* cur = head;
if( cur ) std::cout << "Printing the list: \n";
while( cur )
{
std::cout << cur->val << ' ';
cur = cur->next;
}
std::cout << std::endl;
}

class iterator : std::iterator< forward_iterator_tag, T >
{
friend List< T >;
Node* ptr;
public:
explicit iterator( Node* p = nullptr ) : ptr(p) {}
// implicit copy constructor, copy assignment and destructor

T& operator * () { return ptr->val; }

iterator & operator ++ () { ptr = ptr->next; return *this; }
iterator operator ++ (int) { iterator tmp = *this; ++*this; return tmp; }

bool operator == ( const iterator& other ) const
{
return ptr == other.ptr;
}
bool operator != ( const iterator& other) const
{
return ptr != other.ptr;
}

Node* get_ptr() const { return ptr; }
} ;

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

class const_iterator : std::iterator< forward_iterator_tag,
T, ptrdiff_t, const T*, const T& >
{
friend List< T >;
const Node* ptr;
public:
explicit const_iterator( const Node* p = nullptr ) : ptr(p) {}
// implicit copy constructor, copy assignment and destructor

// Note: this next ctor is 'vital' ... // comment out and compile to see why? //
const_iterator( const iterator& i) : ptr(i.ptr) {}

const T& operator* () const { return ptr->val; }

const_iterator& operator ++ () { ptr = ptr->next; return *this; }
const_iterator operator ++ (int)
{ const_iterator tmp = *this; ++*this; return tmp; }

bool operator == ( const const_iterator& other ) const
{
return ptr == other.ptr;
}
bool operator!= ( const const_iterator& other ) const
{
return ptr != other.ptr;
}

const Node* get_ptr() const { return ptr; }
} ;

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

friend bool operator == ( const iterator& a, const const_iterator& b )
{
return a.get_ptr() == b.get_ptr();
}
friend bool operator != ( const iterator& a, const const_iterator& b )
{
return a.get_ptr() != b.get_ptr();
}
friend bool operator == ( const const_iterator& a, const iterator& b )
{
return a.get_ptr() == b.get_ptr();
}
friend bool operator != ( const const_iterator& a, const iterator& b )
{
return a.get_ptr() != b.get_ptr();
}
} ;

// =========================================================

// This bubble sort IS USEFUL for SMALL data sets
// or when data is in a very near sorted state
// (1 or 2, or very few, elements out of order)
// i.e. only 1 or 2 or very few passes ... till sorted.

template < typename ForwardIter, typename Compare >
void bubble_sort( ForwardIter beg,
ForwardIter end, Compare comp )
{
ForwardIter prev = beg, left_el = beg, right_el = beg;

if( beg == end ) return; // empty or only one element ... //

bool aswap = true;
while( aswap )
{
aswap = false;
while( ++right_el != end )
{
prev = right_el;
// Note r,l order below when doing bubble_sort //
if( comp( *right_el, *left_el) )
{
std::swap( *left_el, *right_el );
aswap = true; // if NO swaps this pass then done .. //
}
++left_el;
}
end = prev; // --end;

left_el = right_el = beg; // start at beg if need a next loop
}
}

template< typename T >
struct MyCmpAscending // re. Ascending bubble_sort...
{
bool operator () ( const T& obj, const T& obj2 )
{
return obj < obj2;
}
} ;

// =========================================================

#endif

--- End code ---

David:
This next, 2nd example, is claimed by some to be in the direction of how the STL might do it ...

Note all the 5 files, 1st a test .cpp file ... and then 4 .h files to be included.
Note the use of typedef to 'nest' the (separate file) iterator and const_iterator classes 'inside' the list class.

NOTE !!! This uses a PRE-C++ compiler (i.e. ISO C++)

Ok ... the little test file :

--- Code: ---// test_MySLList.h.cpp //

#include "MySLList.h"

#include <iostream>
#include <string>

using namespace std;

void test_1()
{
MySLList< string > fruits;

fruits.push_back( "apples");
fruits.push_back( "oranges" );
fruits.push_back( "peaches" );
fruits.push_back( "pears" );
fruits.push_back( "grapes" );

MySLList< string >::const_iterator ptr = fruits.begin();
MySLList< string >::const_iterator end = fruits.end();

MySLList< string >::iterator pptr = fruits.begin();
MySLList< string >::iterator eend = fruits.end();

if( pptr == ptr ) cout << "equals\n";
else cout << "NOT equals\n";

cout << "They're all fruit ...\n";
while( ptr != end )
{
if( *ptr == "grapes" )
{
cout << "Yes ... " << *ptr << " are fruit."
<< endl;
break;
}
++ptr;
}
}

int main()
{
test_1();
cin.get();
}

--- End code ---

David:
Now the Node class ...

--- Code: ---// MySLList_Node.h //

#ifndef MYSLLIST_NODE_H
#define MYSLLIST_NODE_H

template< typename T > class MySLList; // forward declare
template< typename T > class MySLList_iterator; // forward declare
template< typename T > class const_MySLList_iterator; // forward declare

template < typename T >
class MySLList_Node
{
friend class MySLList< T >;
friend class MySLList_iterator< T >;
friend class const_MySLList_iterator< T >;

//MySLList_Node( const T& t, MySLList_Node< T >* next ) : elem(t), next(next) {}
MySLList_Node( const T& e ) : elem(e), next(0) {}
MySLList_Node( const T& e, MySLList_Node< T >* n ) : elem(e), next(n) {}

T elem;
MySLList_Node< T >* next;
} ;

#endif
--- End code ---

And then the iterator class ...

--- Code: ---// MySLList_iterator.h //

#ifndef MYSLLIST_ITERATOR_H
#define MYSLLIST_ITERATOR_H

#include <cassert>

template< typename T >
class MySLList_iterator : public std::iterator< std::forward_iterator_tag, T >
{
friend class MySLList< T >;

MySLList_Node< T >* ptr;

MySLList_iterator( MySLList_Node< T >* x ) : ptr(x) {}

public:

T& operator * () { return ptr->elem; }
//const T& operator * () const { return ptr->elem; }

MySLList_iterator< T >& operator ++ ();
MySLList_iterator< T > operator ++ (int)
{ MySLList_iterator< T > tmp = *this; ++*this; return tmp; }

bool operator != ( const MySLList_iterator< T >& other ) const;
bool operator == ( const MySLList_iterator< T >& other ) const { return !(*this != other); }

bool operator != ( const const_MySLList_iterator< T >& other ) const { return (ptr != other.get_ptr()); }
bool operator == ( const const_MySLList_iterator< T >& other ) const { return (ptr == other.get_ptr()); }

const MySLList_Node< T >* get_ptr() const { return ptr; };
} ;

/*
template< typename T >
T& MySLList_iterator< T >::operator * ()
{
return ptr->elem;
}
template< typename T >
const T& MySLList_iterator< T >::operator * () const
{
return ptr->elem;
}
*/

template< typename T >
MySLList_iterator< T >& MySLList_iterator< T >::operator ++ ()
{
assert( ptr != 0 );
ptr = ptr->next;
return *this;
}

template< typename T >
bool MySLList_iterator< T >:: operator != ( const MySLList_iterator< T >& other ) const
{
return this->ptr != other.ptr;
}

#endif

--- End code ---

And then the const_iterator class ...

--- Code: ---// const_MySLList_iterator.h //

#ifndef CONST_MYSLLIST_ITERATOR_H
#define CONST_MYSLLIST_ITERATOR_H

#include <cassert>

//#include "MySLList_iterator.h"

template< typename T >
class const_MySLList_iterator : public std::iterator<
std::forward_iterator_tag, T, ptrdiff_t, const T*, const T& >
{
friend class MySLList< T >;

const MySLList_Node< T >* ptr;

const_MySLList_iterator( MySLList_Node< T >* x ) : ptr(x) {}

public:

// this next ctor is 'vital ... comment it out and compile to see error message ... why ? //
const_MySLList_iterator< T >( const MySLList_iterator< T >& i ) : ptr(i.get_ptr()) {}

const MySLList_Node< T >* get_ptr() const { return ptr; };

//T& operator * () { return ptr->elem; }
const T& operator * () const { return ptr->elem; }

const_MySLList_iterator< T >& operator ++ ();
const_MySLList_iterator< T > operator ++ (int)
{ const_MySLList_iterator< T > tmp = *this; ++*this; return tmp; }

bool operator != ( const const_MySLList_iterator< T >& other ) const;
bool operator == ( const const_MySLList_iterator< T >& other ) const { return !(*this != other); }

bool operator != ( const MySLList_iterator< T >& other ) const { return (ptr != other.get_ptr()); }
bool operator == ( const MySLList_iterator< T >& other ) const { return (ptr == other.get_ptr()); }

} ;

/*
template< typename T >
T& const_MySLList_iterator< T >::operator * ()
{
return ptr->elem;
}
template< typename T >
const T& const_MySLList_iterator< T >::operator * () const
{
return ptr->elem;
}
*/

template< typename T >
const_MySLList_iterator< T >& const_MySLList_iterator< T >::operator ++ ()
{
assert( ptr != 0 );
ptr = ptr->next;
return *this;
}

template< typename T >
bool const_MySLList_iterator< T >:: operator != ( const const_MySLList_iterator< T >& other ) const
{
return this->ptr != other.ptr;
}

#endif

--- End code ---

Navigation

[0] Message Index

[#] Next page

Go to full version