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

[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: [Select]

// 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();
}


[David]

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

Code: [Select]

// 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




[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: [Select]

// 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();
}


[David]

Now the Node class ...

Code: [Select]

// 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

And then the iterator class ...

Code: [Select]

// 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


And then the const_iterator class ...

Code: [Select]

// 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


[David]

Finally ... the second (simple list) single linked list class .h file

(Note all the comments in the code, especially in the const_iterator section part.)

Remember, this is NOT C++11 code here ... just use an ISO C++ compiler.

Code: [Select]

// MySLList.h //

#ifndef MYSLLIST_H
#define MYSLLIST_H

#include <iostream>
#include <string>


#include "MySLList_Node.h"
#include "MySLList_iterator.h"
#include "const_MySLList_iterator.h"

template< typename T >
class MySLList
{
public:
    typedef MySLList_iterator< T > iterator;

    MySLList() : head(0), tail(0) {}
    ~MySLList() { clear(); }
   
    void push_front( const T& elem );
    void push_back(  const T& elem );
    void clear();
    bool empty() const { return head == 0; }
   
    iterator begin() { return iterator( head ); }
    iterator end() { return iterator( 0 ); }

    typedef const_MySLList_iterator< T > const_iterator;
   
    const_iterator begin() const { return const_iterator( head ); }
    const_iterator end()   const { return const_iterator( 0 ); }

private:
    MySLList_Node< T > *head, *tail;

} ;


template< typename T >
void MySLList< T >::clear()
{
    MySLList_Node< T >* ptr;
    while( head )
    {
        ptr = head;
        head = head->next;
        std::cout << "Inside 'clear()' deleting " << ptr->elem << '\n';
        delete ptr;
    }
    // Note: done while loop when head is 0 //
    tail = 0;
}

template< typename T >
void MySLList< T >::push_front( const T& elem )
{
    MySLList_Node< T >* newNode = new MySLList_Node< T >( elem, head );
    if( !head ) tail = newNode;
    head = newNode;
}
template< typename T >
void MySLList< T >::push_back( const T& elem )
{
    MySLList_Node< T >* newNode = new MySLList_Node< T >( elem, 0 );
    if( tail ) tail->next = newNode;
    else head = newNode;
    tail = newNode;
}

#endif


[David]

Ok ... back to using a C++ 11 compiler for this 3rd and (last here for now) section ...

Firstly, a little test program ...

Code: [Select]

// test_SLList.h.cpp //  // 2014-08-14 //

// needs C++11 compiler //

#define debugSLL 0

#include "SLList.h"

void tests_1()
{
    using std::cout; using std::cin; using std::endl;

    SLList< int > myLst;

    // get some test data into the list ...
    myLst.push_back( 3 );
    myLst.push_back( 4 );
    myLst.push_back( 5 );

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

    //SLList< int > myLst2 = myLst;
    auto myLst2 = myLst;

    cout << "Testing using iterator to print... \n";
    cout << "Note: each element has value++ when done.\n";

    SLList< int >::const_iterator i;
    SLList< int >::iterator it;
    for( it = myLst.begin(); it != myLst.end(); ++ it )
         cout << (*it)++ << ' ';
         
         
    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";

    cout << "\nPrinting with ... for( const auto e : myLst ) cout...\n";
    for( const auto e : myLst ) cout << e << ' ';

    cout << "\nmyLst2.print()... \n";
    myLst2.print();

    cout << endl;
    while( myLst2.size() > 3 )
    {
        cout << "size = " << myLst2.size()
             << ", front = " << myLst2.front()
             << ", back = " << myLst2.back()
             << ", pop_front() ...\n";
        myLst2.pop_front();
    }

    cout << endl;
    while( !myLst2.empty() )
    {
        cout << "size = " << myLst2.size()
             << ", front = " << myLst2.front()
             << ", back = " << myLst2.back()
             << ", pop_back() ...\n";
        myLst2.pop_back();
    }

    cout << "\nmyLst2.print() ...\n";
    myLst2.print();
}



int main()
{
    tests_1();

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



[David]

Now the Node .h file ...

Code: [Select]

// LISTNODE.H //  // 2014-08-14 //

// needs C++11 compiler //

#ifndef LISTNODE_H
#define LISTNODE_H

//forward declaration of class SLList is required to announce that class
template< typename NODETYPE > class SLList;

template< typename NODETYPE >
class Node
{
    friend class SLList< NODETYPE >;

    NODETYPE data;
    Node< NODETYPE > *nextPtr;
public:
    // value ctor...
    Node( const NODETYPE& info ) : data(info), nextPtr(nullptr)
    {}
} ;

#endif


[David]

Then the list .h file ...

Code: [Select]

// SLList.h //  // 2014-08-14 //

// needs C++11 compiler //


#ifndef SLLIST_H
#define SLLIST_H


#include "LISTNODE.H"


#include <iostream>
#include <stdexcept>


#ifndef debugSLL
#define debugSLL 0
#endif

template < typename NODETYPE >
class SLList
{
public:

    //default constructor
    explicit SLList(): firstPtr(nullptr), lastPtr(nullptr), len(0) {}

    //destructor
    ~SLList()
    {
        clear();
#if debugSLL
        std::cout << "dtor called ... all nodes 'cleared' ...\n";
#endif
    }

    void push_front( const NODETYPE& value )
    {
        Node< NODETYPE >* newPtr = getNewNode( value );

        // faster running code if firstly handle most likely case ...
        if( len )
        {
            newPtr->nextPtr = firstPtr;
            firstPtr = newPtr;
        }
        else
        {
            lastPtr = firstPtr = newPtr;
        }
        ++len;
    }

    void push_back( const NODETYPE& value )
    {
        Node< NODETYPE >* newPtr = getNewNode( value );

        if( len )
        {
            lastPtr->nextPtr = newPtr;
            lastPtr = newPtr;
        }
        else
        {
            lastPtr = firstPtr =  newPtr;
        }
        ++len;
    }


    const NODETYPE& front() const
    {
        if( !len )
            throw std::out_of_range( "Error! List is empty, "
                                     "so can NOT access front() ..." ) ;
        // else ...
        return firstPtr->data;
    }
    const NODETYPE& back() const
    {
        if( !len )
            throw std::out_of_range( "Error! List is empty, "
                                     "so can NOT access back() ..." ) ;
        return lastPtr->data;
    }


    //return boolean to signify if operation is successful
    bool pop_front()
    {
        if( len )
        {
            Node< NODETYPE >* curPtr = firstPtr;
            firstPtr = firstPtr->nextPtr;
            delete curPtr;
            --len;
            if( !len ) lastPtr = nullptr;
            return true;
        }
        // else if reach here ...
        return false;
    }

    //return boolean to signify if operation is successful
    bool pop_back()
    {
        if( len )
        {
            Node< NODETYPE >* curPtr = firstPtr,
                            * prevPtr = nullptr;
            while( curPtr->nextPtr )
            {
                prevPtr = curPtr;
                curPtr = curPtr->nextPtr;
            }

            lastPtr = prevPtr;
            if( lastPtr ) lastPtr->nextPtr = nullptr;
            else firstPtr = nullptr;
            delete curPtr;
            --len;
            //if( !len ) firstPtr = nullptr; // handled above //
        }
        // else if reach here ...
        return false;
    }

    //returns true if SLList is empty
    bool empty() const
    {
        return !len;
    }

    //display contents of SLList
    void print() const
    {
        if( empty() )   //SLList is empty
        {
#if debugSLL
            std::cout << "The list is empty.\n\n";
#endif
            return;
        }

        //continue by printing the list's contents
        Node< NODETYPE >* currentPtr = firstPtr;
#if debugSLL
        std::cout << "The list is: ";
#endif
        while( currentPtr )
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << std::endl;
    }

    // copy ctor ...
    SLList< NODETYPE > ( const SLList< NODETYPE >& old )
    {
        firstPtr = lastPtr = nullptr;
        len = 0;
        //iterate over old ... and add copy of each to new list
        Node< NODETYPE >* curPtr = old.firstPtr;
        while( curPtr )
        {
            push_back( curPtr->data );
            curPtr = curPtr->nextPtr;
        }
    }

    // move copy ctor ...
    SLList< NODETYPE > ( const SLList< NODETYPE >&& old )
    {
        firstPtr = old.firstPtr;
        lastPtr = old.lastPtr;
        len = old.len;

        old.firstPtr = old.lastPtr = nullptr;
        old.len = 0;
    }


    // overloaded assignment ...
    SLList< NODETYPE >& operator = ( const SLList< NODETYPE >& old )
    {
        //check to see if the list is the same...
        if( this != &old )
        {
            //first ensure the list being assigned to is empty ...
            clear();

            //iterate over old ... and add copy of each to new list
            Node< NODETYPE >* curPtr = old.firstPtr;
            while( curPtr )
            {
                push_back( curPtr->data );
                curPtr = curPtr->nextPtr;
            }
        }
        return *this;
    }

    // move overloaded assignment ...
    SLList< NODETYPE >& operator = ( const SLList< NODETYPE >&& old )
    {
        //check to see if the list is the same...
        if( this != &old )
        {
            clear();

            firstPtr = old.firstPtr;
            lastPtr = old.lastPtr;
            len = old.len;

            old.firstPtr = old.lastPtr = nullptr;
            old.len = 0;
        }
        return *this;
    }


    // return a modifiable lvalue ...
    NODETYPE& operator [] ( size_t index )
    {
        if( index >= len )
            throw std::out_of_range( "Index out of range" ) ;

        //is in valid range ...
        size_t i = 0;
        Node< NODETYPE >* curPtr = firstPtr;

        while( i != index )
        {
            ++i;
            curPtr = curPtr->nextPtr;
        }
        return ( curPtr->data );
    }

    //returns non-modifiable rvalue
    const NODETYPE& operator [] ( size_t index ) const
    {
        if( index >= len )
            throw std::out_of_range( "Index out of range" ) ;

        //is in valid range ...
        size_t i = 0;
        Node< NODETYPE >* curPtr = firstPtr;

        while( i != index )
        {
            ++i;
            curPtr = curPtr->nextPtr;
        }
        return ( curPtr->data );
    }

    size_t size()  const
    {
        return len;
    }

    void clear()
    {
        if( len ) //SLList is not empty
        {
#if debugSLL
            std::cout << "'clear()' called ... clearing nodes ...\n";
#endif

            Node< NODETYPE > *curPtr = firstPtr;
            Node< NODETYPE > *tmpPtr = nullptr;

            while( curPtr )
            {
                tmpPtr = curPtr->nextPtr;
                //std::cout << curPtr->data << '\n';
                delete curPtr;
                curPtr = tmpPtr;
                --len;
            }
            firstPtr = lastPtr = nullptr;
        }
    }
   
    class const_iterator;

    class iterator : std::iterator< std::forward_iterator_tag, NODETYPE >
    {
        Node< NODETYPE >* ptr;
        friend class SLList< NODETYPE >;
    public:
        iterator( Node< NODETYPE >* p=nullptr ) : ptr(p) {}

        //const NODETYPE& operator * () const { return ptr->data; }
        NODETYPE& operator * () { return ptr->data; }
       
        iterator& operator ++ () { ptr = ptr->nextPtr; return *this; }
        iterator& operator ++ ( int dummy ) { ptr = ptr->nextPtr; return *this; }
       
        bool operator != ( const iterator& it ) const { return  ptr != it.ptr; }
        bool operator == ( const iterator& it ) const { return  ptr == it.ptr; }
       
        bool operator != ( const const_iterator& it ) const { return  ptr != it.get_ptr(); }
        bool operator == ( const const_iterator& it ) const { return  ptr == it.get_ptr(); }
       
        const Node< NODETYPE >* get_ptr() const { return ptr; }
    } ;

    iterator begin() { return iterator(firstPtr); }
    iterator end() { return iterator(nullptr); }
   
   
   
    class const_iterator : std::iterator< std::forward_iterator_tag,
        NODETYPE, ptrdiff_t, const NODETYPE*, const NODETYPE& >
    {
        const Node< NODETYPE >* ptr;
        friend class SLList< NODETYPE >;
    public:
        const_iterator( const Node< NODETYPE >* p=nullptr ) : ptr(p) {}
       
        // Note: this next ctor is 'vital' ... // comment out and compile to see why? //
        const_iterator( const iterator& i ) : ptr(i.ptr) {}
       
        const NODETYPE& operator * () const { return ptr->data; }
        //NODETYPE& operator * () { return ptr->data; }

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

        bool operator != ( const const_iterator& it ) const { return  ptr != it.ptr; }
        bool operator == ( const const_iterator& it ) const { return  ptr == it.ptr; }
       
        bool operator != ( const iterator& it ) const { return  ptr != it.get_ptr(); }
        bool operator == ( const iterator& it ) const { return  ptr == it.get_ptr(); }
       
        const Node< NODETYPE >* get_ptr() const { return ptr; }
    } ;

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

private:
    Node< NODETYPE >* firstPtr;
    Node< NODETYPE >* lastPtr;
    size_t len;

    Node< NODETYPE >* getNewNode( const NODETYPE& value )
    {
        return new Node< NODETYPE >( value );
    }
} ;

#endif



[David]

Ok ... here is a little derived STACK class and test program that uses the above single linked list ...


Firstly ... the test program:

Code: [Select]

//  testIfPalindromeViaStack.cpp //  // 2014-08-14 //

// needs C++11 compiler //

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype> // for C++ ... but Note:  C uses <ctype.h> //

#include "STACK.H"


using namespace std;

const string HEADER =
    "This program tests if a string is a 'palindrome' ...\n";
   
const string ERROR_MSG =
    "\nInput can not have any numeric characters"
    ", please try again.\n";


// some utilities used here ...

string takeInString( const string& msg = "" )
{
    cout << msg << flush;
    string val;
    getline( cin, val );
    return val;
}
int takeInChr( const std::string& msg = "" )
{
    string reply = takeInString( msg );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}
bool more()
{
    if( tolower( takeInChr( "More (y/n) ? " )) == 'n' )
return false;
    // else ...
    return true;
}
bool hasDigits( const string& toTest )
{
    for( auto e : toTest )
        if( isdigit(e) )
            return true;
           
    // else ... if reach here ...
    return false;
}



int main()
{
    cout << HEADER << endl;
    do
    {
        string input;
        for( ; ; )
        {
            input = takeInString( "Enter a line of text, without "
                                  "any numbers in it, to be "
                                  "tested:\n" );
            if( !hasDigits( input ) )
                break; // Ok good ... accept line with NO digits ... //
            else
                cout << ERROR_MSG << endl;
        }

        //convert all letters to lowercase ... using a [] lambda function here //
        for_each( input.begin(), input.end(), [] (char& c) {  c = tolower(c); } );


        //after this is done, create two stacks ...
        //'forward' and 'reverse', and ...
        //use the STL list for the stack//
        Stack< char > forwardStack,
                      backwardStack;

                                   
        // now can populate 'forward' and 'backward' stacks
        for( auto e : input )
            // accept only alpha char's ...
            if( isalpha(e) ) forwardStack.push( e );
           
        std::cout << "Forward ...  ";
        forwardStack.print();
        std::cout << "\n\n";
       
       
        // now can populate ... 'backward' stacks
        for( auto it = input.rbegin(); it != input.rend(); ++ it )
            if( isalpha(*it) ) backwardStack.push( *it );

        std::cout << "Backward ... ";
        backwardStack.print();
        std::cout << "\n\n";
       

        //check to see if the stacks are equal
        cout << "\n'" << input << "' is"
             << (forwardStack == backwardStack ? "" : " not")
             << " a palindrome.\n\n";
     }
     while( more() );
}


[David]

And, finally, for now, the STACK.h file (and class, used above) ...

Code: [Select]

// STACK.H //  // 2014-08-14 //

// needs a C++11 compiler //

// class definition using private inheritance of class SLList //

#ifndef Stack_h
#define Stack_h

#include "SLList.h"

template< typename STACKTYPE >
class Stack : private SLList< STACKTYPE >
{
public:
   
    void push( const STACKTYPE& data )
    {
        this->push_front( data )  ;
    }
   
    const STACKTYPE& top() const
    {
        return this->top();
    }

    bool pop()
    {
        return this->pop_front();
    }

    bool operator == ( const Stack& other ) const
    {
        if( this->size() != other.size() ) return false;
        // else ...
        auto it = this->begin(), it2 = other.begin();
       
        while( it != this->end() )
        {
            if( *it != *it2 ) return false;
            ++it, ++it2;
        }
        // if reach here ...
        return true;
    }

    void print() const
    {
        std::cout << "The stack is: ";
/*
        for( auto it = this->begin(); it != this->end(); ++it )
             std::cout << *it << ' ';
*/
        for( const auto e : *this )
             std::cout << e << ' ';
    }
} ;
#endif


Enjoy ...