Expert: vijayan - 9/30/2008

Question
Hi Vijayan,

 I would like to know what is Leaxicographical_compare? I want to implement in linked list for operator < ( less than ) without using Iterator part. i have pasted some code.. Plz.. let me know is this correct way of implementations.

template <class T,class A>
bool PtrSList<T,A>::operator<(const PtrSList<T,A> &r) const               
{
  if ((*this).entries() == r.entries())
  {
     PtrSLink<T>* _tmp=r._m_pHead;
     PtrSLink<T>* _tmp1=(*this)._m_pHead;
     for(;_tmp;_tmp=_tmp->next_,_tmp1=_tmp1->next_)
     {         
        if( ! ( *(_tmp->element_)<*(_tmp1->element_)  )  )
           return false;         
     }
     return true;
  }
  return false;
}

template <class T,class A>
bool PtrSList<T,A>::operator<(const PtrSList<T,A> &r) const               
{
  PtrSLink<T>* _tmp=r._m_pHead;
  PtrSLink<T>* _tmp1=(*this)._m_pHead;

  T* _First1 = _m_pHead->element_;
  T* _Last1  = _m_pTail->element_;

  T* _First2 = r._m_pHead->element_;
  T* _Last2  = r._m_pTail->element_;

  for (; *_First1 != *_Last1; _tmp = _tmp->next_, _tmp1 = _tmp1->next_)
  if (*_First2 == *_Last2 || *_First2 < *_First1)
  return (false);
  else if (*_First1 < *_First2)
  return (true);
  return (*_First2 != *_Last2);
}

Answer
The name of the lexicographic order stems from the order given to words in a dictionary:
a sequence of letters (that is, a word)

   a1a2 ... ak

appears in a dictionary before a sequence

   b1b2 ... bk

if and only if the first ai which is not equal to bi comes before bi in the alphabet.
The above assumes that words have the same length; this can be achieved by padding out the shorter word with spaces at the end. And to consider that a space is smaller than any other element.

so to compare two sequences of integers (say two vectors) lexicographically, we could write

#include <vector>
#include <algorithm>

// return true if first compares lexicographically less than second
bool lexicographical_compare( const std::vector<int>& first,
                             const std::vector<int>& second )
{
     std::size_t min_size = std::min( first.size(), second.size() ) ;

     for(std::size_t i=0 ; i<min_size ; ++i )
     {
           if( first[i] < second[i] ) return true ;
           if( first[i] > second[i] ) return false ;
           // first[i] == second[i], look at the next element
     }

     // all elements of the sequence compare equal upto min_size, so
     return first.size() < second.size() ;
}