Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
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
14022 / 7507 / 1777
Регистрация: 30.01.2014
Сообщений: 12,561
17.09.2014, 22:59 0

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

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

Ответ


Цитата Сообщение от Erik945 Посмотреть сообщение
А вот произвольный доступ к элементу с постоянной сложностью вообще не понятен.
23.2.3 Sequence containers
16 Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.
Table 101 — Optional sequence container operations
...
push_front, push_back, operator[]
Т.е. там не константная сложность, а амортизированная константная сложность. Это немного разные вещи.

Цитата Сообщение от Erik945 Посмотреть сообщение
По идее, надо пройти по указателю в следующий блок, проверить есть-ли искомый элемент там, и либо вернуть его, либо рекурсивно идти дальше - а это уже линейная сложность.
размер блока фиксирован, количество блоков известно, определить по индексу в какой блок прыгать не сложно. Связный список не обязателен, может быть и массив.

Добавлено через 11 минут
Erik945, В любом случае о способе организации можно рассуждать только на конкретном примере. Ну вот, например, реализация gnu.

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

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

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

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

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

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