Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Книги по си++ https://www.cyberforum.ru/ cpp-beginners/ thread1258099.html
Здравствуйте! Не подскажите какие книги почитать, если уже освоил основы си++. Для более углубленного изучения языка.Заранее спасибо!
C++ Построить таблицу приближенных значений функций
Помогите доделать задачку. Построить таблицу приближенных значений функции f(x)на отрезке с шагом h. Результаты представить в виде таблицы.Значения функции F(x) вычислять, используя ...
Картинка, меняющая цвет C++
Здравствуйте! Мне нужно сделать так, чтобы картинка меняла цвет. То есть у меня есть круг, палочка, которые нарисованы в каком-нибудь графическом редакторе. При нажатии на кнопку, они должны начать...
C++ Преобразование таблиц Excel Необходимо преобразовать таблицы, прешедшие в Excel из одного вида в другой. При этом выполняется сортировка, подсчет суммы за год, за месяц, за день. Встречала тут сообщения про COM. Эта... https://www.cyberforum.ru/ cpp-beginners/ thread1258083.html
C++ Среднее геометрическое, в ответе всегда выдает единицу https://www.cyberforum.ru/ cpp-beginners/ thread1258081.html
Написал программу, но что бы я не ответ всегда 1. Подскажите где я ошибся. #include <iostream> #include <math.h> using namespace std; int main() {
C++ Сортировка одномерного массива по неубыванию (невозрастанию)
Ввести одномерный массив из n элементов. Отсортировать массив по неубыванию (невозростанию) методом прямого выбора.
Неправильный вывод UTF8 строки вместе с setw C++
Есть файл с UTF8 строкой. Считываем его и выводим во второй файл с выравниванием. В результате выравнивание нету. Почему так? Чем поровнять?int main() { std::ifstream ifs("file.txt"); ...
C++ Заданный список из 8 слов. Найти самое короткое слово из списка Ребята, кто сможет такое сделать ? Не имею понятие как вообще это сделать, заранее благодарю. Заданный список из 8 слов. Найти самое короткое слово из списка. Если таких слов несколько, то... https://www.cyberforum.ru/ cpp-beginners/ thread1258048.html
C++ Задача "Расшифровка" https://www.cyberforum.ru/ cpp-beginners/ thread1258047.html
Компания по защите интеллектуальной собственности решила повысить уровень защищённости своих операционных систем путём шифрования всех сообщений, передаваемых внутри её локальных сетей. Любое...
C++ Сформировать второй массив, в котором элементы записаны в обратном порядке помогите сформулировать второй массив, в котором элементы записаны в обратном порядке соответственно элементов первого массива. Вот первый массив, допишите пожалуйста код .. #include <conio.h>... https://www.cyberforum.ru/ cpp-beginners/ thread1258045.html
29 / 1 / 1
Регистрация: 30.08.2013
Сообщений: 37
0

Как работает std::deque?

17.09.2014, 22:28. Просмотров 2505. Ответов 3
Метки (Все метки)


Пытаюсь разобраться в работе std-шного дека. Веб-серфинг дал следующее:
Данные хранятся в куче небольшими блоками(массивами) в виде связанного списка.
С добавлением/удалением элементов более - менее все ясно - данные записываются в блок, когда он заканчивается, создается новый, связывается указателями с нужной стороны, и запись идет уже в него.
А вот произвольный доступ к элементу с постоянной сложностью вообще не понятен. Внутри одного блока все просто, но как быть если надо пройти дальше?
По идее, надо пройти по указателю в следующий блок, проверить есть-ли искомый элемент там, и либо вернуть его, либо рекурсивно идти дальше - а это уже линейная сложность.

В свое время реализовывал дек двумя способами - первый это что-то вроде вектора, только данные начинали писаться не сначала, а с середины, и когда с какой либо стороны упирались в конец блока, выделялся новый (больший) массив, и переписывал этот существующий дек туда, центруя данные.

Вторая реализация - это список с множественными связями. То есть каждый элемент ссылался не только на левого и правого соседа, но и (при условии их существования), на 10-й, 100-й, 1000-й и т.д до 10000000-го элемент.
При добавлении/удалении элемента приходилось переопределять эти 8 указателей, но при доступе к произвольному элементу в здоровых массивах выигрыш получался солидным (хотя сложность опять-же линейная)

Вернуться к обсуждению:
Как работает std::deque?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.09.2014, 22:28
Готовые ответы и решения:

Как устроена std::deque внутри ?
Не могу себе представить возможную внутреннюю реализацию этого контенера, чтоб она удовлетворяла...

Как инициализировать объект типа std::deque<int>?
Доброе время суток! Я видимо совсем не разбираюсь в шаблонах, так как не понимаю почему не...

std::deque
Как известно при добавлении в конец вектора элементов(и не только в конец) может возникнуть...

Разделить std::deque на заданное количество деков
Имеется дек, нужно его разделить на отдельные деки. Это задание я сделал когда знал точное...

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