Конкатенация двух std::vector, какой метод более эффективен и как/почему?

Рассмотрим следующий сценарий:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

Я хочу, чтобы AB имел содержимое A, а затем содержимое B в том же порядке.

Подход 1:

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );

Подход 2:

std::vector<int> AB ( A.begin(), A.end() ); // calling constructor
AB.insert ( AB.end(), B.begin(), B.end() );

Какой из перечисленных методов более эффективен? Почему? Есть ли другой метод, более эффективный?


c++ performance concatenation stdvector
person CinCout    schedule 09.10.2014    source источник
comment
Вы пробовали его измерять?   -  person Chris Drew    schedule 09.10.2014
comment
Ну, это сильно зависит от размера обоих векторов и реализации алгоритма распределения векторов.   -  person EdChum    schedule 09.10.2014
comment
Не уверен, проверяли ли вы, но помните, что производительность — это то, чем вы должны заниматься только после того, как установили, что это проблема. Если только ваши векторы не огромны или элементы внутри них не требуют больших затрат для создания /copy, вы не заметите большой разницы. Не тратьте много времени на сокращение операции с 0,2 мс до 0,1 мс, если только вам не нужно делать это тысячи раз в секунду :-)   -  person paxdiablo    schedule 09.10.2014
comment
Если производительность не является проблемой, я бы посоветовал вам выбрать тот, который вам легче читать. Читаемость кода очень важна, когда вы возвращаетесь к своему коду спустя долгое время.   -  person rozina    schedule 09.10.2014

Ответы (3)


arrow_upward
1
arrow_downward

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

std::vector<int> AB(A.size() + B.size());
std::copy(A.begin(), A.end(), AB.begin());
std::copy(B.begin(), B.end(), AB.begin() + B.size());

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

person Chris Drew    schedule 09.10.2014
comment
недостаток в том, что приходится обнулять всю память -- я посмотрел на сгенерированную сборку и не могу объяснить такую ​​огромную разницу, но очевидно, что оптимизатор убрал обнуление памяти Память. Базовый сгенерированный код для первого и вашего варианта одинаков, но код структурирован немного по-другому, похоже, что оптимизатор был лучше подготовлен для обработки этого последнего варианта... - person David Rodríguez - dribeas; 11.10.2014
comment
@DavidRodríguez-dribeas Интересно. Это не первый раз, когда я был удивлен, насколько эффективен метод обнуления памяти и перезаписи по сравнению с подходом резервирования памяти и вставки. Например, std::vector<int> A(size); for(size_t i=0;i!=size;++i) A[i]=func(i); работает на удивление хорошо. А может вы и правы, причина в том, что оптимизатор убирает обнуление памяти. - person Chris Drew; 11.10.2014

arrow_upward
8
arrow_downward

Первый, вероятно, немного более эффективен, так как вы можете гарантировать, что будет выполнено только одно выделение памяти. Во втором есть вероятность (большинство реализаций), что распределение для A.size() будет выполнено во время построения вектора, а затем insert вызовет второе распределение, поскольку ему нужно увеличиться на B.size() элементов.

person David Rodríguez - dribeas    schedule 09.10.2014

arrow_upward
3
arrow_downward

Подход 1 не выполняет никаких перераспределений, в то время как Подход 2 может перераспределять несколько раз и на практике, скорее всего, перераспределит один раз. Так что подход 1 лучше.

person Kerrek SB    schedule 09.10.2014
comment
Вставляемый диапазон итераторов использует RandomAccessIterators, поэтому количество вставляемых элементов может быть подсчитано за O (1), и поэтому нет оправдания перераспределению более одного раза в подходе 2. - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: Это действительно гарантировано или это просто обычная реализация? (Я знаю, что есть реальная гарантия для конструктора диапазона.) - person Kerrek SB; 09.10.2014
comment
@KerrekSB: это одна из тех вещей, которые будут считаться ошибкой, даже если стандарт этого не гарантирует. - person David Rodríguez - dribeas; 09.10.2014
comment
Это не гарантируется, но именно поэтому я сказал, что это не оправдание, а ошибка, если он перераспределяет :-) Вам обязательно следует пожаловаться своему поставщику, если его реализация не считает элементы при вставке RandomAccessIterators. Конструктор векторов, принимающий диапазон итераторов, требуется для подсчета элементов для всего, кроме InputIterators, но диапазон insert не требуется. - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: я все время жалуюсь своему поставщику :-) - person Kerrek SB; 09.10.2014