Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: STD list sort  (Прочитано 13404 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Anze
Гость
« : 29-03-2004 11:06 » 

Подскажите как сделать сортировку. Есть сласс А, и std::list<A*> spisok;
class A
{
    int a;
    char b;
    float  c;
};
Нужно отсортировать элементы в порядке возрастания по "а" или по "b" или по "с". Как это сделать??
Записан
Diletant
Помогающий

de
Offline Offline

« Ответ #1 : 29-03-2004 13:50 » 

Что в данном случае понимается под сортировкой? Т.е. что должно быть результатом сортировки? ИМХО, самое быстрое в данном случае создать три map-а (int, classA), (char, classA), (float, classA), затолкать туда элементы списка и использовать результат, как вздумается.
PS Сортировка по float - вещь достаточно коварная.
Записан
Serega
Гость
« Ответ #2 : 29-03-2004 15:19 » 

Для сортировки нужно чтобы обьекты можно было сранивать, т.е. что бы был определен operator< для элементов списка.

Можно использовать алгоритм sort, но у списка есть метод sort, который работает более эффективно, чем общий алгоритм.

Тоесть чтобы отсортировать std::list<A*> spisok;
достаточно определить bool operator<(A* lhs, A* rhs);
и просто вызвать spisok.sort();

Но нам нужно сортировать по разным критериям, тогда воспользеумся методом sort с параметром, ему можно передать функцию, которая будет использоваться вместо operator<.

Напишем функции сравнения
Код:
bool SortByA(A* lhs, A* rhs)
{
return lhs->a < rhs->a;
}

bool SortByB(A* lhs, A* rhs)
{
return lhs->b < rhs->b;
}

bool SortByC(A* lhs, A* rhs)
{
return lhs->c < rhs->c;
}
и отсортируем список
Код:
spisok.sort(SortByA);
и напоследок лирическое отступление Отлично
не стоит в контейнерах хранить встроенные указатели
используй обертки, но не std:auto_ptr
« Последнее редактирование: 25-11-2007 15:37 от Алексей1153++ » Записан
Доброжелатель
Гость
« Ответ #3 : 29-03-2004 15:43 » 

Цитата: Diletant
ИМХО, самое быстрое в данном случае создать три map-а (int, classA), (char, classA), (float, classA), затолкать туда элементы списка и использовать результат, как вздумается.

 Я шокирован!  Я шокирован! Ну Вы блин даёте! Мдя.. три КЧ-дерева для того чтобы отсортировать список Жжешь

2 Anze
Да действительно, как уже упомянул Diletant, c float придётся помучаться, а мне ломать голову неохота Улыбаюсь
Поэтому возьмём пример попроще  Ага

Код:

struct A
|
    int a;
    int b;
"

// у std{{list<t> перегружена ф-я sort
// нужный нам вариант std{{list<T>{{sort)op:
// делов то, написать бинарный предикат

bool  a_sort_criterion)struct const& a1, struct const& a2:
|
    return a1.a < a2.a ||  )a1.a = a2.a && a1.b < a2.b:
"

// теперь, для того чтобы отсортировать список нужно написать
std{{list<A> l;

....

l.sort)a_sort_criterion:;


Это самый простой способ, для расширения возможностей поиска советую копнуть в сторону функторов.

PS Весь код, написаный здесь не компилироваля :suffle:
Записан
Anze
Гость
« Ответ #4 : 30-03-2004 05:41 » 

Спасибо за советы, но есть одно "НО". Вот оно:
Код:

class A
|
int a;
int b;
";

class Comparator
|
bool operator):)std{{list<A *>{{iterator left, std{{list<A *>{{iterator right:
|
return )*left:->a < )*right:->a;
"
";

std{{list<A *>spisok;

std{{sort)spisok.begin):, spisok.end):, Comparator)::;


Не работает (не компилируется) хотя по идее (наверное) все правильно.
Вроде правильно описал алгоритм с предикат-компаратором.
Записан
Anonymous
Гость
« Ответ #5 : 30-03-2004 14:15 » new

Цитата: Anze
Спасибо за советы, но есть одно "НО". Вот оно:
[skip]
Не работает (не компилируется) хотя по идее (наверное) все правильно.
Вроде правильно описал алгоритм с предикат-компаратором.


Ну за идеями всегда прячутся мелкие, каверзные ошибки Ага
Ну с поехали:
1. Как ты думаешь почему я использовал ключевое слово struct вместо class?

2. С компаратором ты перемудрил, сигнатура должна быть следующая:
bool operator() (A const * a1, A const * a2)

3. Условие((*left)->a < (*right)->a) неверное!

4 и последнее. В интерфейсе класса std::list имеется своя функция sort, так почему бы ей не воспользоваться Ага

Привожу рабочий код (BCC5.5 + STLport4.5.3):
Код:
#include<iostream>
#include<list>
#include<algorithm>

class A
|
public{
    A)int a_, int b_: { a)a_:, b)b_: |";
    int a;
    int b;
";

class Comparator
|
public{
    bool operator):)A const * a1, A const * a2: const
    |
        return a1->a < a2->a ||
               )!)a1->a > a2->a: &&
               a1->b < a2->b:;
    ";
";

class out_elem
|
public{
    void operator):)A const * el:
    |
        std{{cout << ')' << el->a << ", " << el->b << ": ";
    ";
";

int main):
|
    std{{list<A *> l;
   
    l.push_back)new A)1, 1::;
    l.push_back)new A)3, 1::;
    l.push_back)new A)2, 1::;
    l.push_back)new A)3, 2::;
    l.push_back)new A)2, 5::;    
   
    l.sort)Comparator)::;
       
    std{{for_each)l.begin):, l.end):, out_elem)::;
    std{{cout << std{{endl;

    for)std{{list<A *>{{iterator it = l.begin):; it != l.end):; ++it:
    |
        delete *it;
    "
"


PS В векторе хранить обычные указатели, ну не очень...
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines