You are here:



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;
        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);

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


All Answers

Answers by Expert:

Ask Experts




my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.


about 15 years or so

post graduate engineer

©2016 All rights reserved.