Изменить размер по сравнению с push_back в std::vector: избегает ли ненужное назначение копии?

При вызове метода push_back из std::vector его размер увеличивается на единицу, подразумевая при создании нового экземпляра, а затем передаваемый вами параметр будет скопирован в этот недавно созданный элемент, правильно? Пример:

myVector.push_back(MyVectorElement());

Ну, тогда, если я хочу увеличить размер вектора с помощью элемента, просто используя его значения по умолчанию, не лучше ли использовать метод resize? Я имею в виду вот так:

myVector.resize(myVector.size() + 1);

Насколько я вижу, это будет делать то же самое, но позволит избежать совершенно ненужной присваивающей копии атрибутов элемента.

Правильно ли это рассуждение или я что-то упускаю?

11 ответов

По крайней мере, с GCC, не имеет значения, что вы используете (результаты ниже). Однако, если вы дойдете до такой степени, что вам приходится беспокоиться об этом, вы должны использовать указатели или (еще лучше) некоторую форму умных указателей.. Я бы, конечно, рекомендовал те, что были в библиотеке boost.

Если бы вы хотели знать, что лучше использовать на практике, я бы предложил либо push_back, либо reserve, поскольку изменение размера будет изменять размер вектора каждый раз, когда он вызывается, если он не имеет размер, соответствующий требуемому размеру. push_back и резерв будет только изменять размер вектора, если это необходимо. Это хорошо, как если бы вы хотели изменить размер вектора на size+1, он уже может быть на size+20, поэтому изменение размера вызова не принесет никакой пользы.

Тестовый код

#include <iostream>
#include <vector>
class Elem{
 public:
 Elem(){
 std::cout << "Construct\n";
 }
 Elem(const Elem& e){
 std::cout << "Copy\n";
 }
 ~Elem(){
 std::cout << "Destruct\n";
 } 
};
int main(int argc, char* argv[]){
 {
 std::cout << "1\n";
 std::vector<elem> v;
 v.push_back(Elem());
 }
 {
 std::cout << "\n2\n";
 std::vector<elem> v;
 v.resize(v.size()+1);
 }
}
</elem></elem></vector></iostream>

Тестовый выход

1
Construct
Copy
Destruct
Destruct
2
Construct
Copy
Destruct
Destruct


Я нахожу myVector.push_back(MyVectorElement()); гораздо более прямым и понятным для чтения.

Дело в том, что resize не просто изменяет размеры элементов массива и элементов по умолчанию в этих местах; это то, что он по умолчанию. На самом деле он принимает второй параметр, который будет составлять каждый новый элемент, и по умолчанию это значение T(). По сути, ваши два примера кода точно совпадают.


A С++ 0x перспектива относительно тестового кода принятого ответа Якоби:

  • Добавьте переместить конструктор в класс:

    Elem(Elem&& e) { std::cout << "Move\n"; }

    С gcc я получаю "Move" вместо "Copy" в качестве вывода для push_back, что намного эффективнее вообще.

  • Даже немного лучше с заменить операции (принять то же самое аргументы как конструктор):

    v.emplace_back()

Выход теста:

1
Construct
Destruct
2
Construct
Copy
Destruct
Destruct


В EA (Electronic Arts) это считалось такой большой проблемой, что они написали собственную версию STL, EASTL, которая среди многих другие вещи включают push_back(void) в свой класс vector.


Когда вы выполняете push_back(), метод проверяет базовую область хранения, чтобы увидеть, требуется ли пространство. Если пространство необходимо, оно будет выделять новую конхуальную область для всех элементов и копировать данные в новые.

НО: размер вновь выделенного пространства не только один элемент больше. Он использует отличный алгоритм для увеличения пространства (я не думаю, что алгоритм определен как часть стандарта, но обычно удваивает выделенное пространство). Таким образом, если вы нажимаете большое количество элементов, лишь небольшой процент из них на самом деле вызывает перераспределение основного пространства.

Чтобы реально увеличить выделенное пространство вручную, у вас есть два варианта:

  • резерв() Это фактически увеличивает базовое пространство для хранения без добавления элементов к вектору. Таким образом, менее вероятно, что будущий puah_back() потребует увеличения пространства.
  • размер() Это фактически добавляет/удаляет элементы в вектор, чтобы сделать его правильным.
  • capacity() Общее количество элементов, которые могут быть добавлены до того, как базовый хранилище необходимо перераспределить. Таким образом, если ((capacity() - size()) > 0) push_back не приведет к перераспределению векторного хранилища.


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

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


Когда вы вызываете push_back, при условии, что не требуется изменить размер базового хранилища, класс vector будет использовать оператор "размещение нового" для копирования-сборки новых элементов на месте. Элементы в векторе не будут построены по умолчанию до того, как будут построены копии.

Когда вы вызываете resize, происходит почти такая же последовательность. vector выделяет хранилище, а затем копирует значение по умолчанию с помощью размещения нового в каждое новое место.

Конструкция выглядит следующим образом:

::new (p) _T1(_Val);

Где p - указатель на векторное хранилище, _T1 - это тип, который хранится в векторе, а _Val - параметр "по умолчанию" (по умолчанию - _T1()).

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


myVector.resize(myVector.size() + 1);

вызовет пустой конструктор MyVectorElement. Что вы пытаетесь достичь? Для резервирования места в векторе (и сохранения служебных данных памяти) существует метод reserve(). Вы не можете избежать конструктора.


Очевидно, вы беспокоитесь об эффективности и производительности.

std::vector на самом деле очень хороший исполнитель. Используйте метод запаса для предварительного распределения пространства, если вы знаете, насколько он может быть большой. Очевидно, что это за счет потенциально потраченной впустую памяти, но при использовании push_back это может оказать значительное влияние.

Я полагаю, что реализация зависит от того, сколько памяти зарезервировано впереди для вектора, если вообще есть или сколько зарезервировано для будущего использования в качестве элементов. Худший сценарий - это то, что вы заявляете, - только растет по одному элементу за раз.

Попробуйте выполнить тестирование производительности в своем приложении, сравнив его без резерва и с ним.


push_back: вы создаете объект и копируете его в вектор. изменить размер: вектор создает объект со стандартным конструктором и копирует его в вектор.

Разница в скорости. Вам придется протестировать вашу реализацию STL и вашего компилятора, но я думаю, что это не имеет значения.


Я подозреваю, что фактический ответ сильно зависит от реализации STL и используемого компилятора, однако функция "resize" имеет прототип ( ref)

void resize( size_type num, TYPE val = TYPE() );

который подразумевает, что значение по умолчанию сконфигурировано и скопировано в новое выделенное (или, возможно, ранее выделенное, но неиспользуемое) пространство с помощью места размещения new и copy-constructor. Таким образом, обе операции требуют одинаковой последовательности действий:

  • Вызов конструктора по умолчанию
  • Выделить пространство
  • Инициализировать через конструктор копирования

Вероятно, лучше отложить до более четкого и более общего (в терминах контейнеров STL) push_back, а не применять преждевременную оптимизацию - если профилировщик выделяет push_back как горячую точку, то наиболее вероятной причиной является выделение памяти, которое наилучшим образом разрешен путем разумного использования резерва.

licensed under cc by-sa 3.0 with attribution.