Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
 Аватар для spoilsport
1 / 1 / 0
Регистрация: 17.08.2020
Сообщений: 19

Дек (deque) - проверка знаний

03.08.2021, 13:42. Показов 4781. Ответов 27

Студворк — интернет-сервис помощи студентам
Добрый день/вечер/ночь.

Захотел воспользоваться знаниями опытных программистов этого форума и получить критику по ниже представленному "коду"

Очень интересны абсолютно любые замечания, касающиеся стиля (если он там есть), работой с памятью и изобретенных велосипедов. Понимаю, что снизу представлен слишком скудноватый на строки код, чтобы по нему делать какие-то выводы, но уверен, что даже в нем находятся ошибки, которых я не замечаю ввиду своей неопытности.

Итак, ниже я попытался написать дек при помощи динамического массива. Акцентирую внимание, что просматривал как работает стандартная библиотека <deque>, чтобы не отходить от её функционала. И немного глупо (по-моему мнению) получились методы begin() И end(), так как для очереди может быть выделена память из кучи, но заполнена только до половины, однако метод end() вернет значение на последний "мусорный" элемент очереди. Посмотрел и в <deque> работает это точно также, однако возможно чего то не заметил или не понял.

Здесь ссылка на GitHub, если понадобится: https://github.com/spo1lsp0rt/deque_darr

Ниже также находится вывод в консоль.

Заранее благодарю за потраченное вами время
Код:
Кликните здесь для просмотра всего текста

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
/*
 Ниже представлен программный код реализации дека на базе динамического массива.
 Удалось реализовать методы:
 assign, front, back, size, empty, begin, end, insert(pos,val),
 push_front, push_back, pop_front, pop_back, clear
*/
#include <iostream>
 
template <typename T>
class deque
{
private:
    T *a;
    unsigned int d_size;
 
public:
    deque(const unsigned int& _size, const T& val) {
        a = new T[_size];
        for (unsigned int i = 0; i < _size; i++) {
            a[i] = val;
        }
        d_size = _size;
    }
    deque(const unsigned int& _size) {
        a = new T[_size];
        for (unsigned int i = 0; i < _size; i++) {
            a[i] = NULL;
        }
        d_size = _size;
    }
 
    void assign(const unsigned int& _size, const T& val) {
        if (d_size != 0) delete a;
        a = new T[_size];
        for (unsigned int i = 0; i < _size; i++) {
            a[i] = val;
        }
        d_size = _size;
    }
 
    T& front() {
        return a[0];
    }
 
    T& back() {
        return a[d_size - 1];
    }
 
    unsigned int size() {
        return d_size;
    }
 
    bool empty() {
        return d_size == 0;
    }
 
    unsigned int begin() const {
        return 0;
    }
 
    unsigned int end() const {
        return d_size - 1;
    }
 
    void insert(const unsigned int& pos, const T& val) {
        if (d_size == 0) {
            d_size++;
            a = new T[d_size];
            a[0] = val;
        }
        else {
            d_size++;
            T* temp = new T[d_size];
            for (unsigned int i = 0; i < pos; i++) {
                temp[i] = a[i];
            }
            temp[pos] = val;
            for (unsigned int i = pos; i < d_size - 1; i++) {
                temp[i + 1] = a[i];
            }
            delete a;
            a = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                a[i] = temp[i];
            }
            delete temp;
        }
    }
 
    void push_front(const T& val) {
        if (d_size == 0) {
            d_size++;
            a = new T[d_size];
            a[0] = val;
        }
        else {
            d_size++;
            T* temp = new T[d_size];
            temp[0] = val;
            for (unsigned int i = 0; i < d_size - 1; i++) {
                temp[i + 1] = a[i];
            }
            delete a;
            a = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                a[i] = temp[i];
            }
            delete temp;
        }
    }
 
    void push_back(const T& val) {
        if (d_size == 0) {
            d_size++;
            a = new T[d_size];
            a[0] = val;
        }
        else {
            d_size++;
            T* temp = new T[d_size];
            for (unsigned int i = 0; i < d_size - 1; i++) {
                temp[i] = a[i];
            }
            delete a;
            a = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                a[i] = temp[i];
            }
            delete temp;
            a[d_size - 1] = val;
        }
    }
 
    void pop_front() {
        if (d_size == 0) {
            throw std::out_of_range("err: out of range");
        }
        else {
            d_size--;
            T* temp = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                temp[i] = a[i + 1];
            }
            delete a;
            a = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                a[i] = temp[i];
            }
            delete temp;
        }
    }
 
    void pop_back() {
        if (d_size == 0) {
            throw std::out_of_range("err: out of range");
        }
        else {
            d_size--;
            T* temp = new T[d_size];
            for (int i = d_size - 1; i >= 0; i--) {
                temp[i] = a[i];
            }
            delete a;
            a = new T[d_size];
            for (unsigned int i = 0; i < d_size; i++) {
                a[i] = temp[i];
            }
            delete temp;
        }
    }
 
    void clear() {
        delete a;
        d_size = 0;
    }
 
    T& operator[](const unsigned int& pos) {
        if (pos >= d_size) {
            throw std::out_of_range("err: out of range");
        }
        else return a[pos];
    }
};
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "ru");
    deque<int> dq(3, 1);
    //изменили первое значение дека вызовом front()
    dq.front() = 777;
    //изменили промежуточное значение дека вызовом оператора []
    dq[1] = 888;
    //изменили последнее значение дека вызовом back()
    dq.back() = 999;
    cout << "Первое значение дека: " << dq.front() << endl;
    cout << "Промежуточное значение дека: " << dq[1] << endl;
    cout << "Последнее значение дека: " << dq.back() << endl;
 
    cout << "Пуст ли дек? Ответ: " << dq.empty() << endl;
    dq.clear();
    cout << "Очистили дек. Пуст ли дек? Ответ: " << dq.empty() << endl;
 
    dq.assign(5, 9);
    cout << "Воспользовались assign(). \nВывод дека:  ";
    for (size_t i = dq.begin(); i <= dq.end(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl << "Размер дека: " << dq.size() << endl;
    dq.insert(dq.begin(), 0);
    cout << endl << "Воспользовались insert() для begin(). \nВывод дека:  ";
    for (size_t i = dq.begin(); i <= dq.end(); i++) {
        cout << dq[i] << " ";
    }
    dq.pop_back();
    dq.pop_front();
    cout << endl << "Воспользовались pop_back() и pop_front(). \nВывод дека:  ";
    for (size_t i = dq.begin(); i <= dq.end(); i++) {
        cout << dq[i] << " ";
    }
    dq.push_back(-5);
    dq.push_front(-5);
    cout << endl << "Воспользовались push_back() и push_front(). \nВывод дека:  ";
    for (size_t i = dq.begin(); i <= dq.end(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl;
    return 0;
}

Вывод в консоли:
Кликните здесь для просмотра всего текста

Первое значение дека: 777
Промежуточное значение дека: 888
Последнее значение дека: 999
Пуст ли дек? Ответ: 0
Очистили дек. Пуст ли дек? Ответ: 1
Воспользовались assign().
Вывод дека: 9 9 9 9 9
Размер дека: 5

Воспользовались insert() для begin().
Вывод дека: 0 9 9 9 9 9
Воспользовались pop_back() и pop_front().
Вывод дека: 9 9 9 9
Воспользовались push_back() и push_front().
Вывод дека: -5 9 9 9 9 -5
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.08.2021, 13:42
Ответы с готовыми решениями:

Deque (Дек) на двусвязном списке
Стояла задача реализовать дек с указателем только на начало очереди. Мой код вроде как рабочий, но хотелось бы поинтересоваться с более...

Создание ДЕК (как стэк только о двух концах) без <deque>
здравствуйте! написал класс Deque, создал методы push_back(), push_front(), pop_back(), pop_front()... Все работает нормально, кроме...

Есть ли в Qt контейнер типа "Дек" (deque) или надо свой написать?
Пока не нашёл. Если нет, то от кого лучше унаследоваться, чтобы реализовать?

27
Эксперт С++
 Аватар для hoggy
8973 / 4319 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
04.08.2021, 17:41
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от DrOffset Посмотреть сообщение
"Кешировать" значение, полученное по ссылке, внутри функции компилятор не станет.
она ж не волатильная.
почему ж не станет то?
0
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
04.08.2021, 17:51
hoggy, потому что в общем случае компилятор будет не в состоянии доказать, что объект, переданный по ссылке, не изменяется в процессе выполнения функции.
Вот пример: https://godbolt.org/z/vz18rbWo7
1
Эксперт С++
 Аватар для hoggy
8973 / 4319 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
04.08.2021, 18:34
Цитата Сообщение от DrOffset Посмотреть сообщение
потому что в общем случае компилятор будет не в состоянии доказать, что объект, переданный по ссылке, не изменяется в процессе выполнения функции.
почему это не может?
он же видит, что внутри функции ссылка не изменяется.

а то, что она может измениться снаружи функции,
например, в параллельном потоке,
это компилятор уже не обязан учитывать.

разве нет?
0
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
04.08.2021, 18:45
hoggy, вообще речь не про потоки.
Посмотри ассемблерный код, который я скинул. Там и в цикле и вне цикла происходит каждый раз косвенное чтение.
А все почему? Потому что компилятор не может видеть побочные эффекты foo и boo. Может они внутри себя меняют глобальную переменную, ссылку на которую мы и передали?
Т.е. тут речь о трудности в общем случае предсказать именно синхронное изменение объекта при наличии хоть малейшей возможности присутствия побочных эффектов. Т.к. в реальном мире достаточно редко встречаются функции, которые не делают внутри себя что-то имеющее побочные эффекты, то почти всегда такое чтение по ссылке будет сопровождаться накладными расходами на косвенный доступ.
1
Эксперт С++
 Аватар для hoggy
8973 / 4319 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
04.08.2021, 19:07
Цитата Сообщение от DrOffset Посмотреть сообщение
А все почему? Потому что компилятор не может видеть побочные эффекты foo и boo. Может они внутри себя меняют глобальную переменную, ссылку на которую мы и передали?
помниццо, как компилятор студии кэшировал значение глобальной переменной,
совершенно не заморачиваясь тем, что кто-то может её поменять.
а мне, соответственно, приходилось делать её волатильной.
0
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
04.08.2021, 19:14
Цитата Сообщение от hoggy Посмотреть сообщение
помниццо, как компилятор студии кэшировал значение глобальной переменной,
совершенно не заморачиваясь тем, что кто-то может её поменять.
Может она была статическая (в смысле с внутренним связыванием)?
0
фрилансер
 Аватар для Алексей1153
6506 / 5756 / 1134
Регистрация: 11.10.2019
Сообщений: 15,404
04.08.2021, 19:23
Цитата Сообщение от hoggy Посмотреть сообщение
компилятор студии кэшировал значение глобальной переменной,
совершенно не заморачиваясь тем, что кто-то может её поменять
давно использую глобальные переменные в студии (VS6, VS2008, VS2019) - ни разу такого не было. Клиенты бы заметили
0
Эксперт С++
 Аватар для hoggy
8973 / 4319 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
04.08.2021, 19:26
Цитата Сообщение от DrOffset Посмотреть сообщение
Может она была статическая (в смысле с внутренним связыванием)?
я думаю сейчас нет смысла гадать,
чего там было не так.

сейчас я вижу ситуацию так:
хороший компилятор должен предполагать худший сценарий.
и если есть вероятность, что оптимизация может что-то нарушить,
то хороший компилятор не должен её осуществлять.
именно по этой причине хороший компилятор и не оптимизирует ссылку.

однако в реальном мире компиляторы не всегда ведут себя хорошо.
поэтому, я допускаю мысль,
что компилятор запросто может соптимизировать и ссылку,
и глобальную переменную,
и все что угодно, что не было помеченно как volatile
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.08.2021, 19:26

Хранение в контейнере deque целых чисел и проверка основных операций
Написала код: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;deque&gt; using namespace std; void show (const char *str,...

Проверка знаний по C++
Оцените правильность моих ответов пожалуйста. Всего было 100 вопросов. Я оставил только те, в которых сомневаюсь. Тест дали в университете....

Программа - проверка знаний
Изучаю Qt Creator и нужно написать программу тестирование, которая будет состоять из нескольких тем тестов, варианты в вопросах будут...

Проверка знаний таблицы умножения
Доброго времени суток! есть задача: Написать программу, которая проверяет пользователя на знание таблицы умножения. Программа выводит...

Проверка знаний таблицы умножения
Пользователь сам вводит два целых однозначных числа. Программа задаёт вопрос: результат умножения первого числа на второе. Пользователь...


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

Или воспользуйтесь поиском по форуму:
28
Ответ Создать тему
Новые блоги и статьи
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP
and_y87 12.10.2026
10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .
День 5 из 28: Codex подсказывает следующий запрос
and_y87 12.10.2026
9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
Adler 06.10.2026
Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке
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. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru