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

@_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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .

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

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

Решение