изменение размера по сравнению с push_back в std :: vector: избегает ли это ненужного копирования? - PullRequest
22 голосов
/ 14 декабря 2009

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

myVector.push_back(MyVectorElement());

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

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

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

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

Ответы [ 11 ]

19 голосов
/ 14 декабря 2009

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

Если вы хотите знать, что лучше использовать на практике, я бы предложил либо push_backили reserve, поскольку resize будет изменять размер вектора при каждом вызове, если только он не совпадает с запрошенным размером.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);
    }
}

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

1
Construct
Copy
Destruct
Destruct

2
Construct
Copy
Destruct
Destruct
16 голосов
/ 14 декабря 2009

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

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

6 голосов
/ 18 декабря 2009

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

  1. Добавить конструктор move в класс:

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

    С gcc я получаю «Move» вместо «Copy» в качестве вывода для push_back, что в целом гораздо эффективнее.

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

    v.emplace_back()

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

1
Construct
Destruct

2
Construct
Copy
Destruct
Destruct
6 голосов
/ 14 декабря 2009

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

4 голосов
/ 14 декабря 2009

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

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

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

  • reserve()

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

  • resize()

    Это фактически добавляет / удаляет элементы в векторе, чтобы сделать его правильным.

  • capacity()

    Общее количество элементов, которое можно сохранить до того, как базовое хранилище необходимо будет перераспределить. Таким образом, если capacity() > size() push_back не приведет к перераспределению памяти вектора.

3 голосов
/ 14 декабря 2009

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

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

2 голосов
/ 18 декабря 2009

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

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

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

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

2 голосов
/ 14 декабря 2009

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

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

Конструкция выглядит так:

::new (p) _T1(_Val);

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

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

2 голосов
/ 14 декабря 2009
myVector.resize(myVector.size() + 1);

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

1 голос
/ 14 декабря 2009

push_back : вы создаете объект, и он копируется в вектор.
resize : вектор создает объект с конструктором по умолчанию и копирует его в вектор.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...