0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
1

Создание шаблонной функции сортировки с предикатом

05.06.2017, 16:04. Показов 2431. Ответов 8
Метки нет (Все метки)

MrGluck, Более менее проясняется. Но мне нельзя пользоваться функциями из библиотек. Нужно написать что то аналогичное std::sort и уже в неё передавать компараторы. Правильно я понимаю что эта моя функция должна быть вне всех классов?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.06.2017, 16:04
Ответы с готовыми решениями:

Создание шаблонной функции
Создать шаблонную функцию, изменяющий порядок элементов таким образом: первая половина списка...

Шаблоны. Явное создание экземпляра шаблонной функции
Не совсем понимаю, зачем нужно явное создание экземпляров шаблонной функции: #include <iostream> ...

Создание специализации шаблонной функции и задача на std::vector
Здравствуйте, подскажите, пожалуйста: 1.В чем ошибка объявления специализации шаблонной...

Создание шаблонной функции для работы с массивами разных типов данных
Здравствуйте. Столкнулся со следующей проблемой: не могу написать шаблонную функцию подсчета суммы...

8
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.06.2017, 16:11 2
Цитата Сообщение от Степан174174 Посмотреть сообщение
Правильно я понимаю что эта моя функция должна быть вне всех классов?
Желательно её сделать шаблонной, "вне классов". Первый параметр шаблона - тип объекта (можно принимать два указателя/итератора, как в STL, можно массив), второй - компаратор.
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
05.06.2017, 16:36  [ТС] 3
MrGluck, начал писать функцию. Пока пришёл к такому, дальше не знаю что делать. На данном этапе выдаёт кучу ошибок. Не подскажете что не так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
template <class Predicate, class ValueType>
void Sorting(Iterator<ValueType> begin, Iterator<ValueType> end, Predicate condition) {
    
    for (Iterator<ValueType> tmp = begin; tmp != end; --tmp)
            if (condition(static_cast<Node<ValueType>*>(tmp)->value, static_cast<Node<ValueType>*>(tmp++)->value))
 {  
 
 
 
        }
    
}
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.06.2017, 16:45 4
Степан174174, что за Node такой? К чему это вообще?
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
05.06.2017, 16:50  [ТС] 5
MrGluck, Это элемент списка, который уже содержит данные. Вот целиком код чтобы было проще.
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
struct NodeBase {
    NodeBase *prev; // указатель на предыдущий элемент связного списка
    NodeBase *next; // указатель на следующий элемент связного списка
                    // при создании объекта класса конструктор по-умолчанию
                    // назначает следующий и предыдущий элемент указывать на себя 
    NodeBase() : prev(this), next(this) {}
    // при создании с таким констуктором, элемент добавляет сам себя
    // в связный список, представляя себя предыдущему и следующему элементу
    NodeBase(NodeBase *prev_, NodeBase *next_)
        : prev(prev_), next(next_) { // назначаются предыдущий и следующий элементы
                                     // у предыдущего элемента следующим элементом назначается данный элемент
                                     // и у следующего элемента предыдущим элементом назначается данный элемент
        prev->next = next->prev = this;
    }
    // деструктор. при удалении элемента связного списка, 
    // элемент убирает сам себя из списка
    virtual ~NodeBase() {
        prev->next = next;
        next->prev = prev;
    }
};
 
// элемент связного списка, уже содержащий данные.
template <typename ValueType>
struct Node : public NodeBase {
    ValueType value; // то значение, которое хранит класс
                     // конструктор подставляет значения и вызывает конструтор предка
    Node(NodeBase *prev_, NodeBase *next_, ValueType value)
        : NodeBase(prev_, next_), value(value) {}
};
 
// итератор. класс, который позволит получать доступ к данным,
// сохранив инкапсуляцию
template <typename ValueType>
struct Iterator {
private:
    // собственно, элемент связного списка, который хранит итератор
    NodeBase *node;
public:
    // создание итератора при помощи элемента связного списка
    explicit Iterator(NodeBase *node_) : node(node_) {}
    // создание копированием с другого итератора
    Iterator(const Iterator &other) : node(other.node) {}
    // получение значения элемента связного списка
    ValueType &operator*() {
        return static_cast<Node<ValueType>*>(node)->value;
    }
    // присваивание итератору другого итератора
    Iterator &operator=(const Iterator &other) {
        if (&other != this)
            node = other.node;
        return *this;
    }
    // переход к следующему элементу (постфиксный)
    Iterator &operator++() {
        node = node->next;
        return *this;
    }
    // переход к предыдущему элементу (постфиксный)
    Iterator &operator--() {
        node = node->prev;
        return *this;
    }
    // проверка итераторов на равенство
    bool operator==(const Iterator &other) {
        return node == other.node;
    }
    // ... на неравенство
    bool operator!=(const Iterator &other) {
        return node != other.node;
    }
 
};
 
// собственно, шаблон двусвязного списка
// смотрите, как мало собственно кода, если убрать комментарии
template <typename ValueType>
class List {
private:
    // базовый эелемент.
    // его поле next указывает на первый элемент списка
    // поле prev указываеты на последний элемент списка
    // если список пуст, next == prev == &base
    NodeBase base;
public:
    // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
    List() : base() {};
    // деструктор удаляет список функцией Clear
    ~List() {
        Clear();
    }
    // функция проверяет, пустой ли список
    bool Empty() {
        // список пустой, если базовый элемент указывает сам на себя
        return ((base.next == &base) && (base.prev == &base));
    }
    void Clear() {
        // пока список не пуст
        while (!Empty())
            // удаляется первый элемент
            // работу по удалению из списка сделает деструктор класса элемента
            delete base.next;
    }
    // добавление элемента в конец списка
    void PushBack(const ValueType &value) {
        // просто создается новый элемент списка,
        // всё остальное сделает конструктор класса NodeBase
        new Node<ValueType>(base.prev, &base, value);
    }
    // удаление последнего элемента
    void PopBack() {
        // удаляется элемент связного списка 
        // (в данном случае последний, но в принципе, сработает с любым)
        // работу по фактическому удалению элемента из списка выполнит деструктор
        // класса NodeBase
        delete base.prev;
    }
    // плохой стиль, лучше делать через итераторы, но эта концепция, наверно,
    // слишком сложна
    void PrintAll() {
        // перебор всех элементов в одном цикле
        for (NodeBase *node = base.next; node != &base; node = node->next)
            // для получения значения элемент списка приводится к типу Node*
            std::cout << static_cast< Node<ValueType>* >(node)->value;
    }
    // печать данных по условию
    template <class Predicate> // класс или функция, принимающие параметром
                               // ValueType и возвращающая true или false.
    void PrintIf(Predicate condition) {
        // цикл по всем элементам массива
        for (NodeBase *node = base.next; node != &base; node = node->next)
            // если условие выполняется
            if (condition(static_cast<Node<ValueType>*>(node)->value))
                // вывести значение
                std::cout << static_cast<Node<ValueType>*>(node)->value;
    }
 
    
 
    // итератор на начало связного списка
    Iterator<ValueType> Begin() {
        // началом связного списка является элемент, на который указывает
        // поле next переменной base
        return Iterator<ValueType>(base.next);
    }
    // итератор на элемент связного списка _после_ последнего
    Iterator<ValueType> End() {
        // элементом за связным списком является само поле base
        return Iterator<ValueType>(&base);
    }
    // поиск элемента в списке
    // принимает параметрами первый элемент и последний элемент, в
    // которых надо искать список
    // и функтор, принимающий значение элемента и возвращающая true или
    // false
    // возвращает итератор найденного элемента или последний параметр
    // если элемента не найдено
    template <class Predicate>
    Iterator<ValueType> Search(Iterator<ValueType> begin,
        Iterator<ValueType> end,
        Predicate condition) {
        for (; begin != end; ++begin)
            if (condition(*begin)) break;
        return begin;
    }
    
    
};
 
// класс автобуса
struct Person {
    std::string surname;
    std::string name;
    std::string otch;
    int phone;
    int date[3];
    
    //... тут наверно нужны другие поля
    Person(std::string surname_, std::string name_, std::string otch_,  int phone_, int date_[3])
        : surname(surname_), name(name_), otch(otch_), phone(phone_) {
        date[0] = date_[0];
        date[1] = date_[1];
        date[2] = date_[2];
    }  // переопределенный оператор для вывода на экран
    
    friend std::ostream& operator<<(std::ostream &stream, const Person &person) {
        return stream << 
             " Surname: " << person.surname
            << ", Name: " << person.name
            << ", Otch: " << person.otch
            << ", Phone : " << person.phone
            << ", Date: " << person.date[0]<<'.'<<person.date[1] << '.' << person.date[2] 
            << std::endl;
    }
    // класс-функтор для поиска по номеру
    struct IsPhone {
        // запоминаем параметр в классе
        IsPhone(int parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.phone == parameter;
        }
        int parameter; // параметр
    };
 
    // класс-функтор для поиска по дате рождения
    struct IsDate {
        // запоминаем параметр в классе
        IsDate(int parameter_[3]) 
        {
            for (int i = 0; i < 3; i++)
                parameter[i] = parameter_[i];
        }
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            if (person.date[0] == parameter[0] && person.date[1] == parameter[1] && person.date[2] == parameter[2])
                return true;
                else return false;
        }
        int parameter[3]; // параметр
    };
 
    // класс-функтор для поиска по водителю
    struct IsSurname {
        // запоминаем параметр в классе
        IsSurname(const std::string &parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.surname == parameter;
        }
        std::string parameter; // параметр
    };
 
    struct IsSurnamesort {
    
        // оператор-функтор для сравнения параметра
        bool operator()(Person person, Person person2) {
            if (person.surname > person2.surname)
            return true;
            else return false;
        }
        
    };
 
 
    struct IsName {
        // запоминаем параметр в классе
        IsName(const std::string &parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.name == parameter;
        }
        std::string parameter; // параметр
    };
 
};
 
 
 
template <class Predicate, class ValueType>
void Sorting(Iterator<ValueType> begin, Iterator<ValueType> end, Predicate condition) {
    
    for (Iterator<ValueType> tmp = begin; tmp != end; --tmp)
            if (condition(static_cast<Node<ValueType>*>(tmp)->value, static_cast<Node<ValueType>*>(tmp++)->value))
 {  
 
 
 
        }
    
}
 
 
 
 
int main(int argc, char *argv[]) {
    
    List<Person> a; 
        
    int n = 0;
    while (!0)
    {
        std::cout << "\n Menu \n\
1) New person \n\
2) Print notebook \n\
3) Search\n\
4) Sorting \n\
5) Delete \n\
0) Exit\n";
        std::cin >> n;
        if (n == 1) {
            std::string surname, name, otch;
            int nomer, date[3];
                        std::cout << "Surname... ";
            std::cin >> surname;
            std::cout << "Name... ";
            std::cin >> name;
            std::cout << "otch... ";
            std::cin >> otch;
            std::cout << "Nom... ";
            std::cin >> nomer;
            std::cout << "Date... ";
            for (int i=0;i<3;i++)
            std::cin >> date[i];
                    
            a.PushBack(Person(surname, name, otch, nomer, date));
        }
        if (n == 2) a.PrintAll();
        
        if (n == 3) {
            std::cout << "\nSearch\n\
            1) by Surname\n\
            2) by Name\n\
            3) by Phone\n\
            4) by birthday\n\
            0) Exit\n";
            int n2;
            std::cin >> n2;
            if (n2 == 1)
            {   std::string req;
                std::cin >> req;
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsSurname(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            if (n2 == 2)
            {   std::string req;
            std::cin >> req;
            Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsName(req));
            if (b != a.End())
                std::cout << *b;
            }
            
            if (n2 == 3)
            {   int req;
                std::cin >> req;
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsPhone(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            if (n2 == 4)
            {   int req[3];
            std::cout << "Date... ";
            for (int i = 0; i<3; i++)
                std::cin >> req[i];
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsDate(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            
        }
            
        if (n == 4) {
            Sorting(a.Begin(), a.End(), Person::IsSurnamesort());
 
        }
    
    }
    system("pause");
    return 0;
}
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.06.2017, 16:53 6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
template <typename T, size_t N, typename Compare>
void BubbleSort(T (&arr)[N], Compare comp)
{
    for (size_t i = 0; i < N - 1; i++)
        for (size_t j = i + 1; j < N; j++)
            if (comp(arr[j], arr[i]))
                std::swap(arr[i], arr[j]);
}
 
int main()
{
    int arr[] = {3, 1, 5, 4, 2};
    BubbleSort(arr, [](const int x, const int y) { return x < y; });
    for (const auto x : arr)
        std::cout << x << " ";
}
Добавлено через 1 минуту
Степан174174, так я вас не понял. Если вам нужно сортировать элементы вашего двунаправленного списка - напишите метод, который будет этим заниматься. Учитывая, что вы используете шаблон класса, метод будет итак работать с производными данными.
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
05.06.2017, 17:10  [ТС] 7
MrGluck Да я хочу чтобы двунаправленный список "list" сортировался по разным полям структуры "Person".
Для этого нужно сделать метод сортировки внутри класса "list" ?
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.06.2017, 17:18 8
Лучший ответ Сообщение было отмечено Степан174174 как решение

Решение

Цитата Сообщение от Степан174174 Посмотреть сообщение
Для этого нужно сделать метод сортировки внутри класса "list" ?
Да. Но абстрагироваться от типа. Вызов компаратора сделайте как в моём примере.
1
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
06.06.2017, 20:06  [ТС] 9
MrGluck, Спасибо большое. Всё получилось
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.06.2017, 20:06
Помогаю со студенческими работами здесь

Создание dll-файла с шаблонной функцией
Здравствуйте! Требуется создать .dll файл, который будет хранить в себе шаблонную функцию Вот код...

Создание шаблонной страницы в один клик
народ, php знаю лишь поверхносно /*читаю со словарем*/, подскажите мональ написать такую страничку...

Создание массива шаблонной структуры в шаблонном классе
Столкнулся с проблемой. Имеется шаблонная структура с двумя полями и шаблонный класс. В классе...

ГСЧ в шаблонной функции
Всем здрасти. Реализую шаблонную функцию, для заполнения массива случайными числами, в которой...

Объявление шаблонной функции
Здравствуйте, встретил в учебнике это: template &lt;typename Type, int size&gt; Type min( Type...

Вызов шаблонной функции
Что я делаю не так? есть функция: template &lt;class T&gt; T rFF(string input_file) { string tmp;...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru