Сортировка шаблонного дека

@_Beginner_ · Регистрация: 20.09.2019

Студворк — интернет-сервис помощи студентам

Добрый вечер. Начал изучать шаблонные типы данных, поэтому немного трудно ориентироваться в них. Нужно сделать сортировку шаблона класса дек, но понятия не имею как это сделать. Был бы благодарен, если бы кто-то наглядно показал как.
Код:

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
#ifndef  DEQUE_H
#define DEQUE_H
 
#include <iostream>
#include "abiturient.h"
 
using namespace std;
 
template <class T> struct Node
{
    T Data;
    Node<T>* Next;
    Node<T>* Prev;
    Node(const T &data)
    {
        this->Data = data;
        Next = nullptr;
        Prev = nullptr;
    }
};
 
template <class T> 
class Deque
{
    Node<T>* head;
public:
    int size;
    Deque();
    Deque(const Deque&);
    ~Deque();
    void push_front(const T&);
    T pop_front();
    void push_back(const T&);
    T pop_back();
    const T peek();
    const bool isEmpty();
    Deque<T>& operator= (const Deque&);
    template <class U>
    friend ostream& operator<< (ostream& os, const Deque<U>& obj);
    template <class T>
    friend class Iterator;
};
 
template <class T>
Deque<T>::Deque() {
    head = NULL;
    size = 0;
}
// Конструктор копирования
template <class T>
Deque<T>::Deque(const Deque& obj)
{
    if (!obj.head)
    {
        head = new Node<T>(NULL);
    }
    head = new Node<T>(obj.head->Data);
    Node<T>* temp = obj.head->Next;
    Node<T>* pnew = 0;
    Node<T>* pold = head;
    while (temp)
    {
        pnew = new Node<T>(temp->Data);
        pnew->Prev = pold;
        pold->Next = pnew;
        pold = pnew;
        temp = temp->Next;
    }
}
template <class T>
// Деструктор
Deque<T>::~Deque()
{
    while (!isEmpty())
        pop_front();
}
 
 
template <class T>
class Iterator
{
    Deque<T>* D;
    Node<T>* current;
public:
    // Конструктор преобразования
    Iterator(Deque<T>& obj)
    {
        D = &obj;
        current = obj.head;
    }
    // Возвращает текущий объект дека без его удаления
    int peek() {
        return current->Data;
    }
    // Переходит к следующему объекту дека
    void next() {
        current = current->Next;
    }
    // Переходит к предыдущему объекту дека
    void prev() {
        current = current->Prev;
    }
    // Переходит в начало дека
    void reset() {
        current = D->head;
    }
    // Проверяет существует ли элемент
    const bool isEmptyElement() {
        if (!current)
            return true;
        else
            return false;
    }
    // Доступ к элементу по адресу
    void set(Node<T>* p = 0) {
        current = p;
    }
};
 
template <class T>
void Deque<T>::push_front(const T& data)
{
    size++;
    if (head != NULL)
    {
        Node<T>* temp = new Node<T>(data);
        temp->Next = head;
        head->Prev = temp;
        head = temp;
    }
    else
    {
        head = new Node<T>(data);
    }
}
// Удаляет и возвращает объект, находящийся в начале дека
template <class T>
T Deque<T>::pop_front()
{
    if (head)
    {
        T temp = head->Data;
        Node<T>* p = head;
        head = p->Next;
        delete[] p;
        size--;
        return temp;
    }
    else
        return NULL;
}
// Вставляет объект как нижний элемент дека
template <class T>
void Deque<T>::push_back(const T& data)
{
    size++;
    if (head != NULL)
    {
        Node<T>* tail = new Node<T>(NULL);
        for (Node<T>* i = head; i != NULL; i = i->Next) {
            if (i->Next == NULL)
                tail = i;
        }
        Node<T>* temp = new Node<T>(data);
        tail->Next = temp;
        temp->Prev = tail;
        tail = temp;
    }
    else
    {
        head = new Node<T>(data);
    }
}
// Удаляет и возвращает объект, находящийся в конце дека
template <class T>
T Deque<T>::pop_back()
{
    if (head)
    {
        Node<T>* tail = new Node<T>(NULL);
        for (Node<T>* i = head; i != NULL; i = i->Next) {
            if (i->Next == NULL)
                tail = i;
        }
        T temp = tail->Data;
        Node<T>* p = tail;
        tail = p->Prev;
        tail->Next = NULL;
        size--;
        return temp;
    }
    else
        return NULL;
}
// Возвращает объект в верхней части дека без его удаления
template <class T>
const T Deque<T>::peek()
{
    if (head)
        return head->Data;
    else
        return 0;
}
// Проверяет пуст ли дек
template <class T>
const bool Deque<T>::isEmpty() {
    return size == 0;
}
// Перегрузка оператора присваивания
template <class T>
Deque<T>& Deque<T>::operator= (const Deque& obj)
{
    if (this == &obj)
        return *this;
    if (!obj.head)
        return *this;
    head = new Node<T>(obj.head->Data);
    Node<T>* temp = obj.head->Next;
    Node<T>* pnew = 0;
    Node<T>* pold = head;
    while (temp)
    {
        pnew = new Node<T>(temp->Data);
        pnew->Prev = pold;
        pold->Next = pnew;
        pold = pnew;
        temp = temp->Next;
    }
    return *this;
}
// Перегрузка потокового оператора вывода
template <class U>
ostream& operator<<(ostream& os, const Deque<U>& obj)
{
    for (Node<U>* i = obj.head; i != NULL; i = i->Next)
        os << i->Data << " " << endl;
    return os;
}
#endif

@oleg-m1973 · 07.04.2020, 21:00

Сообщение от _Beginner_

Сделал так, но я не понимаю как оно сортирует, если я записываю через конструктор с параметрами три разные записи, а оно их также(в том же порядке) и выводит(извиняюсь за глупые вопросы)

Потому что у тебя указатели сравниваются

@_Beginner_ · 07.04.2020, 21:07 **[ТС]**

Сообщение от oleg-m1973

Потому что у тебя указатели сравниваются

А как сделать для полей? И если указатели сравниваются, то по какому принципу выводится?

И я ещё сделал так:

C++
1
2
3
4
5
6
7
8
9
10
11
Deque <Abiturient*> abiturient;
 
    Abiturient* abit = new Abiturient(5, "dsf", "sdf", 2.5, 5, 1, 2);
    Abiturient* abit1 = new Abiturient(198, "dsf", "sdf", 2.5, 5, 1, 2);
    Abiturient* abit2 = new Abiturient(197, "zsf", "zdf", 2.3, 4, 0, 1);
    Abiturient* abit3 = new Abiturient(198, "dsf", "sdf", 2.5, 5, 1, 3);
    abiturient.push_front(abit);
    abiturient.push_back(abit1);
    abiturient.push_front(abit2);
    abiturient.push_front(abit3);
    abiturient.sort();

И выводится только одна запись и даже не возвращает код(просто зависает в консоли)

@oleg-m1973 · 07.04.2020, 21:15

Сообщение от _Beginner_

И выводится только одна запись и даже не возвращает код(просто зависает в консоли)

Вот это сделал?

Сообщение от oleg-m1973

C++Выделить код
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T>
void Deque<T>::insert_after(Node<T>* pos, Node<T>* node)
{
if (pos == nullptr)
{
node->Prev = nullptr;
node->Next = head;
if (head)
head->Prev = node;
head = node;
}
else
{
node->Prev = pos;
node->Next = pos->Next;
if (node->Next)
node->Next->Prev = pos->Next = node;
}
++size;
}

Добавлено через 2 минуты

Сообщение от _Beginner_

А как сделать для полей? И если указатели сравниваются, то по какому принципу выводится?

Здесь придётся прокидывать предикат сравнения в upper_bound и sort

@_Beginner_ · 07.04.2020, 21:16 **[ТС]**

Сообщение от oleg-m1973

Вот это сделал?

Нет, до это было:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
void Deque<T>::insert_after(Node<T>* pos, Node<T>* node)
{
        if (pos == nullptr)
        {
            node->Prev = nullptr;
            node->Next = head;
            head = node;
        }
        else
        {
            node->Prev = pos;
            node->Next = pos->Next;
            node->Next->Prev = pos->Next = node;
        }
        ++size;
}

Но если поменять на то, что Вы кинули, то тоже самое, хотя с тремя записями работает

Добавлено через 1 минуту

Сообщение от oleg-m1973

Здесь придётся прокидывать предикат сравнения в upper_bound и sor

А как это сделать? А то об этом первый раз слышу

@oleg-m1973 · 07.04.2020, 21:18

Сообщение от _Beginner_

Но если поменять на то, что Вы кинули, то тоже самое, хотя с тремя записями работает

То же самое что, падает?

Добавлено через 1 минуту

Сообщение от _Beginner_

А как это сделать? А то об этом первый раз слышу

По аналогии с https://en.cppreference.com/w/... pper_bound

@_Beginner_ · 07.04.2020, 21:19 **[ТС]**

Сообщение от oleg-m1973

То же самое что, падает?

Когда вот так реализовано:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
void Deque<T>::insert_after(Node<T>* pos, Node<T>* node)
{
    if (pos == nullptr)
    {
        node->Prev = nullptr;
        node->Next = head;
        if (head)
            head->Prev = node;
        head = node;
    }
    else
    {
        node->Prev = pos;
        node->Next = pos->Next;
        if (node->Next)
            node->Next->Prev = pos->Next = node;
    }
    ++size;
}

То ведёт себя очень странно: то одну запись выведет и всё, то две, то три, то все и вернёт 0, хотя в отладчике тоже всё нормально(ну, в отладчике ошибку не возвращает, но выводит также)

@oleg-m1973 · 07.04.2020, 21:22

Сообщение от _Beginner_

То ведёт себя очень странно: то одну запись выведет и всё, то две, то все и вернёт 0, хотя в отладчике тоже всё нормально.

C++
1
2
3
4
5
6
7
8
9
    else
    {
        node->Prev = pos;
        node->Next = pos->Next;
      pos->Next = node;
  if (node->Next)
            node->Next->Prev = node;
 
    }

@_Beginner_ · 07.04.2020, 21:56 **[ТС]**

Сообщение от oleg-m1973

По аналогии с https://en.cppreference.com/w/... pper_bound

Не совсем могу понять как связать это с моим классом Abiturient, не могли бы Вы наглядно показать? Просто первый раз с этим имею дело

Добавлено через 1 минуту

Сообщение от oleg-m1973

else
{
node->Prev = pos;
node->Next = pos->Next;
pos->Next = node;
if (node->Next)
node->Next->Prev = node;
}

Теперь всё корректно выводит, осталось только с сортировкой по полям разобраться

Добавлено через 32 минуты

Сообщение от oleg-m1973

Потому что у тебя указатели сравниваются

А по какой логике сравниваются указатели? Т.е почему именно так выводятся элементы?

@oleg-m1973 · 08.04.2020, 09:57

Сообщение от _Beginner_

по какой логике сравниваются указатели? Т.е почему именно так выводятся элементы?

Указатель - это адрес, 64-битное целое. Так и сравниваются

Добавлено через 11 минут

Сообщение от _Beginner_

Теперь всё корректно выводит, осталось только с сортировкой по полям разобраться

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
template <class T> 
class Deque
{
    Node<T>* head;
public:
    int size;
    Deque();
    Deque(const Deque&);
    ~Deque();
    void push_front(const T&);
    T pop_front();
    void push_back(const T&);
    T pop_back();
    const T peek();
    const bool isEmpty();
    Deque<T>& operator= (const Deque&);
    template <class U>
    friend ostream& operator<< (ostream& os, const Deque<U>& obj);
    void insert_after(Node<T>* pos, Node<T>* node);
    void sort();
    template <typename > friend class Iterator;
 
 
    template <typename TCmpFunc>
    Node<T>* upper_bound(const T &data, TCmpFunc &&is_less)
    {
        if (head == nullptr)
            return nullptr;
 
        if (is_less(data, head->Data))
            return nullptr;
 
        auto p = head;
        while (p->Next && is_less(p->Next->Data, data))
            p = p->Next;
 
        return p;
    }
 
    template <typename TCmpFunc>
    void sort(TCmpFunc &&is_less)
    {
        Node<T>* head2 = this->head;
        this->head = nullptr;
        this->size = 0;
        while (head2)
        {
            Node<T>* node = head2;
            head2 = head2->Next;
            Node<T>* pos = this->upper_bound(node->Data, is_less);
            this->insert_after(pos, node);
        }
    }
 
};

Добавлено через 15 секунд

C++
1
2
3
4
    abiturient.sort([](Abiturient *a1, Abiturient *a2)
    {
        return a1->getFio() < a2->getFio();
    });

Добавлено через 17 секунд

C++
1
2
3
4
    abiturient.sort([](Abiturient *a1, Abiturient *a2)
    {
        return a1->getFio() < a2->getFio();
    });

@_Beginner_ · 08.04.2020, 10:54 **[ТС]**

Спасибо большое за ответ

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .

@_Beginner_ 0 / 0 / 0 Регистрация: 20.09.2019 Сообщений: 86
	08.04.2020, 10:54 [ТС]
	Спасибо большое за ответ 0

Сортировка шаблонного дека

Решение