Форум программистов, компьютерный форум CyberForum.ru

Действительно универсальная сортировка - C++

Восстановить пароль Регистрация
 
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
18.02.2011, 00:30     Действительно универсальная сортировка #1
Вопрос заключается в следующем, возможно-ли сделать такую?

Есть сортировка
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename Iterator, typename Pred>
void quick_sort (Iterator first, Iterator last, Pred pred) {
        Iterator base = first;
        Iterator new_last = last;
                
        if (first != last && first++ != --last) {               
                while (first != last) {
                        while (first != last && !pred(*first, *base)) ++first;
                        while (first != last && pred(*last, *base)) --last;
                        
                        if (first != last) std::swap(*first, *last);
                }
                
                if (pred(*base, *first)) std::swap(*base, *first);
                        
                quick_sort(base, first, pred);
                quick_sort(first, new_last, pred);
        }
}
Сортировка не моя. Но все же.
Допустим так же, что у нас есть сортировка которая сортирует список элементов.

C++
1
2
3
4
void sort()
{
    quick_sort(begin(), end(), std::greater<T>());
}
ПОД-ы отсортирует без проблем.
Но допустим так же, что у нас есть такие классы.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Figure
{
public:
   virtual int GetSquare()=0;
   virtual bool operator <(Figure* Ob)=0;
};
 
class Square:public Figure
{
public:
   Square(int a_):a(a_)
   {
   }
   int GetSquare()
   {
       return a*a;
   }
   bool operator <(Figure* Ob)
   {
      return GetSquare() < static_cast<Square*>(Ob)->GetSquare();
   } 
private:
   int a;
};
 
class Triangle:public Figure
{
public:
   Triangle(int a_):a(a_)
   {
   }
   int GetSquare()
   {
       return (a*a)/2;
   }
   bool operator <(Figure* Ob)
   {
      return GetSquare() < static_cast<Triangle*>(Ob)->GetSquare();
   } 
private:
   int a;
};
 
int main()
{
    List<Figure*> Lst;
    Lst.push_back(new Square(5));
    Lst.push_back(new Triangle(4));
    Lst.push_back(new Square(7));
    Lst.push_back(new Triangle(3));
    Lst.sort();
    for(List<Figure*>::iterator iter=Lst.begin(); iter != Lst.end(); ++iter)
    {
         std::cout<<(*iter)->GetSquare()<<'\n';
    }
    return 0;
}
Сортировка в этом случае не сработает. Ибо даже не будет заходить в функцию сравнения элементов, потому как один из параметров мол должен быть объектом класса, но не указателем на него (что-то вроде). Получается для указателей нужна другая сортировка с разыменованием первого параметра? Или возможна универсальная? Как быть?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
18.02.2011, 00:50     Действительно универсальная сортировка #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
template< class T >
struct pointerComp : public binary_function<T*,T*,bool>{
  bool operator()(T* t1, T* t2){
    return( *t1 < t2 );
  }
};
 
//
 
Lst.sort(pointerComp<Figure>());
или ты ожидаешь чего-то концептуального?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
18.02.2011, 00:54  [ТС]     Действительно универсальная сортировка #3
alex_x_x, Интересно. Вполне себе вариант. Возьму как основной пока что...
Я так понимаю, что это впринципе единственный вариант по сути (кроме написания новой функции, который не хотелось бы применять).
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
18.02.2011, 00:58     Действительно универсальная сортировка #4
ForEveR, ну компоратора, может даже стандартные для указателей есть, не знаю
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
18.02.2011, 01:04  [ТС]     Действительно универсальная сортировка #5
alex_x_x, Не, вроде для указателей нету. Спасибо большое. Как-то функтор в голову не пришел.
Yandex
Объявления
18.02.2011, 01:04     Действительно универсальная сортировка
Ответ Создать тему
Опции темы

Текущее время: 21:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru