Как реализованы итераторы с произвольным доступом для несмежных контейнеров (таких как std :: deque)?
Я понимаю, как итераторы произвольного доступа работают для смежных контейнеров, таких как std::vector: итератор просто поддерживает указатель на текущий элемент и любые добавления / вычитания применяются к указателю.
Однако я озадачен тем, как подобная функциональность может быть реализована для несмежного контейнера. Моя первая догадка о том, как std::deque:iterator работает, заключается в том, что он поддерживает указатель на некоторую таблицу групп смежной памяти, которую он содержит, но я не уверен.
Как бы типичная стандартная библиотека реализовала это?
Решение
Вы можете удовлетворить требования std::deque с std::vector<std::unique_ptr<std::array<T,N>>> примерно. плюс знак низкой / высокой воды, указывающий, где находятся первые / последние элементы. (для реализации, определенной N, которая может варьироваться в зависимости от Tи std::arrayS на самом деле блоки правильно выровненной неинициализированной памяти, а не std::arrayс, но вы поняли).
Используйте обычный экспоненциальный рост, но как спереди, так и сзади.
Lookup просто делает (index+first)/N а также %N найти блок и подэлемент.
Это дороже, чем std::vector поиск, но O (1).
Другие решения
Итератор deque может быть реализован путем сохранения как указателя на указанное значение, так и двойного указателя на непрерывный блок памяти, в котором находится это значение. Двойной указатель указывает на непрерывный массив указателей на блоки, управляемые deque.
class deque_iterator
{
T* value;
T** block;
…
}
Потому что оба value а также block указав в непрерывную память, вы можете реализовать такие операции, как нахождение расстояния между итераторами за постоянное время (пример адаптирован из libc ++).
difference_type operator-(deque_iterator const& x, deque_iterator const& y)
{
return (x.block - y.block) * block_size
+ (x.value - *x.block)
- (y.value - *y.block);
}
Обратите внимание, что в то время как value не будут аннулированы такими операциями, как push_front а также push_back, block может быть, поэтому deque_iterator признан недействительным такими операциями.