как push_back реализован в векторе STL?

Благодаря некоторым комментариям я полностью исправляю очень неправильный исходный ответ.

Согласно спецификации STL , ваш ответ был правильным. Вектор реализован как массив с динамически изменяемым размером:

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

Но в отличие от обычных массивов, хранение в векторах обрабатывается автоматически, что позволяет расширять и сжимать его по мере необходимости.

Примерно так:

void push_back(T const& param)
{
  vector temp(rbegin(), rend());
  temp.push_front(param);
  *this = vector(temp.rbegin(), temp.rend());
}

STL вектор имеет размер (текущее количество хранимых элементов) и емкость (текущее выделенное пространство для хранения).

• Если size < capacity, то push_back просто помещает новый элемент в конец и увеличивает size на 1.
• Если size == capacity до push_back, выделяется новый, больший массив (обычно в два раза больший, но это зависит от реализации, afaik), все текущие данные копируются (включая новый элемент), а старое выделенное пространство освобождается. При неудачном распределении может возникнуть исключение.

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

Это, конечно, по своей сути определяется реализацией. Если предположить, что речь идет о том, как кто-то будет реализовывать динамический массив, то в общем случае это будет выглядеть примерно так:

1. push_back проверяет capacity() и убеждается, что он по крайней мере на единицу больше, чем size().
2. Если для нового элемента нет емкости, вектор перераспределяет все свое базовое хранилище, копируя содержимое старого хранилища в новое. Старое хранилище деаллоцируется.
3. Новый элемент копируется в конец динамического массива.

В некоторых реализациях STL некоторые из копий будут исключены за счет использования свопов (например, для контейнеров контейнеров), но в основном это работает именно так.

vector не использует связанный список. Он использует непрерывную память.

Если зарезервированного места недостаточно, push_back выделяет новый кусок памяти вдвое больший, чем исходный vector. Благодаря этому амортизированное время выполнения становится O(1).

template< typename T >
void std::vector<T>::push_back(const T& obj)
{
    this->insert(this->end(),obj);
}

Возможно, они искали, что push_back делает копию помещаемого объекта в вектор (используя свой конструктор копии).

Что касается изменения размера: в стандарте сказано, что a.push_back (x) эквивалентно a.insert (a.end (), x) . Определение insert , в частности, гласит: «Вызывает перераспределение, если новый размер больше, чем старый».

Стандарт говорит , что функции должны делать. Но то, как они реализуются, в большинстве случаев зависит от конкретной реализации.

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

Помимо обычного изменения размера по мере необходимости для сохранения семантики O (1) в среднем, некоторые вещи, которые следует учитывать, включают, но не ограничиваются:

• Безопасность при исключениях : Обеспечивает ли реализация гарантию того, что состояние вектора не будет изменено, если при добавлении нового элемента возникает исключение (например, семантика отката)? Например, исключение может быть вызвано во время выделения, копирования, вставки и т. Д.
• Правильное использование распределителя : правильно ли реализация использует распределитель вектора вместо обычного старого ] новый распределитель на основе (оба могут быть, а могут и не быть одинаковыми)? В идеале это будет прозрачно обрабатываться кодом изменения размера вектора , однако реализации, безусловно, могут отличаться.