fork download 
  1. #include <cstdlib>
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <string>
  6.  
  7. template < typename T >
  8. struct Node {
  9.  
  10.     T data;
  11.     Node * next;
  12.  
  13.     Node( T const & data )
  14.     : data( data ), next( 0 ) { }
  15.  
  16.     ~Node() {
  17.         delete next;
  18.     }
  19. };
  20.  
  21. template < typename T >
  22. struct LinkedList {
  23.  
  24.     Node<T> * head;
  25.     size_t size;
  26.  
  27.     // inner class
  28.     struct Wrapper {
  29.  
  30.         bool (*callee)( T const &, T const & );
  31.  
  32.         Wrapper( bool (*callee)(T const &, T const &) ) 
  33.         : callee( callee ) { }
  34.  
  35.         bool operator()( Node<T> const * lhs, Node<T> const * rhs ) {
  36.             return (*callee)( lhs->data, rhs->data );
  37.         }
  38.     };
  39.  
  40.     LinkedList() 
  41.     : head( 0 ), size( 0 ) { }
  42.  
  43.     ~LinkedList() {
  44.         delete head;
  45.     }
  46.  
  47.     void add( Node<T> * elem ) {
  48.         elem->next = head;
  49.         head = elem;
  50.         ++size;
  51.     }
  52.  
  53.     void sort( bool (*cmp)(T const &, T const &) ) {
  54.  
  55.         Node<T> ** nodes = new Node<T>*[ size ];
  56.         size_t idx = 0;
  57.         for( Node<T> * curr = head; curr != 0; curr = curr->next ) {
  58.             nodes[ idx++ ] = curr;
  59.         }
  60.  
  61.         std::sort( nodes, nodes+size, Wrapper(cmp) );
  62.         head = nodes[ 0 ];
  63.         for( idx = 1; idx != size; ++idx ) {
  64.             nodes[ idx-1 ]->next = nodes[ idx ];
  65.         }
  66.         nodes[ size-1 ]->next = 0;
  67.         delete [] nodes;
  68.     }
  69. };
  70.  
  71. bool userDefinedComparator( std::string const & lhs,
  72.                             std::string const & rhs ) {
  73.     return rhs < lhs;                                
  74. }
  75.  
  76. int main() {
  77.  
  78.     using namespace std;
  79.  
  80.     LinkedList<string> ll;    
  81.     ll.add( new Node<string>("world") );
  82.     ll.add( new Node<string>("the") );
  83.     ll.add( new Node<string>("hello") );
  84.  
  85.     for( Node<string> * curr = ll.head; curr != 0; curr = curr->next ) {
  86.         cout << curr->data << " ";
  87.     }
  88.     cout << endl;
  89.  
  90.     ll.sort( &userDefinedComparator );
  91.  
  92.     for( Node<string> * curr = ll.head; curr != 0; curr = curr->next ) {
  93.         cout << curr->data << " ";
  94.     }
  95.     cout << endl;
  96. }
Success #stdin #stdout 0.02s 2816KB
comments (?)
stdin 
Standard input is empty
stdout 
hello the world 
world the hello
https://ideone.com/TAWlqc
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!