Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > И опять сортировка списка в STL

Автор: AlexanderV 15.5.2006, 12:12

Нужно отсортировать STL-список (list), содержащий указатели на пользовательския структуры.

Стандартный алгоритм sort не работает для списка (для vector(массива) - отлично работает).
Остаеться стандартный алгоритм sort в классе list. Он не поддерживает перегрузки функторов, и поэтому единственный возможный способ - это перегрузить оператор сравнения ">". Но он не перегружается! Из-за того, что надо сравнить не структуры, а указатели на них.

Стандартное сравнивание указателей, понятно, не приводит к правильной сортировке списка.

Код






#include <list>
using namespace std;


struct s1
{
    int n;
    s1(int i){n=i;}

    /*friend bool operator > (s1* p1,s1* p2) //не работает!!!
    {
        return p1->n<p2->n;
    }*/
};

void printlist(char* title,list<s1*> s)
{
    list<s1*>:: iterator i;
    printf("%s\n",title);

    i = s.begin();
    while(i!=s.end())
    {
        printf("%d ",(*i)->n);
        i++;
    }

    printf("\n");
}

int main()
{
    
    int end = 0;
    list<s1*> s;


    s.push_back(new s1(4));
    s.push_back(new s1(8));
    s.push_back(new s1(9));
    s.push_back(new s1(2));


    printlist("not sorted:",s);

    //
    s.sort(greater<s1*>()); //можно и s.sort, это ничего не меняет
    //

    printlist("sorted:",s);

    scanf("%d",&end);

    return 0;
}

результат:
not sorted:
4 8 9 2
sorted:
8 9 2 4

Если это никак нельзя правильно заставить работать, какой вообще толк от STL?
Буду рад любому варианту решения проблемы.

Автор: Vyacheslav 15.5.2006, 12:51

Код



struct s1
{
    int n;
    s1(int i){n=i;}

    /*friend bool operator > (s1* p1,s1* p2) //не работает!!!
    {
        return p1->n<p2->n;
    }*/
};

class Comparator
{
public:
  bool operator()(s1* a, s1* b)
  {
    return a->n < b->n;
  }

};



void printlist(char* title,list<s1*> s)
{
    list<s1*>:: iterator i;
     cout <<   title;

    i = s.begin();
    while(i!=s.end())
    {
        cout << (*i)->n ;
        i++;
    }

    cout << endl;
}

int main()
{
    
    int end = 0;
    list<s1*> s;


    s.push_back(new s1(4));
    s.push_back(new s1(8));
    s.push_back(new s1(9));
    s.push_back(new s1(2));


    printlist("not sorted:",s);

    //
    //s.sort(greater<s1*>()); //можно и s.sort, это ничего не меняет
    //
    s.sort( Comparator() );

     printlist("sorted:",s);
    return 0;
}

Автор: Earnest 15.5.2006, 16:30

Vyacheslav, обращаю внимание на это:

Цитата(AlexanderV @ 15.5.2006, 13:12

)

Он не поддерживает перегрузки функторов

Не все версии STL поддерживают list::sort с предикатами.
А ты как раз дал решение с пользовательским предикатом.

AlexanderV, если твоя STL точно не поддерживает list::sort с пользовательским предикатом, то просто скопируй свои указатели во временный вектор, отсортируй и скопируй обратно (всего-то 2 лишних строчки):

Код


void sort_list (my_list& l) 
{
   std::vector<sl*> tmp(l.begin(),l.end());

   std::sort(tmp.begin(),tmp.end(),my_predicat());

   l.assign(tmp.begin(),tmp.end());
}

Автор: Vyacheslav 15.5.2006, 18:23

Цитата(Earnest @ 15.5.2006, 16:30

)

Не все версии STL поддерживают list::sort с предикатами.

Угу. Тогда откуда у него в коде sort c использованием темплейтного функтора? smile

Код


 s.sort(greater<s1*>());

Ну в конце концов у него и специализация не поддерживается?
Например, так

Код


template <>
struct greater<s1*> : public binary_function<s1*,s1*,bool>
{
  bool operator()(const s1*& __x, const s1*& __y) const { return __x->n > __y->n; }
};

Или воспользоваться наследованием

Код


struct my_greater : public greater<s1*>
{
 bool operator()(const s1*& __x, const s1*& __y) const { return __x->n > __y->n; }
};

Вообще я лично не понял, что такое "Он не поддерживает перегрузки функторов". Если принять наиболее распространненое понятие, предполагающее что функторы - это только классы с перегруженным оператором(), то причем здесь тогда "перегрузка функторов"?

Автор: Earnest 15.5.2006, 19:04

Цитата(Vyacheslav @ 15.5.2006, 19:23

)

Тогда откуда у него в коде sort c использованием темплейтного функтора?

А фиг его знает... просмотрела, честно говоря... smile

Цитата(Vyacheslav @ 15.5.2006, 19:23

)

Вообще я лично не понял, что такое "Он не поддерживает перегрузки функторов".

Ну, работала я как-то с версией STL, которая имеет только функцию list::sort() без параметров, подразумевающую сортировку с оператором <. Я так это и поняла.

Ну, в общем, всегда можно выкрутиться.

Автор: AlexanderV 15.5.2006, 19:05

Похоже, мой компилятор окончательно устарел smile

Я пробовал и создавать новые функторы, производные от greater - ни хрена не работает. Используеться стандартный оператор (), что вызывает ошибку.

Копирование в временный вектор решает проблему, но слишком грубо. Программа критична к скорости выполнения.

А где можно скачать последнюю версию STL (если можно вообще)?

Автор: MAKCim 15.5.2006, 19:10

Цитата

Тогда откуда у него в коде sort c использованием темплейтного функтора?

быть может пытался использовать но не получилось smile

Автор: bsa 15.5.2006, 19:10

http://www.sgi.com/tech/stl/

Автор: MAKCim 15.5.2006, 19:13

Цитата

Похоже, мой компилятор окончательно устарел

какой компилятор?
в g++ 4.0.2 такое прокатывает

Автор: AlexanderV 15.5.2006, 19:17

MSVC++6

Автор: Earnest 15.5.2006, 19:17

Лучше использовать stl_port. А может, компилятор пора сменить?

Кстати, копирование по сравнению с сортировкой добавит тебе всего ~2N. В том смысле, что время выполнения так и останется ~ NlogN. Не стоит париться с оптимизацией, пока не убедишься, что проблемы действительно есть (причем с помощью профилитора).

Кроме того, встает вопрос: если тебе нужен сортированный список, то список ли тебе нужен? Подходящий выбор контейнера тоже может поспособствовать быстродействию.

Автор: AlexanderV 15.5.2006, 19:38

Если так уже говорить, то STL - вообще медленная часть программы. Самое эффективное - это использование обычных массивов и структур.

А какую версию STL качать, чтоб она была совместима с MSVC++ 6.0?

Автор: bsa 15.5.2006, 22:12

Не уверен, что самая медленная. Быстрее, думаю, не сделаешь. Разве что на ассемблере с учетом оптимизации размещения кода под P4 и использования SSE инструкций, может что и ускоришь. Но оно тебе надо?!?

Добавлено @ 22:15
Я думаю, STL 3.3 подойдет. Там написаны специальные версии для VC 4.2, а про VC 6 ничего не написано.

Автор: AlexanderV 15.5.2006, 22:38

Скачал STL 3.3 как только пробую компилировать - сплошные ошибки в файлах iostream и им подобных. В общем, полная ж***! Уже блин не знаю что и делать! Хоть новый диск Visual Studio покупать!

Автор: Earnest 16.5.2006, 07:52

AlexanderV, чтобы сконфигурировать STL стороннего разработчика под 6ю студию нужно наверняка покопаться в заголовках. Там должно быть какое-то описание.
Но лучше переходи на 7ю студию - там STL вполне приличная, да и сам компилятор тоже гораздо лучше.

Автор: Vyacheslav 16.5.2006, 10:40

Цитата(AlexanderV @ 15.5.2006, 19:17)

MSVC++6

Понятно

Оставь тот STL, который был
Вот это будет работать. Проверено на MSVC++6

Код


using namespace std;

//...
namespace std{
template <>
 struct greater<s1*> : public binary_function<s1*,s1*,bool>
 {
   bool operator()(const s1*& __x, const s1*& __y) const { return __x->n > __y->n; }
 };
}

//...
 s.sort(greater<s1*>())
//...

PS. Здесь ключевое "namespace std{"

Добавлено @ 10:47
кстати и наследование, обрамленное в namespace тоже сработает

Код


namespace std{
struct my_greater : public greater<s1*>
{
  bool operator()(const s1*& __x, const s1*& __y) const { return __x->n > __y->n; }
};
}

Это ж Microsoft, понимаешь smile

Автор: AlexanderV 16.5.2006, 12:06

Спасибо!

Только второй способ не работает. Он хоть и компилируется, но не работает. smile

Но первого уже достаточно!

Автор: AlexanderV 16.5.2006, 12:51

Новая проблема smile

Если всунуть в s1 список
list<s1*> s4;
то
template<>struct greater
будет выдавать ошибку, так как в файле list.h что-то происходит.

Как быть?

Автор: Vyacheslav 16.5.2006, 14:27

Цитата(AlexanderV @ 16.5.2006, 12:06

)

Только второй способ не работает.

У меня работают оба.

Цитата(AlexanderV @ 16.5.2006, 12:51

)

Как быть?

Добавь перед объявлением струтуры forward definition для s1 и greater<s1*>

Код


struct s1;
namespace std{
template <> struct greater<s1*>;
}

Автор: AlexanderV 16.5.2006, 19:30

А как сделать forward definition для s2 который вложен в s1?

Автор: Vyacheslav 17.5.2006, 09:26

Код в студию, плиз. На словах - это только гадать.

Автор: Vyacheslav 17.5.2006, 11:03

Наверное что-то вроде этого

Код


struct s1
{

    int n;
    s1(int i){n=i;}

    list<s1*> m_list;

    struct s2;  
   
    template <> friend struct std::greater<s2*>;
  
    struct s2 
    {
//...

Автор: AlexanderV 17.5.2006, 21:02

Да! Это то, что надо! Спасибо smile