Ответ
Нет, не всегда. Сложность операции push_back() — амортизированная константная O(1), но не чистая константная.
Механизм работы и сложность:
- O(1): Если в векторе есть свободная емкость (
size() < capacity()),push_backпросто размещает элемент в конце — это константная операция. - O(N): Если вектор заполнен (
size() == capacity()), происходит реаллокация (reallocation). Алгоритм выделяет новый блок памяти, обычно в 1.5 или 2 раза больше предыдущего, перемещает (или копирует) все существующие элементы в новый блок, а затем добавляет новый элемент. Перемещение всех N элементов имеет линейную сложность.
Пример, демонстрирующий разницу:
#include <vector>
#include <iostream>
#include <chrono>
int main() {
std::vector<int> v;
v.reserve(5); // Устанавливаем capacity = 5
// Эти 5 вызовов будут выполняться за O(1) каждый
for (int i = 0; i < 5; ++i) {
v.push_back(i); // Без реаллокаций
}
// Этот вызов вызовет реаллокацию (capacity станет, например, 10)
// Все 5 старых элементов будут перемещены, сложность O(N)
v.push_back(5);
std::cout << "Size: " << v.size() << std::endl; // 6
std::cout << "Capacity: " << v.capacity() << std::endl; // 10
return 0;
}Практический вывод: Для предсказуемой производительности, когда известно примерное количество элементов, следует использовать метод reserve(). Это позволяет избежать множественных реаллокаций и обеспечивает истинно константное время добавления в пределах зарезервированной емкости.
Ответ 18+ 🔞
А, ну это классика, блядь! Смотри, тут многие думают, что push_back() — это всегда быстро, как пуля. А на деле, ёпта, не всё так просто. Сложность у него амортизированная константная O(1), а не чистая. То есть в среднем быстро, но иногда он может так пиздануть по производительности, что мало не покажется.
Как это работает на самом деле:
- O(1) — быстро: Пока в векторе есть свободное место (
size() < capacity()),push_backпросто суёт элемент в конец — и всё, красота. Константная операция, всё летает. - O(N) — пиздец: А вот если вектор заполнен до отказа (
size() == capacity()), начинается цирк под названием реаллокация (reallocation). Алгоритм, сука, ищет новый, больший кусок памяти (обычно в 1.5 или 2 раза больше), потом начинает тупо тащить все старые элементы на новую квартиру. Это перемещение всех N элементов — операция линейная, то есть чем больше элементов, тем дольше всё это будет. Представь, ты переезжаешь, и тебе надо вручную перетащить всю свою коллекцию пивных крышек — вот это и есть реаллокация, блядь.
Смотри пример, чтобы вообще ни хуя не путать:
#include <vector>
#include <iostream>
#include <chrono>
int main() {
std::vector<int> v;
v.reserve(5); // Говорим вектору: "Забей, дружище, место на пятерых"
// Эти 5 вызовов — просто праздник, O(1) каждый, реаллокаций нет
for (int i = 0; i < 5; ++i) {
v.push_back(i); // Всё гладко, как жопа младенца
}
// А вот этот, шестой вызов — тут-то и начнётся пиздец.
// Места нет, capacity станет, скажем, 10.
// Все 5 старых элементов поедут на новое место, сложность O(N).
v.push_back(5);
std::cout << "Size: " << v.size() << std::endl; // 6
std::cout << "Capacity: " << v.capacity() << std::endl; // 10
return 0;
}Так что же делать, чтобы не бздеть за производительность? Да всё просто, чувак! Если ты хоть примерно представляешь, сколько элементов будет, — используй reserve(). Это как сказать вектору заранее: "Слушай, пацан, готовь место, ща народ подъедет". Это позволит избежать этих ёбаных реаллокаций в самый неподходящий момент и даст тебе по-настоящему константное время добавления, пока зарезервированное место не кончится. Иначе потом будешь сидеть и думать: "Ну какого хуя всё так тормозит?", а это всё он, этот хитрожопый вектор, переезжает.