VPF::И опять сортировка списка в STL - Форум программистов

AlexanderV

Дата 15.5.2006, 12:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 49
Регистрация: 31.8.2005
Где: Украина, Киев

Репутация: нет
Всего: нет

Нужно отсортировать 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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 2124
Регистрация: 25.3.2002
Где: Москва

Репутация: 9
Всего: 59

Код



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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 2124
Регистрация: 25.3.2002
Где: Москва

Репутация: 9
Всего: 59

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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

)

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

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

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

)

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

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

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

--------------------

...

AlexanderV

Дата 15.5.2006, 19:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 49
Регистрация: 31.8.2005
Где: Украина, Киев

Репутация: нет
Всего: нет

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

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

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

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

MAKCim

Дата 15.5.2006, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207

Цитата

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

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

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

bsa

Дата 15.5.2006, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

MAKCim

Дата 15.5.2006, 19:13 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207

Цитата

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

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

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

AlexanderV

Дата 15.5.2006, 19:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 49
Регистрация: 31.8.2005
Где: Украина, Киев

Репутация: нет
Всего: нет

MSVC++6

Earnest

Дата 15.5.2006, 19:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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

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

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

--------------------

...

AlexanderV

Дата 15.5.2006, 19:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 49
Регистрация: 31.8.2005
Где: Украина, Киев

Репутация: нет
Всего: нет

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

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

bsa

Дата 15.5.2006, 22:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

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

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

AlexanderV

Дата 15.5.2006, 22:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 49
Регистрация: 31.8.2005
Где: Украина, Киев

Репутация: нет
Всего: нет

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

Earnest

Дата 16.5.2006, 07:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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

--------------------

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »