Jaki jest najlepszy sposób na połączenie dwóch wektorów?

Używam wielowątkowości i chcę scalić wyniki. Na przykład:

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

Chcę, aby AB musiał mieć zawartość A i zawartość B w tej kolejności. Jaki jest najbardziej efektywny sposób zrobienia czegoś takiego?

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

To właśnie funkcja członek std::vector::insertjest dla

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

Zależy od tego, czy naprawdę musisz fizycznie połączyć dwa wektory, czy chcesz sprawić wrażenie konkatenacji ze względu na iterację. Funkcja boost :: join

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

da ci to.

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;
}

powinienem ci dać

1
2
3
4
5
6

Uwaga boost :: join nie kopiuje dwóch wektorów do nowego kontenera, ale generuje parę iteratorów (zakres), które pokrywają rozpiętość obu kontenerów. Wystąpi pewien narzut wydajności, ale być może mniejszy niż skopiowanie wszystkich danych do nowego kontenera w pierwszej kolejności.

Na podstawie odpowiedzi Kirila V. Lyadvinsky'ego stworzyłem nową wersję. Ten szablon użycia fragmentu kodu i przeciążenie. Dzięki niemu możesz pisać vector3 = vector1 + vector2i vector4 += vector3. Mam nadzieję, że to może pomóc.

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
}

Zgodnie z odpowiedzią Bradgonesurfing wiele razy nie trzeba tak naprawdę łączyć dwóch wektorów (O (n)), ale po prostu pracować z nimi tak, jakby były one połączone (O (1)) . Jeśli tak jest w twoim przypadku, można to zrobić bez potrzeby bibliotek Boost.

Sztuką jest utworzenie wektorowego proxy: klasy opakowania, która manipuluje odwołaniami do obu wektorów, zewnętrznie postrzeganych jako pojedynczy, ciągły.

STOSOWANIE

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

REALIZACJA

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

GŁÓWNE KORZYŚCI

Jest O (1) (czas stały), aby go utworzyć, przy minimalnym przydziale dodatkowej pamięci.

NIEKTÓRZY RZECZY DO ROZWAŻENIA

• Powinieneś to zrobić tylko wtedy, gdy naprawdę wiesz, co robisz, zajmując się referencjami . To rozwiązanie jest przeznaczone do konkretnego celu postawionego pytania, dla którego działa całkiem dobrze . Zastosowanie go w innym kontekście może prowadzić do nieoczekiwanego zachowania, jeśli nie masz pewności, jak działają odwołania.
• W tym przykładzie AB nie zapewnia operatora non-const access ([]). Uwzględnij go, ale pamiętaj: ponieważ AB zawiera referencje, przypisanie mu wartości wpłynie również na oryginalne elementy w A i / lub B. Niezależnie od tego, czy jest to pożądana cecha, należy zadać pytanie dotyczące aplikacji dokładnie zastanów się.
• Wszelkie zmiany dokonane bezpośrednio w A lub B (takie jak przypisywanie wartości, sortowanie itp.) Również „modyfikują” AB. Niekoniecznie jest to złe (w rzeczywistości może być bardzo przydatne: AB nigdy nie musi być wyraźnie aktualizowana, aby zachować synchronizację z A i B), ale z pewnością jest to zachowanie, o którym należy pamiętać. Ważny wyjątek: zmiana rozmiaru A i / lub B na coś większego może spowodować, że zostaną one ponownie przydzielone w pamięci (ze względu na potrzebę ciągłego miejsca), a to z kolei unieważni AB.
• Ponieważ każdy dostęp do elementu jest poprzedzony testem (mianowicie „i <v1.size ()”), czas dostępu VecProxy, chociaż stały, jest również nieco wolniejszy niż w przypadku wektorów.
• To podejście można uogólnić na n wektorów. Nie próbowałem, ale to nie powinna być wielka sprawa.

Jeszcze jeden prosty wariant, o którym jeszcze nie wspomniano:

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

I używając algorytmu scalania:

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

Jeśli twoje wektory są posortowane *, sprawdź set_union w <algorytm>.

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

Link zawiera dokładniejszy przykład

* dzięki rlbond

Wszystkie rozwiązania są poprawne, ale łatwiej mi było napisać funkcję, aby to zaimplementować. lubię to:

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

W ten sposób możesz uniknąć tymczasowego umieszczenia:

ContainerInsert(vec, GetSomeVector());