В прошлом видео мы познакомились
с понятием инвалидации ссылок, увидели, что вектор подвержен
инвалидации просто потому, что он так устроен, а дек не подвержен.
Соответственно, мы поняли, что нам важно знать внутреннее устройство и дека тоже.
Хотя бы потому, что, зная внутреннее устройство дека, мы могли бы
заранее предвидеть, что он не инвалидирует ссылки при добавлении предметов.
Давайте же попробуем сами в некотором смысле придумать дек.
А именно, вот у нас есть вектор.
Какими недостатками он обладает?
Во-первых, он инвалидирует ссылки на свои элементы.
Это во-первых.
При этом реаллоцируя память и копируя данные из старой памяти в новую.
Во-вторых, он долго вставляет в начало.
Если вы хотите вставить в начало вектор, вам придется двигать все последующие
элементы, что мы уже обсуждали во втором курсе.
И из-за чего эти недостатки присутствуют?
Из-за того, что вектор гарантирует, что все его элементы хранятся подряд.
И гарантируя это, он теряет некоторые полезные свойства,
которые у него могли бы быть.
Инвалидацию ссылок он приобретает и долго вставляет в начало.
Давайте откажемся от требования хранения вообще всех элементов подряд в едином
куске памяти и попробуем получить что-то более интересное, а именно, дек.
Итак, создаем дек, кладем в него числа 1, 2 и 3.
Давайте для простоты выделим кусок памяти под три инта, положим туда 1, 2 и 3.
Пока всё хорошо.
Всё хорошо, пока мы не начинаем его изменять.
Что, если мы хотим добавить туда 4?
Мы не можем ее добавить сразу после 3,
потому что мы выделили блок памяти под три инта.
Но что мы можем сделать?
Можем выделить еще один блок памяти,
давайте там тоже для простоты будет три инта, и в первую ячейку положим 4.
И просто будем каким-то образом помнить, что после блока памяти,
в котором лежат 1, 2 и 3, идет следующий блок памяти где-то в другом месте в куче,
в котором лежит 4 и пока две пустых ячейки.
Ладно.
А что, если я добавляю элемент в начало, добавляю 0 с помощью метода push_front?
Опять же, я не могу прямо перед 1 записать этот 0,
потому что это блок памяти из трех элементов, а вокруг в куче неизвестно что.
Но я могу выделить еще один блок памяти, для простоты у него будет тоже три инта.
И в последний элемент, чтобы соблюсти некоторый разумный порядок, я положу 0.
Теперь у меня получается следующая картина.
У меня есть три блока памяти, в первом лежит только 0 в конце, во втором лежат 1,
2, и 3, и в начале третьего лежит 4.
Всё было бы неплохо,
но нам нужно уметь обращаться к элементу по его номеру.
Это очень удобное свойство дека, что можно обращаться к элементу по номеру.
Поэтому нам нужно уметь эти блоки памяти, они еще называются чанками,
как-то проиндексировать, в смысле где-то отдельно сохранить их адреса в памяти,
и прямо запомнить, что нулевой чанк лежит вон там-то,
и там лежит 0, первый чанк лежит там, и второй чанк лежит там.
Прямо сохраним вектор-указатель на эти чанки, на эти блоки памяти.
Чего же мне теперь не хватает, что же мне сохранить в самом деке?
Мне нужно сохранить сам этот вектор-указатель на чанке,
назовем его chunks прямо, нам нужно сохранить количество элементов,
это полезное знание, метод size должен быстро работать,
хорошо бы знать всегда, сколько у меня элементов в деке.
А еще нам понадобится такая интересная вещь, как сдвиг.
Сдвиг того самого нуля относительно начала его чанка.
Сдвиг нулевого элемента дека относительно начала первого блока памяти.
В данном случае 0 сдвинут относительно начала своего блока памяти на две ячейки.
Соответственно, мы в поле shift положим 2.
Теперь как же мне найти второй элемент?
Я вижу, что мне нужно элемент № 2,
прибавляю сдвиг, с учетом сдвига мне нужен четвертый элемент.
И как мне найти четвертый элемент?
Я знаю, что размер блока памяти 3, я делю 4 на 3, получаю 1,
иду в первый чанк памяти и там иду в элемент №4%3,
я беру остаток от деления 4 / 3 и получаю,
что у меня в первом блоке памяти нужен первый элемент, и вот я нахожу эту двойку.
Я смог найти двойку, но все-таки потратив на это некоторые усилия.
Но дек у меня получился.
Кажется, вот с этим вполне можно жить, и кажется,
что дек вполне себе может быть устроен именно так.
Соответственно, мы получили быструю ставку в начало и неинвалидацию ссылок
при вставке в начало или в конец.
Очень удобно.
Но что же мы потеряли при этом?
Мы теперь тяжелее получаем элемент по индексу.
Нам приходится прибавлять shift, брать остаток от деления, делить нацело.
Это сложнее, чем как в векторе просто прибавить число к указателю.
Соответственно, итерироваться по деку тоже не просто,
потому что мы должны перепрыгивать с одного чанка на другой чанк.
Наверно, итератор дека устроен сложнее, чем просто указатель,
как он устроен у вектора.
Но давайте посмотрим на то,
в каких случаях дек может быть эффективнее, чем вектор.
Или, может быть, он никогда не эффективнее, чем вектор?
Давайте рассмотрим следующий пример.
Пусть нам нужно вставить набор чисел в наш контейнер,
но при этом мы заранее не знаем, сколько у нас будет этих чисел.
Соответственно, мы не можем reserve вызвать, используя вектор.
Мы, например, читаем эти числа из какого-то сетевого соединения,
пока нам не придет сигнал о том, что хватит читать.
Соответственно, reserve вызвать не можем, ну давайте как-то промоделируем.
Давайте я заведу константу, как будто бы я не знаю, чему она равна.
SIZE = 1000000.
И теперь я вставлю миллион чисел в контейнер, как будто бы заранее не зная,
сколько их там будет, не имея возможности вызвать reserve.
Сразу буду замерять с помощью макроса LOG_DURATION.
Используя вектор, я это делаю таким образом.
Давайте я даже снаружи объявлю вектор.
Я просто сделаю серию push_back.
От 0 до SIZE вставлю i.
И то же самое сделаю для дека.
Что же будет быстрее — без
использования reserve вставить миллион элементов
в вектор или вставить миллион элементов в дек с помощью push_back?
Вот у меня дек d, и я тоже делаю в него SIZE push_back.
Давайте замерим, что же будет быстрее.
Компилируем код и видим,
что особой разницы нет.
Примерно 60 миллисекунд я вставлял миллион элементов в вектор и миллион
элементов в дек.
Почему? Потому что вектор, конечно,
память реаллоцировал, что-то копировал, с одной стороны.
А с другой стороны, дек выделял какие-то новые блоки памяти.
Кстати, в реальности они имеют размер не 3, а гораздо больше.
Но все-таки, нам нужно тратить какие-то временные ресурсы на то,
чтобы выделять очередные блоки памяти.
Ладно.
А что, если у меня не миллион элементов, а, например, пять миллионов?
Попробую вставит пять миллионов элементов в вектор и в дек.
Код почти скомпилировался.
Да, теперь, когда вставляю пять миллионов элементов,
вектор это делает за 400 миллисекунд, кстати, очень долго,
а дек за 168 миллисекунд, гораздо быстрее, более, чем в два раза быстрее.
О чем это говорит?
О том, что вы не можете заранее знать, будет ли вам полезнее, вот в данном
примере, когда не будет возможности вызвать reserve, вектор или дек.
Поэтому нужно измерять.
Зная конкретное ограничение на то, сколько у вас может быть чисел,
нужно взять и измерить, будет ли дек эффективнее, чем вектор.
И в данном случае он оказался эффективнее,
потому что он не перевыделяет память в два раза больше, чем предыдущий блок,
и не копирует данные из предыдущего блока, не тратит время на это.
С деком получилось сэкономить только в этом.
Давайте вспомним,
что по деку тяжелее итерироваться и тяжелее обращаться к элементу по индексу.
Когда это может быть нужно?
Например, при использовании каких-то алгоритмов.
Давайте я попробую отсортировать полученный вектор и дек.
Опять же, с помощью макроса LOG_DURATION я буду это замерять.
sort vector.
Вызываю функцию sort.
Наверное, довольно скучно сортировать вектор,
в котором все числа от 0 и по возрастанию до SIZE − 1.
Давайте я отсортирую в обратном порядке, например.
С помощью rbegin и rend.
Как вы помните, если я в сортировку передаю обратные итераторы,
у меня сортировка происходит в обратном порядке.
Итак, я это сделал для вектора.
И то же самое сделаю для дека.
[БЕЗ_ЗВУКА] Посмотрим,
что быстрее — отсортировать вектор или отсортировать дек?
Они имеют один и тот же размер и одни и те же данные в них.
Итак, сортируются, сортируются.
Какой кошмар.
Неужели она столько долго сортирует?
Ничего, подождем.
Видим, что вектор отсортировался за 5,5 секунд.
В то время как дек сортировался 11 секунд.
Видите, мы быстрее заполнили дек,
но сортировали мы его гораздо дольше, чем вектор, что лишний раз подтверждает то,
что дек в принципе, если мы не добавляем в него элемент,
а просто используем готовый дек, он все-таки несколько тяжелее, чем вектор.
Какие выводы из этого можно сделать?
Когда же нужно использовать вектор, а когда дек?
Вектор хорош быстрыми обращениями к элементам,
это буквально прибавить к указателю число и разыменовать.
Обращение к элементу вектора по индексу быстрое и
итерирование по вектору тоже быстрое, с одной стороны.
С другой стороны, дек хорош тем,
что можно быстро сделать серию push_back, если вы заранее не знаете размер.
Кроме того, можно быстро вставлять в начало,
при этом не инвалидируя ссылки на элементы дека.
Соответственно, когда же стоит использовать вектор, когда дек?
Мы показали вам несколько примеров,
когда гарантированно быстрее вектор или быстрее дек.
Но если у вас примеры уже чуть более сложные, вам все равно придется измерять.
Так что, пожалуйста, имейте в виду те примеры, которые мы вам показываем,
но в случае сомнений всегда лучше измерить, чем взять один какой-то
контейнер и на слово кому-то поверить, что он эффективнее, чем какой-то другой.
В следующем видео мы узнаем еще одно интересное свойство дека.
