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

Question

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

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

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

Answer 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() );

Answer 2

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

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

Answer 3

Зависит от того, действительно ли вам нужно физически объединить два вектора или вы хотите создать вид конкатенации ради итерации.Функция 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

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

Answer 4

На основании Кирил В. Лядвинский ответ , я сделал новую версию. Этот фрагмент использования шаблона и перегрузки. С его помощью вы можете написать 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
}

Answer 5

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

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

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

</p>

<code>#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;
}
</code>

Answer 6

В направлении ответа Bradgonesurfing, много раз одному действительно не нужно для объединения двух векторов, а вместо этого просто работайте с ними, как если бы они были объединены .Это похоже на ваш случай, и это может быть сделано без использования библиотек Boost.

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

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

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

VecProxy<int> AB(A, B);  // ----> O(1)

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

std::cout << AB[6]; // ----> Output: 20

РЕАЛИЗАЦИЯ

template <class T>
class VecProxy {
private:
    std::vector<T>& v1;
    std::vector<T>& v2;
public:
    VecProxy(std::vector<T>& ref1, std::vector<T>& ref2) : v1(ref1), v2(ref2) {}
    T& operator[](const size_t& i);
    const T& operator[](const size_t& i) const;
    const size_t size() const;
};
template<class T>
T& VecProxy<T>::operator[](const size_t& i){
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};
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) (постоянное время) для его создания и с минимальным выделением дополнительной памяти.На практике это быстрая операция даже при рассмотрении огромных векторов, поскольку вы заменяете | B |(или | A | + | B |) копирует элемент на ноль.Кроме того, он обеспечивает именно желаемое поведение.

Конкатенация векторов составляет не менее O (| B |) (когда B добавляется к A), независимо от применяемой методики.В вашем случае, поскольку вы намереваетесь работать с третьим вектором, AB, это O (| A | + | B |).В зависимости от размера векторов и количества необходимых операций конкатенации, это может быть узким местом.Приведенный выше трюк обращается к нему.

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

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

Answer 7

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

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

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

ContainerInsert(vec, GetSomeVector());

Answer 8

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

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

Более подробный пример приведен в ссылке

* благодаря rlbond