Что происходит, когда мы используем векторную стирание или вставку

Question

Перемещает ли все элементы с правой стороны вектора (до 1 позиции слева, если стирает и переместится в 1 позицию справа, если вставить) или это как связанный список (он создает новый адрес и новый адрес. Также, когда я инициализирую вектор со строкой, как он позаботится о памяти. Если он хранит его в последовательности, что произойдет, когда мы продолжим делать push_back, когда он достигнет максимума выделение памяти.

Answer 1

A std::vector Гарантируется (стандартом C++) для хранения элементов в смежной области памяти. Это означает, что нет, это не похоже на связанный список, а скорее как динамически выделенный массив. push_back после того, как вектор достигнет максимальная емкость происходит перераспределение, и элементы копируются в новый буфер. То же самое происходит, когда вы используете элементы вставки или стирания, вещи сдвигаются так, что эти операции в общем случае O (N), а не O (1), как это имеет место для связанных списков.

Похоже, что std::vector хуже, чем std::list. Это не так, поскольку, как и во многих приложениях, операции чтения являются доминирующими, для которых std::vector намного быстрее, чем std::list из-за локальности кэша и произвольного доступа O (1) из-за того, что элементы хранятся смежно. Также push_back - это O (1), за исключением случаев, когда вектор выполняет перераспределение (технически push_pack амортизировал сложность O (1)).