c++ конкатенация (объединение) 2х векторов

Question

Какой самый быстрый способ объединения 2х векторов (std::vector)? Т.е. присоединить вектор 2 к вектору 1. Нужен вариант как с move семантикой, чтобы вектор 2 был пустым, так и с копированием (наиболее быстрым), и еще для POD типов (опять таки быстрый). Ну и как дополнение к вопросу: а если нужно соединить более 2х векторов?

Answer 1

Ниже функция которая переносит элементы вектора b в конец вектора a. Если вы хотите использовать её много раз с одним и тем же вектором a, рекомендую вызвать a.reserve() с размером равным длине ожидаемого результата.

Если вы не хотите разрушать элементы b, уберите вызовы std::make_move_iterator.

template<typename Item>
void concat(std::vector<Item> &a, std::vector<Item> &b) {
    a.insert(
        a.end(),
        std::make_move_iterator(b.begin()),
        std::make_move_iterator(b.end())
    );
}

Этот код работает одинаково хорошо и для POD и для сложных типов с конструкторами. Например берём код

struct S { int i; };

void concat(std::vector<S> &a, std::vector<S> &b) {
    a.insert(
        a.end(),
        std::make_move_iterator(b.begin()),
        std::make_move_iterator(b.end())
    );
}

Компилируем его с оптимизацией в ассемблер: g++ -S -O3 concat.cpp. В файле concat.s можно найти код в котором в основной ветке, когда места в векторе a достаточно, вызывается call memmove один раз. Если места недостаточно, то в коде выделяется новая память и делаются два вызова call memcpy (старые данные a) и call memove (новые данные из b). Циклов нигде нет, всё настолько оптимально насколько возможно.

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

БЛОГ НА HUSL

c++ конкатенация (объединение) 2х векторов

Ответы (1 шт):