Ребята, а std::deque реализован на базе двусвязанного списка? Иначе я не

Question

Ребята, а std::deque реализован на базе двусвязанного списка? Иначе я не

очень понимаю, как это возможно:

`push_front`, `push_back`, `emplace_front` and `emplace_back` do not invalidate any references to elements of the `deque`.

#c++ #embedded #programming #russian

0

31.05.2021

13 ответов

3 просмотра

𝙽𝚒𝚌𝚔 𝙻𝚒𝚗𝚔𝚎𝚛 Автор вопроса

magras
Обычно двухсвязный список чанков фиксированного ра...

Понял, спасибо.

0

31.05.2021

Kirill Bolshakov

std::list<std::vector>

0

31.05.2021

𝙽𝚒𝚌𝚔 𝙻𝚒𝚗𝚔𝚎𝚛 Автор вопроса

Kirill Bolshakov
std::list<std::vector>

✊👍

0

31.05.2021

magras

magras
Обычно двухсвязный список чанков фиксированного ра...

Точнее вектор чанков.

0

31.05.2021

Dmitriy [Отпуск]

magras
Обычно двухсвязный список чанков фиксированного ра...

А как быть с индексным доступом тогда? Разве там не вектор указателей на чанки?

0

31.05.2021

Dmitriy [Отпуск]

magras
Точнее вектор чанков.

Прочитал позже, чем ответил :)

0

31.05.2021

magras

Dmitriy [Отпуск]
А как быть с индексным доступом тогда? Разве там н...

Да, немного опозорился, но почти успел исправиться. =)

0

31.05.2021

Egor Suvorov

Dmitriy [Отпуск]
А как быть с индексным доступом тогда? Разве там н...

Да, вектор указателей на чанки фиксированного размера K. Так можно и быстро делать вставку в конец/начало (не надо передвигать элементы, только N/K указателей на чанки), и делать доступ по индексу (сначала нашли чанк, потом внутри чанка взяли по номеру).

0

31.05.2021

Kelbon

представь себе массив указателей на std::array, в этой схеме никогда не будет переаллоцироваться память для уже существующих элементов(кроме массива указателей), соответственно итераторы будут ломаться, а существующие ссылки на элементы - никогда

0

01.06.2021

𝙽𝚒𝚌𝚔 𝙻𝚒𝚗𝚔𝚎𝚛 Автор вопроса

Kelbon
представь себе массив указателей на std::array, в ...

Спасибо за такое образное описание, мне достаточно было термина "вектор чанков" 😉

0

01.06.2021

Kelbon

𝙽𝚒𝚌𝚔 𝙻𝚒𝚗𝚔𝚎𝚛
Спасибо за такое образное описание, мне достаточно...

а вот как раз вектор чанков сломает все ссылки и итераторы

0

01.06.2021