Каков наилучший способ объединить два вектора?

190

Я использую многопоточность и хочу объединить результаты. Например:

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

Я хочу, чтобы AB содержал содержимое A и содержимое B в указанном порядке. Какой самый эффективный способ сделать что-то подобное?

jmasterx
источник
1
Если вы ищете эффективность при работе с контейнерами большого размера, может быть более эффективно использовать список, в котором вы можете соединить один с другим несколькими операциями с указателями. Но у списка есть служебная память (подумайте об использовании единого связанного списка).
Кемин Чжоу

Ответы:

323
AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );
Кирилл В. Лядвинский
источник
6
Спасибо! Не подумал бы о резерве.
jmasterx
10
он должен копировать каждый элемент, так что это O (n)
Кирилл В. Лядвинский
1
Не уверен, стоит ли задавать новый вопрос или нет, но можно ли улучшить этот ответ, принимая во внимание семантику перемещения? Есть ли какой-то способ, которым я могу ожидать / дать указание компилятору выполнить одно перемещение в памяти вместо зацикливания на всех элементах?
Broes De Cat,
2
@ Boycy Нет. Амортизируется постоянное время для push_back одного элемента. Отодвинуть n элементов - это O (n)
Конрад Линденбах
1
@ Конрад Я не имел в виду иначе, но спасибо за разъяснения. Обратите внимание, что сложность операции вставки никогда не указывается с точки зрения количества вставляемых элементов, которое всегда будет давать O (n), но с точки зрения количества элементов, уже находящихся в контейнере, поскольку это обеспечивает меру его масштабируемости. ,
мальчик
65

Это именно то , что функция член std::vector::insertдля

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
Shirik
источник
4
@ Ник: Медленный по сравнению с чем?
GManNickG
2
Может быть, он проверяет, достаточно ли места на каждой вставке элемента? Использование резерва заранее ускорит его.
RvdK
10
@Nick: Я не удивлюсь, если каждая современная реализация stdlib специализируется insertна итераторах с произвольным доступом и зарезервирована заранее .
GManNickG
1
@Gman: Это справедливо, поскольку мы знаем, что источником является также вектор (где итератор distanceимеет сложность O (1)). Тем не менее, гарантии производительности insert- это то, о чем следует помнить, когда вы часто можете добиться большего успеха, планируя заранее.
Ник Бастин
2
@RvdK проверка на наличие места - это всего лишь несколько инструкций: загрузка, сравнение с размером, условный переход; все это незначительная стоимость в большинстве случаев. Поскольку в size < capacityбольшинстве случаев предсказание ветвления, скорее всего, приведет к тому, что команды нераспределенного ветвления окажутся в конвейере команд, что минимизирует задержку, вызванную ветвлением, за исключением низкого количества итераций. Это предполагает хорошую векторную реализацию, плюс конвейер инструкций процессора и [хорошее] предсказание ветвлений, но это довольно надежные предположения для современного набора инструментов и настольного компьютера. Не знаю, как насчет смартфонов ..
Бойси
27

Зависит от того, действительно ли вам нужно физически объединить два вектора или вы хотите создать вид конкатенации ради итерации. Функция boost :: join

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/utilities/join.html

даст вам это.

std::vector<int> v0;
v0.push_back(1);
v0.push_back(2);
v0.push_back(3);

std::vector<int> v1;
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
...

BOOST_FOREACH(const int & i, boost::join(v0, v1)){
    cout << i << endl;
}

должен дать вам

1
2
3
4
5
6

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

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

Исходя из ответа Кирилла Лядвинского , я сделал новую версию. Этот фрагмент использования шаблона и перегрузки. С его помощью вы можете написать vector3 = vector1 + vector2и vector4 += vector3. Надеюсь, это поможет.

template <typename T>
std::vector<T> operator+(const std::vector<T> &A, const std::vector<T> &B)
{
    std::vector<T> AB;
    AB.reserve(A.size() + B.size());                // preallocate memory
    AB.insert(AB.end(), A.begin(), A.end());        // add A;
    AB.insert(AB.end(), B.begin(), B.end());        // add B;
    return AB;
}

template <typename T>
std::vector<T> &operator+=(std::vector<T> &A, const std::vector<T> &B)
{
    A.reserve(A.size() + B.size());                // preallocate memory without erase original data
    A.insert(A.end(), B.begin(), B.end());         // add B;
    return A;                                        // here A could be named AB
}
aloisdg переходит на codidact.com
источник
1
Вы хотите добавить элементы каждого вектора друг к другу? Или вы хотите добавить? Это ясно сейчас, но в течение следующих 5 лет ..? Вы не должны перегружать оператор, если значение неоднозначно.
SR
2
@ SR Я хочу констатировать. Я написал этот ответ 3 года назад. Я до сих пор знаю, что это значит. Нет проблем там. Если C ++ может обеспечить свою собственную перегрузку, это будет еще лучше. (и да ::принято;)
aloisdg переезжает на codidact.com
Определенно не ясно, в общем, что v1 + v2не представляет собой сложение.
Аполлис поддерживает Монику
@Apollys хорошо
aloisdg переходит на codidact.com
Альтернативой было бы использовать @как в F #
aloisdg переходит на codidact.com
6

В направлении ответа Bradgonesurfing, часто не нужно объединять два вектора (O (n)), а просто работать с ними, как если бы они были объединены (O (1)) . Если это ваш случай, это можно сделать без использования библиотек Boost.

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

ИСПОЛЬЗОВАНИЕ

std::vector<int> A{ 1, 2, 3, 4, 5};
std::vector<int> B{ 10, 20, 30 };

VecProxy<int> AB(A, B);  // ----> O(1). No copies performed.

for (size_t i = 0; i < AB.size(); ++i)
    std::cout << AB[i] << " ";  // 1 2 3 4 5 10 20 30

РЕАЛИЗАЦИЯ

template <class T>
class VecProxy {
private:
    std::vector<T>& v1, v2;
public:
    VecProxy(std::vector<T>& ref1, std::vector<T>& ref2) : v1(ref1), v2(ref2) {}
    const T& operator[](const size_t& i) const;
    const size_t size() const;
};

template <class T>
const T& VecProxy<T>::operator[](const size_t& i) const{
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};

template <class T>
const size_t VecProxy<T>::size() const { return v1.size() + v2.size(); };

ОСНОВНАЯ ВЫГОДА

Это O (1) (постоянное время) для его создания и с минимальным выделением дополнительной памяти.

НЕКОТОРЫЕ ВЕЩИ ДЛЯ РАССМОТРЕНИЯ

  • Вы должны пойти на это, только если вы действительно знаете, что делаете, когда имеете дело со ссылками . Это решение предназначено для конкретной цели поставленного вопроса, для которого оно работает довольно хорошо . Использование его в любом другом контексте может привести к неожиданному поведению, если вы не уверены в том, как работают ссылки.
  • В этом примере AB не предоставляет неконстантный оператор доступа ([]). Не стесняйтесь включать его, но имейте в виду: поскольку AB содержит ссылки, присвоение ему значений также повлияет на исходные элементы в A и / или B. Независимо от того, является ли это желательной функцией, это вопрос для конкретного приложения, который следует внимательно обдумайте.
  • Любые изменения, внесенные непосредственно в A или B (например, присвоение значений, сортировка и т. Д.), Также «изменят» AB. Это не обязательно плохо (на самом деле, это может быть очень удобно: AB никогда не нужно явно обновлять, чтобы синхронизировать себя как с A, так и с B), но это определенно поведение, о котором нужно знать. Важное исключение: изменение размера A и / или B до большего может привести к тому, что они будут перераспределены в памяти (для непрерывного пространства), что, в свою очередь, приведет к аннулированию AB.
  • Поскольку каждому доступу к элементу предшествует тест (а именно, «i <v1.size ()»), время доступа VecProxy, хотя и постоянное, также немного медленнее, чем у векторов.
  • Этот подход можно обобщить на n векторов. Я не пробовал, но это не должно иметь большого значения.
Рональд Соуза
источник
2

Еще один простой вариант, который еще не был упомянут:

copy(A.begin(),A.end(),std::back_inserter(AB));
copy(B.begin(),B.end(),std::back_inserter(AB));

И используя алгоритм слияния:

#include <algorithm> #include <vector> #include <iterator> #include <iostream> #include <sstream> #include <string> template<template<typename, typename...> class Container, class T> std::string toString(const Container<T>& v) { std::stringstream ss; std::copy(v.begin(), v.end(), std::ostream_iterator<T>(ss, "")); return ss.str(); }; int main() { std::vector<int> A(10); std::vector<int> B(5); //zero filled std::vector<int> AB(15); std::for_each(A.begin(), A.end(), [](int& f)->void { f = rand() % 100; }); std::cout << "before merge: " << toString(A) << "\n"; std::cout << "before merge: " << toString(B) << "\n"; merge(B.begin(),B.end(), begin(A), end(A), AB.begin(), [](int&,int&)->bool {}); std::cout << "after merge: " << toString(AB) << "\n"; return 1; }

Д. Алекс
источник
-1

Если ваши векторы отсортированы *, посмотрите set_union из <алгоритма>.

set_union(A.begin(), A.end(), B.begin(), B.end(), AB.begin());

В ссылке есть более подробный пример

* спасибо Rlbond

Зубчатое колесо
источник
4
кроме того, он не делает то же самое, что и прямое добавление - элементы в выходном диапазоне уникальны, что может не соответствовать желаемому OP (они могут даже не сравниваться). Это, конечно, не самый эффективный способ сделать это.
Питер
-1

Все решения правильные, но мне было проще написать функцию для реализации этого. как это:

template <class T1, class T2>
void ContainerInsert(T1 t1, T2 t2)
{
    t1->insert(t1->end(), t2->begin(), t2->end());
}

Таким образом, вы можете избежать временного размещения, как это:

ContainerInsert(vec, GetSomeVector());
user3360767
источник