qSort of "List of Lists"

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

Ответить
zhuk
Сообщения: 1
Зарегистрирован: 13 окт 2004, 14:03

qSort of "List of Lists"

Сообщение zhuk » 13 окт 2004, 14:28

я написал такую вот програмку. По идее она должна сортироват полиномы. Список полиномов хранится в list_of_lists1. Получается список из списков. Проблема в том что:

Код: Выделить всё

 list_of_list1.sort(member_lexicographical_compare());
не подходит из-за специфики задания, А написать свою функцию у меня не получается.

Код: Выделить всё

#include <iostream>
#include <time.h>      // time
#include <list>        // to create a list with STL templates
#include <algorithm>   // to use lexicographical_compare() function
#include <math.h>      // to use rand() function
#include <fstream>     // file I/O
#include <iterator>
 using namespace std; 



// declaration of List and "List of Lists" 
 typedef list<int> List;
 typedef list<List> ListOfList;
 
// functoid to for a sorting algorithm 
 struct member_lexicographical_compare{
     bool operator()(const List &lhs, const List &rhs){
         return lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
     }
 }; 
 
template <typename T>
void quicksort(T begin, T end) {
    if (begin != end) {
     T middle = partition (begin, end, bind2nd(member_lexicographical_compare(), *begin));
        sort (begin, middle);
        sort (max(begin + 1, middle), end);
    }
}

 


// a print list function
 void print_list(const List& list1, int id) {
     ostream_iterator<int> out(cout, " ");
     cout << "list " << id << ": ";
     copy(list1.begin(), list1.end(), out);
     cout << endl;
 }
 
// a random number[a,b] generation function
 int randInt(int a,int b){
     return a + rand() % (b - a + 1);
 }
// main function
 int main () {
     int poly_number, members_number, members_number_rand,members_range_min,members_range_max;
     ListOfList list_of_list1;
     
// some user defined data     
     srand(unsigned(time(NULL)));
     cout << "Polynomes number? (0 for random): " ;
     cin >> poly_number;
     if(poly_number==0) poly_number=randInt(1,100);
     cout << endl << "Members number? (0 for random): ";
     cin >> members_number;
     cout << endl << "Members range min, max?: ";
     cin >> members_range_min >> members_range_max;
     cout << endl << endl << "System of polynomes: ";
     cout << endl;

// a "list of lists" with list as container generation loop
     for(int i = 0; i < poly_number; ++i) {
         List list1;
/*
   a list generation loop. Fitst one with fixed polynome
   length second with random
*/
         if(members_number!=0){
             for(int j = 0; j < members_number; ++j) {
                 list1.push_back(randInt(members_range_min,members_range_max));
             }
         }else{
// this one fills not used members with zero value
             members_number_rand = randInt(1,10);
             for(int b =  members_number_rand; b < 10; ++b) {
                 list1.push_back(0);
             }
             for(int j = 0; j < members_number_rand; ++j) {
                 list1.push_back(randInt(members_range_min,members_range_max));
             }

         }
/*
   this part prints a polynome(list) and push it to the system of polynomes(list
   of lists)
*/
         print_list(list1, i+1);
         list_of_list1.push_back(list1);
     }


    cout << endl;

/* 
   this thing sorts list_of_list1 relying on member_lexicographical_compare()
   functoid(compare method). C++ uses qsort sorting wich was modifyed to compare
   lists
*/
/*
   ne podxodit
   list_of_list1.sort(member_lexicographical_compare());
*/
    quicksort (list_of_list1.begin(), list_of_list1.end());

// Printing out sorted list    
    ListOfList::iterator it = list_of_list1.begin();
    for(int j = 1; it != list_of_list1.end(); ++it, ++j) {
        const List& list1 = *it;
        print_list(list1, j);
    }
     
int i;
cin >> i;
     return 0;
 }

functor для сравнения списков:

Код: Выделить всё

member_lexicographical_compare()
При компиляции выдаёт такие ошибки:

Код: Выделить всё

U:/programs/cpp/POLYN~JQ.CPP: In instantiation of `std::binder2nd<member_lexicographical_compare>':
U:/programs/cpp/POLYN~JQ.CPP:27:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
U:/programs/cpp/POLYN~JQ.CPP:27: no type named `first_argument_type' in `struct 
   member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:389: no type named `
   second_argument_type' in `struct member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:393: no type named `
   second_argument_type' in `struct member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:395: no type named `
   result_type' in `struct member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:401: no type named `
   result_type' in `struct member_lexicographical_compare'

U:/programs/cpp/POLYN~JQ.CPP: In function `void quicksort(T, T) [with T = 
   std::_List_iterator<List, List&, List*>]':
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
U:/programs/cpp/POLYN~JQ.CPP:29: no match for `std::_List_iterator<List, List&, 
   List*>& + int' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h: In function 
   `std::binder2nd<_Operation> std::bind2nd(const _Operation&, const _Tp&) 
   [with _Operation = member_lexicographical_compare, _Tp = std::list<int, 
   std::allocator<int> >]':
U:/programs/cpp/POLYN~JQ.CPP:27:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:412: no type named `
   second_argument_type' in `struct member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_function.h:413: no type named `
   second_argument_type' in `struct member_lexicographical_compare'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h: In function `void 
   std::sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = 
   std::_List_iterator<List, List&, List*>]':
U:/programs/cpp/POLYN~JQ.CPP:28:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2178: no match for `
   std::_List_iterator<List, List&, List*>& - std::_List_iterator<List, List&, 

   List*>&' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h: In function 
   `_BidirectionalIter std::__partition(_BidirectionalIter, _BidirectionalIter, 
   _Predicate, std::bidirectional_iterator_tag) [with _BidirectionalIter = 
   std::_List_iterator<List, List&, List*>, _Predicate = 
   std::binder2nd<member_lexicographical_compare>]':
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1758:   instantiated from `_ForwardIter std::partition(_ForwardIter, _ForwardIter, _Predicate) [with _ForwardIter = std::_List_iterator<List, List&, List*>, _Predicate = std::binder2nd<member_lexicographical_compare>]'
U:/programs/cpp/POLYN~JQ.CPP:27:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1717: no match for call to 
   `(std::binder2nd<member_lexicographical_compare>) (std::list<int, 
   std::allocator<int> >&)'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1758:   instantiated from `_ForwardIter std::partition(_ForwardIter, _ForwardIter, _Predicate) [with _ForwardIter = std::_List_iterator<List, List&, List*>, _Predicate = std::binder2nd<member_lexicographical_compare>]'
U:/programs/cpp/POLYN~JQ.CPP:27:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1725: no match for call to 
   `(std::binder2nd<member_lexicographical_compare>) (std::list<int, 
   std::allocator<int> >&)'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h: In function `void 
   std::__final_insertion_sort(_RandomAccessIter, _RandomAccessIter) [with 
   _RandomAccessIter = std::_List_iterator<List, List&, List*>]':
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2179:   instantiated from `void std::sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:28:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2056: no match for `
   std::_List_iterator<List, List&, List*>& - std::_List_iterator<List, List&, 
   List*>&' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2057: no match for `
   std::_List_iterator<List, List&, List*>& + std::<anonymous enum>' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2058: no match for `
   std::_List_iterator<List, List&, List*>& + std::<anonymous enum>' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h: In function `void 
   std::__insertion_sort(_RandomAccessIter, _RandomAccessIter) [with 
   _RandomAccessIter = std::_List_iterator<List, List&, List*>]':
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2061:   instantiated from `void std::__final_insertion_sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<List, List&, List*>]'

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2179:   instantiated from `void std::sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:28:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1980: no match for `
   std::_List_iterator<List, List&, List*>& + int' operator

C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2061:   instantiated from `void std::__final_insertion_sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<List, List&, List*>]'
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:2179:   instantiated from `void std::sort(_RandomAccessIter, _RandomAccessIter) [with _RandomAccessIter = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:28:   instantiated from `void quicksort(T, T) [with T = std::_List_iterator<List, List&, List*>]'
U:/programs/cpp/POLYN~JQ.CPP:107:   instantiated from here
C:/Program Files/Dev-Cpp/include/c++/bits/stl_algo.h:1984: no match for `
   std::_List_iterator<List, List&, List*>& + int' operator

Execution terminated
причом пока я не обрашаюсь к функции quicksort ошибок нет.

P.s.
Кто нибудь может подсказать как заменить эту функцию алгоритмом :

Код: Выделить всё

partition (begin, end, bind2nd(member_lexicographical_compare(), *begin));
Зарание спасибо

Ответить