PDA

Просмотр полной версии : qSort of "List of Lists"



zhuk
13.10.2004, 15: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_rang e_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));


Зарание спасибо