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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
#1

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

18.02.2011, 00:30. Просмотров 1033. Ответов 4
Метки нет (Все метки)

Вопрос заключается в следующем, возможно-ли сделать такую?

Есть сортировка
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;
}
Сортировка в этом случае не сработает. Ибо даже не будет заходить в функцию сравнения элементов, потому как один из параметров мол должен быть объектом класса, но не указателем на него (что-то вроде). Получается для указателей нужна другая сортировка с разыменованием первого параметра? Или возможна универсальная? Как быть?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2011, 00:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Действительно универсальная сортировка (C++):

Универсальная функция - C++
Напишите пожалуйста прогу.Написать универсальную функцию для вычислениия заданных выражений.В main() обеспечить вызов этой функции и...

Универсальная программа тестирования - C++
Напишите универсальную программу тестирования. Тест, последовательность вопросов и варианты ответов должны находиться в текстовом файле....

Универсальная функция получения числа через cin - C++
Пытался написать универсальную функцию для гарантированного получения числа нужного типа, примерно так: // Функция для безопасного...

Универсальная функция считывания переменных из бинарного файла - C++
Подскажите, написал запись в бинарный файл переменных, не могу считать, точнее функция должна быть универсальная под любой тип считывания ...

Универсальная функция для приема разных двумерных массивов - C++
В программе у меня много двумерных массивом разной размерности. Мне нужна одна функция (общая) чтобы работала на все массивы. Функция...

Помогите с действительно простой задачкой. - C++
Дан код: /* Conditional expressions */ #include &lt;stdio.h&gt; #include &lt;iostream&gt; int main() { int x=1; int y=1; int...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
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>());
или ты ожидаешь чего-то концептуального?
1
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
18.02.2011, 00:54  [ТС] #3
alex_x_x, Интересно. Вполне себе вариант. Возьму как основной пока что...
Я так понимаю, что это впринципе единственный вариант по сути (кроме написания новой функции, который не хотелось бы применять).
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
18.02.2011, 00:58 #4
ForEveR, ну компоратора, может даже стандартные для указателей есть, не знаю
1
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
18.02.2011, 01:04  [ТС] #5
alex_x_x, Не, вроде для указателей нету. Спасибо большое. Как-то функтор в голову не пришел.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2011, 01:04
Привет! Вот еще темы с ответами:

Проверить, действительно ли число является палиндромом - C++
Проверить истинность высказывания: «Данное четырехзначное число читается одинаково слева направо и справа налево». нужен код плз :)

Действительно ли new выделяет память в куче (heap)? - C++
Чаще всего пишут что в куче . Ок . Куча процесса это вроде бы блок вполне конкретного размера . Я помню раньше это было 1Мб для intel и 4Мб...

Действительно ли использование шаблонов снижает производительность программы? - C++
Просветите пожалуйста. Шаблоны в программе снижают её производительность или нет? и намного ли они больше занимают память чем обычные...

Множественное наследование - когда оно действительно нужно? - C++
Здравствуйте! До изучения языка C++ я программировал на языках типа Java и C#, где множественное наследование от классов явно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.02.2011, 01:04
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru