Expert: vijayan - 9/17/2008

Question
QUESTION: Hi Vijayan,
 I have read source as to how to make own iterator for linked list. I have some problem while creating the iterator. Problem in the sense, i want to check less than operator with two list using lexicographical_compare function. I got wrong result.  And also, I haven't get proper answer while invoking STL::max_element function when passing input as a my own iterator. Please have a look at below iterator code and let me know what is the problem



template <class T >
class PtrSLink {

  public:
    inline PtrSLink<T>(): element_(0), next_(NULL) {}
    inline PtrSLink<T>(T* Elemval, PtrSLink* nextp):element_(Elemval), next_(nextp){}

    typename T*  element_;      // Elem value for this node
    PtrSLink* next_;  // Pointer to next node in list

};

template <class T,class A=std::allocator<T> >
class PtrSList
{

  which contains _m_pHead, _m_pTail and some insert(),append() function
};

class Iterator : public iterator<std::forward_iterator_tag,T*,typename std::allocator<PtrSLink<T> >::difference_type >
{
  private:
     PtrSLink<T>* _link;

  public:
     //Iterator(PtrSLink<T>* l = 0) : _link(l) { }
     Iterator() : _link(0) { }
     Iterator(PtrSLink<T>* l ) : _link(l) { }
     Iterator(const Iterator& i) : _link(i._link) { }
     Iterator& operator=(const Iterator& i)
     { _link=i._link; return *this; }
  
     T& operator* () const { return *(_link->element_); }
     T* operator->() const { return &(_link->element_); }


     Iterator& operator++() {/*cout<<"++Operator"<<std::endl;;*/ _link=_link->next_;return *this; }

     Iterator operator++(int) { PtrSLink<T>* _tmp = _link; ++(*this);return Iterator(_tmp); }

     T* Item() { return (_link->element_); }
     T* Item() const {/* cout<<"Item  "<<*(_link->element_)<<std::endl;*/ return (_link->element_); }

     bool operator!=(const Iterator& i) const
     {
        //return *Item()!=*i.Item();
        cout<<"!=!="<<*Item()<<std::endl;
        cout<<"!=!="<<*i.Item()<<std::endl;

        if( *Item() != *i.Item() )
        {
         cout<<"operator!= returning true"<<std::endl;
         return true;          
        }
        else
         {
         cout<<"operator!= returning false"<<std::endl;
         return false;      
        }
     }

        bool operator==(const Iterator& i) const
        {
         //return (*Item()!=*i.Item());
         cout<<"=="<<*Item()<<std::endl;
         cout<<"=="<<*i.Item()<<std::endl;

         if( *Item() == *i.Item() )          
         {
         cout<<"operator== returning true"<<std::endl;
         return true;          
         }
         else
         {
         cout<<"operator== returning false"<<std::endl;
         return false;      
         }

        }

};
/////////////////////////Iterator Class///////////////

ANSWER: as indicated by

class Iterator : public iterator<std::forward_iterator_tag,T*,typename std::allocator<PtrSLink<T> >::difference_type >

your Iterator is iterating over a sequence of values of type T*

therefore, operator* should return a reference to the value_type (a T*) that the iterator is identifying:

T& operator* () const { return *(_link->element_); }

should be:

T*& operator* () { return _link->element_ ; }

(to return a const reference, you should use a const_iterator.)

for the same reason, drop const from
T* operator->() { return &(_link->element_); }

this could also be equivalently written as
T* operator->() { return &**this ; }

the operator== should return true if two iterators identify the same value_type (element) of the sequence, false otherwise. ( != is its complement)

therefore, the equality comparison operators should be:

bool operator==(const Iterator& i) const
{
 // _element is a pointer to the node; if the pointers are
 // the same, the nodes are the same. they identify the same
 // 'element' of the sequence.
 return element_ == i.element_ ;
}

bool operator!=(const Iterator& i) const
{
 return element_ != i.element_ ;
}

i think that the unfortunate choice of the name _element for a pointer to the node (it is not an element of the sequence) has lead you astray.  

> i want to check less than operator with two list using lexicographical_compare function.
> I got wrong result.  
> And also, I haven't get proper answer while invoking STL::max_element function when passing input as a my own iterator

this may not be a good idea. as the elements in the sequence are pointers (T*), you would be comparing the pointers (addresses); not what they point to.

i'm curious as to why a std::list is not used. eg.

template < typename T, typename A = std::allocator<T> >
class PtrSList : public std::list< T*, A >
{
 // add constructor, operator= here
 // inheric all else from std::list< T*, A >
};

(an alternative would be to contain and forward).



---------- FOLLOW-UP ----------

QUESTION: Hi Vijayan,

sorry, still i got same problem... This time, i completely pasted my code..
list.h
~~~~~~
#ifndef slist_h
#define slist_h

#include <iostream>
#include <stdlib.h>
#include <iterator>
#include <string>
#include <memory.h>
#include <algorithm>
#include <functional>


using namespace std;


template <class Compare, class T>
struct deref_compare : public std::binary_function<T*, T*, bool>
{
  Compare cmp_;
  deref_compare(const Compare& c = Compare() ) : cmp_(c) {}
  //bool operator()(const T* const x, const T* const y) const
  bool operator()( T*  x,  T*  y)    
  {
     return cmp_(*x,*y);
  }
};

template <class T >
class PtrSLink {

  public:
    inline PtrSLink<T>(): element_(0), next_(NULL) {}
    inline PtrSLink<T>(T* Elemval, PtrSLink* nextp):element_(Elemval), next_(nextp){}

    typename T*  element_;      // Elem value for this node
    PtrSLink* next_;  // Pointer to next node in list

};

template <class T >
class PtrSIterator;

template <class T,class A=std::allocator<T> >
class PtrSList
{
  public: //typdef
     typedef std::allocator<PtrSLink<T> > alloc_type;      

     class Iterator;
     
     friend class Iterator;      

     typedef deref_compare<std::less<T>,T> less;      

  public:
     //Constructor.
     inline PtrSList<T,A>():_m_pHead(NULL),_m_pTail(NULL),_m_pCurr(0),_m_iSize(0) {}
     
     PtrSList<T,A>(const PtrSList<T>& s):_m_pHead(NULL),_m_pTail(NULL),_m_pCurr(NULL),_m_iSize(0)
     {
        PtrSLink<T>* _tmp = s._m_pHead;
        while(_tmp!=NULL)
        {
         insert((_tmp->element_));          
         _tmp=_tmp->next_;
        }
     }

     //Destructor
     ~PtrSList<T,A>()      
     {      
        if(!isEmpty())
         clear();
     }      
     
     void append(T* a);
     
     //Adds the item a to the end of the collection. Returns true
     bool insert(T* a);


     /**************************************De-allocation*****************************/

      void Destroy(PtrSLink<T>* _Node)
     {
        allocator.deallocate(_Node,sizeof(PtrSLink<T>));
     }

     /***************************************End De-allocation*************************/

     //Clears the collection by removing all items from self.
     void clear()
     {      
        _m_pCurr=_m_pHead;
        while(_m_pCurr!=NULL)
        {
         _m_pHead = _m_pHead->next_;
         //allocator.deallocate(_m_pCurr,sizeof(PtrSLink<T>));
         Destroy(_m_pCurr);          
         _m_pCurr = _m_pHead;
        }         
        _m_iSize = 0;
        _m_pTail = NULL;      
     }

     inline size_t entries() const
     {
        return _m_iSize;
     }
     inline bool isEmpty() const
     {
        return ( (_m_iSize == 0 ) ? true : false );
     }   

     void assertElement(size_t i)
      {
        if(i<0 || i>entries() )
         throw std::exception();
     }

     void Print() const;
     

     /////////////////////////Iterator Class///////////////////////////////


     class Iterator : public iterator<std::forward_iterator_tag,T,typename std::allocator<PtrSLink<T> >::difference_type >
     {
        private:
         PtrSLink<T>* _link;

        public:
         Iterator() : _link(0) { }
         Iterator(PtrSLink<T>* l ) : _link(l) { }
         Iterator(const Iterator& i) : _link(i._link) { }
         Iterator& operator=(const Iterator& i)
         { _link=i._link; return *this; }
     
         T*& operator* () const { return _link->element_; }
         T* operator->() const { return (_link->element_); }


         T*& operator* ()  { return _link->element_; }
         T* operator->()   { return &(_link->element_); }


         Iterator& operator++() { _link=_link->next_;return *this; }

         Iterator operator++(int) { PtrSLink<T>* _tmp = _link; ++(*this);return Iterator(_tmp); }

         T* Item() { return (_link->element_); }
         T* Item() const { return (_link->element_); }

         bool operator!=(const Iterator& i) const
         {
         //return *Item()!=*i.Item();
         cout<<"!=!="<<*Item()<<std::endl;
         cout<<"!=!="<<*i.Item()<<std::endl;

         if( *Item() != *i.Item() )
         {
         cout<<"operator!= returning true"<<std::endl;
         return true;          
         }
         else
         {
         cout<<"operator!= returning false"<<std::endl;
         return false;      
         }
         }

         bool operator==(const Iterator& i) const
         {
         //return (*Item()!=*i.Item());
         cout<<"=="<<*Item()<<std::endl;
         cout<<"=="<<*i.Item()<<std::endl;

         if( *Item() == *i.Item() )          
         {
         cout<<"operator== returning true"<<std::endl;
         return true;          
         }
         else
         {
         cout<<"operator== returning false"<<std::endl;
         return false;      
         }

         }

     };
     /////////////////////////Iterator Class///////////////////////////////


     Iterator begin()
     {
        return Iterator(_m_pHead);
     }

     Iterator end()
     {
        return Iterator(_m_pTail);
     }

     Iterator begin() const
     {
        return Iterator(_m_pHead);
     }

     Iterator end() const
     {
        return Iterator(_m_pTail);
     }

     T*& maxElement()
     {
        if( entries() !=0 )          
         return *std::max_element( this->begin(),this->end(),less() );          
         //return *std::max_element( this->begin(),this->end() );          
     }

     T*& minElement()
     {
        if( entries() !=0 )          
         return *std::min_element( this->begin(),this->end(),less() );
         //return *std::min_element( this->begin(),this->end() );
     }

  private:
     PtrSLink<T> * _m_pHead;
     PtrSLink<T> *  _m_pTail;
     PtrSLink<T> * _m_pCurr;
     
     size_t          _m_iSize;

     friend class PtrSIterator<T>;

     alloc_type allocator;
};

template<class T,class A>
inline bool operator==(const PtrSList<T,A> &l,const PtrSList<T,A> &r)
{
  return l.entires()==r.entries() && std::equal(l.begin(),l.end(),r.begin());
}

template<class T,class A>
bool operator<(typename const PtrSList<T,A> &l,typename const PtrSList<T,A> &r)
{
  //return lexicographical_compare(_m_pHead,_m_pTail, (r._m_pHead), (r._m_pTail),cmp);
  return std::lexicographical_compare(l.begin(),l.end(), r.begin(), r.end());
  //return true;
}

#endif;
list.cc
~~~~~~~
#include <list.h>

template <class T,class A>
void PtrSList<T,A>::append (T* a)
{
  PtrSLink<T>* _tmp = (PtrSLink<T>*) allocator.allocate(sizeof(PtrSLink<T>));
  if (_m_pHead == NULL)
   {
  _m_pHead = new(_tmp) PtrSLink<T>(a,NULL);
       _m_pTail = _m_pCurr = _m_pHead;
   }
   else
        //_m_pTail = _m_pTail->next_ = new PtrSLink<T>(a, NULL);
   _m_pTail = _m_pTail->next_ = new(_tmp) PtrSLink<T>(a,NULL);

  _m_iSize++;
}

template <class T,class A>
void PtrSList<T,A>::Print() const
{
  PtrSLink<T>* _tmp = NULL;
  for (_tmp = _m_pHead;_tmp != NULL;_tmp=_tmp->next_)
        cout << * (_tmp->element_) << endl;
}


template <class T,class A>
bool PtrSList<T,A>::insert (T* a)
{
  PtrSLink<T>* _tmp = (PtrSLink<T>*) allocator.allocate(sizeof(PtrSLink<T>));
  if (_m_pHead == NULL)
       {
     //_m_pHead = new PtrSLink<T>(a, NULL);
     _m_pHead = new(_tmp) PtrSLink<T>(a,NULL);
     _m_pTail = _m_pCurr = _m_pHead;
       }
       else
        _m_pTail = _m_pTail->next_ = new(_tmp) PtrSLink<T>(a,NULL);   
      //_m_pTail = _m_pTail->next_ = new PtrSLink<T>(a, NULL);

  _m_iSize++;

  return true;
}

Test.cc
~~~~~~~
# include <list.h>
# include <string.h>
# include <iostream.h>

int main()
{   
 PtrSList<string> l,r;
 PtrSList<int> i;

 cout<<"Construction"<<std::endl;
  
 //l.append(new string(0));
 
 l.insert(new string("A"));
 l.insert(new string("B"));
 l.insert(new string("C"));
 l.insert(new string("D"));
 l.insert(new string("E"));
 
 l.Print();

 cout<<"Max  "<<*(l.maxElement())<<std::endl;

 cout<<"Min  "<<*(l.minElement())<<std::endl;

 r.insert(new string("F"));
 r.insert(new string("G"));
 r.insert(new string("H"));
 r.insert(new string("I"));
 r.insert(new string("J"));

 if(l<r)
    cout<<"True";
 else
    cout<<"False";

 cout<<std::endl;
 
}

Actually, when i invoke max_element() function, from Test.cc file, i always getting result 'max=D' why not max='E' and also less than operator, getting wrong result..
Even min_element also got problem..

Plz..suggest me..






ANSWER: your code would not compile; so i had to make a few changes:
they were
a. remove incorrect use of the typename keyword.
b. modify maxElement, minElement to return iterators.

there were two logical errors:
a. you had refused to correct operator==, operator!= as suggested in my earlier post and they were incorrect.
b. end() should return an iterator corresponding to one past the last element, you were returning one corresponding to the last element.
these were corrected.

these are the corrections (other than incorrect use of typename )

         Iterator begin()
         {
         return Iterator(_m_pHead);
         }

         Iterator end()
         {
         return Iterator(0);
         }

         Iterator begin() const
         {
         return Iterator(_m_pHead);
         }

         Iterator end() const
         {
         return Iterator(0);
         }

         Iterator maxElement()
         {
         return std::max_element( this->begin(),this->end() );
         }

         Iterator minElement()
         {
         return std::min_element( this->begin(),this->end()  );
         }

// ITERATOR
         bool operator!=(const Iterator& i) const
         {
         return _link != i._link ;
         }

         bool operator==(const Iterator& i) const
         {
         return _link == i._link ;
         }

here are the (modified) test program and the results:

int main()
{
   PtrSList<string> l,r;

   string* a = new string("A") ; l.insert(a);
   string* b = new string("B") ; l.insert(b);
   string* c = new string("C") ; l.insert(c);
   string* d = new string("D") ; l.insert(d);
   string* e = new string("E") ; l.insert(e);

   cout << "{elements are}  a: " << a << "  b: " << b << "  c: " << c
         << "  d: " << d << "  e: " << e << '\n' ;

   cout << "Max  " << *( l.maxElement() ) << std::endl;

   cout << "Min  " << *( l.minElement() ) << std::endl;
}


> g++43 -Wall -std=c++98 -pedantic -Werror iterator_test.cc
> ./a.out
{elements are}  a: 0x804c030  b: 0x804c050  c: 0x804c070  d: 0x804c090  e: 0x804c0b0
Max  0x804c0b0
Min  0x804c030


with these in corrections in place, as you can see, the iterator works correctly.



---------- FOLLOW-UP ----------

QUESTION: Thanks you so very vijayan about your answer...
Actuall, i am facing one more issue..
In the same linked list I wrote some functions removeFirst() & removeLast(). I got following compilation error.. Plz..help me how to resolve the issue...

     inline T*& first()    
     {    
        if ( _m_pHead != NULL )
         return (_m_pHead->element_);
        else
         return 0;
     }

     inline  T*const& first() const    
     {
        if ( _m_pHead != NULL )
         return (_m_pHead->element_);
        else
         return 0;
     }

     //Returns a reference to the last item in the collection. If no elements it returns 0
     inline T*& last()    
     {
        if ( _m_pTail != NULL )
         return (_m_pTail->element_);
        else
         return 0;
     }

     inline  T*const& last() const    
     {
        if ( _m_pTail != NULL )
         return (_m_pTail->element_);
        else
         return 0;
     }  

Answer
the error message is self-explanatory:
'A reference return value must be an lvalue'

0 is a literal value for a pointer (that does not point).
you get the error for the same reason that the following is an error:
int i = 7 ;
int& r = i ; // ok, i is an lvalue
int& r1 = 7 ; // error, 7 is not an lvalue.

modify the four functions to return rvalues (as in this example):

      inline T* first()
      {
         if ( _m_pHead != NULL )
         return (_m_pHead->element_);
         else
         return 0;
      }