Почему std :: vector использует смещение?

Простой вопрос. При добавлении или удалении с передней части вектора, почему вам нужно переместить все элементы для внесения изменений? Используя смещение вместо этого, чтобы изменить индекс, указанный при индексировании в вектор, решит эту проблему. Разумеется, это может привести к (в лучшем случае) двум непрерывным блокам данных в памяти, но это кажется небольшой ценой для сокращения линейной операции до постоянного времени.Почему std :: vector использует смещение?

Вот пример, чтобы быть как можно более ясно:

['A', 'B', 'C', _, _, _, _, _] offset is 0, 4th through 8th position unused. 
push_front('M') 
['A', 'B', 'C, _, _, _, _, 'M'] offset is -1

, а затем при индексировании

operator[](size_t index) { 
    return backing_array[(index + offset) % size] 
}

я получаю это означает, что не может быть один чистый непрерывный блок данных, но переход от 1 до 2 не кажется огромной сделкой в обмен на постоянное время толчка и поп-фронт.

источник

2016-05-31 Keltek

+10

Это то, что ['std :: deque'] (http://en.cppreference.com/w/cpp/container/deque) для. –

вектор не создан для удаления элементов между ними. Вы можете это сделать, но есть лучшие контейнеры (например, связанный список). Векторы гарантируют, что элементы хранятся в непрерывной памяти – user463035818

Одна из причин заключается в том, что каждый раз, когда вы будете использовать 'std :: vector :: operator []' вам придется добавить это смещение в индекс. – 101010

я получаю это означает, что не может быть один чистый непрерывный блок данных

Нет, это конец истории прямо там. Весь смысл vector заключается в том, что он является «чистым смежным блоком данных». Это фундаментальное требование реализации.

Способность делать это основной частью всей цели vector «s:

T *ptr = &vec[0]; 
ptr+1; 
ptr == &vec[1];

Таким образом, интерфейс не может обеспечить дополнительные требования, которые препятствовали бы vector от того, прилегающий.

источник

2016-05-31 21:06:55

Вся идея вектора для одного непрерывного блока данных: Например, вы можете передать их (ну, адрес первого элемента) к API, C, вы получите хорошее расположение кэша и т.д.

стандарт обеспечивает deque для точно сценарий, в котором вы нуждаетесь: быстрый нажим/поп для передней/задней части контейнера.

источник

2016-05-31 21:08:48

Почему std :: vector использует смещение?

ответ

Смежные вопросы