Was ist der beste Weg, um zwei Vektoren zu verketten?

189

Ich verwende Multitreading und möchte die Ergebnisse zusammenführen. Beispielsweise:

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

Ich möchte, dass AB den Inhalt von A und den Inhalt von B in dieser Reihenfolge hat. Was ist der effizienteste Weg, so etwas zu tun?

jmasterx
quelle
1
Wenn Sie bei der Arbeit mit großen Containern nach Effizienz suchen, ist es möglicherweise effizienter, Listen zu verwenden, bei denen Sie mit mehreren Zeigeroperationen eine Verbindung zueinander herstellen können. Die Liste hat jedoch Speicherplatz (erwägen Sie die Verwendung einer einzelnen verknüpften Liste).
Kemin Zhou

Antworten:

316
AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );
Kirill V. Lyadvinsky
quelle
6
Vielen Dank! Hätte nicht an Reserve gedacht.
Jmasterx
10
es sollte jedes Element kopieren, also ist es O (n)
Kirill V. Lyadvinsky
1
Sie sind sich nicht sicher, ob Sie eine neue Frage stellen sollen oder nicht, aber kann diese Antwort unter Berücksichtigung der Verschiebungssemantik verbessert werden? Kann ich vom Compiler erwarten, dass er eine einzelne Speicherverschiebung ausführt, anstatt alle Elemente zu durchlaufen?
Broes De Cat
2
@boycy Nein. Es wird eine konstante Zeit amortisiert, um ein Element zurückzuschieben. N Elemente zurückzuschieben ist O (n)
Konrad Lindenbach
1
@Konrad habe ich nicht anders angedeutet, aber danke für die Klarstellung. Beachten Sie, dass die Komplexität einer Einfügeoperation niemals in Bezug auf die Anzahl der eingefügten Elemente angegeben wird - was immer O (n) ergibt -, sondern in Bezug auf die Anzahl der Elemente, die sich bereits im Container befinden, da dies ein Maß für ihre Skalierbarkeit darstellt .
Boycy
64

Genau dafür ist die Member-Funktion std::vector::insertgedacht

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
Shirik
quelle
4
@ Nick: Langsam im Vergleich zu was?
GManNickG
2
Vielleicht, dass auf jeder Elementeinfügung genügend Platz vorhanden ist? Wenn Sie vorher Reserve verwenden, wird dies beschleunigt.
RvdK
10
@Nick: Es würde mich nicht wundern, wenn jede moderne stdlib-Implementierung auf insertIteratoren mit wahlfreiem Zugriff spezialisiert und im Voraus reserviert wäre.
GManNickG
1
@Gman: Das ist ein fairer Punkt, da wir wissen, dass die Quelle auch ein Vektor ist (wobei der Iterator distanceeine O (1) -Komplexität aufweist). Die Leistungsgarantien von insertsind jedoch zu beachten, wenn Sie durch vorausschauende Planung häufig bessere Ergebnisse erzielen können.
Nick Bastin
2
@RvdK Überprüfung auf Speicherplatz ist nur ein paar Anweisungen: Ladekapazität, Vergleich mit Größe, bedingter Sprung; All dies sind in den meisten Fällen vernachlässigbare Kosten. Da size < capacitydie Verzweigungsvorhersage die meiste Zeit wahrscheinlich dazu führt, dass sich die Befehle der nicht neu zugewiesenen Verzweigung in der Befehlspipeline befinden, wird die durch Verzweigungen induzierte Latenz minimiert, mit Ausnahme einer geringen Iterationszahl. Dies setzt eine gute Vektorimplementierung sowie eine CPU-Befehlspipeline und eine [gute] Verzweigungsvorhersage voraus, aber dies sind ziemlich zuverlässige Annahmen für eine moderne Toolchain und Desktop-Maschine. Ich weiß aber nichts über Smartphones.
Boycy
27

Hängt davon ab, ob Sie die beiden Vektoren wirklich physisch verketten müssen oder ob Sie aus Gründen der Iteration den Anschein einer Verkettung erwecken möchten. Die Funktion boost :: join

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

werde dir das geben.

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

sollte dir geben

1
2
3
4
5
6

Hinweis boost :: join kopiert die beiden Vektoren nicht in einen neuen Container, sondern generiert ein Paar Iteratoren (Bereich), die die Spanne beider Container abdecken. Es wird einen gewissen Leistungsaufwand geben, aber möglicherweise weniger, als zuerst alle Daten in einen neuen Container zu kopieren.

Bradgonesurfing
quelle
1
Gute Idee. Nachdem ich eine Weile nachgedacht hatte, wurde mir klar, dass dieses Ziel auch ohne die Verwendung von Boost-Bibliotheken erreicht werden kann. Ich habe eine Antwort gepostet, in der erklärt wird, wie.
Ronald Souza
11

Basierend auf der Antwort von Kiril V. Lyadvinsky habe ich eine neue Version erstellt. Dieses Snippet verwendet Vorlage und Überladung. Damit können Sie schreiben vector3 = vector1 + vector2und vector4 += vector3. Hoffe es kann helfen.

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 wechselt zu codidact.com
quelle
1
Wollen Sie die Elemente jedes Vektors miteinander addieren? Oder du willst anhängen? Dies ist jetzt klar, aber für die nächsten 5 Jahre ..? Sie sollten den Operator nicht überladen, wenn die Bedeutung nicht eindeutig ist.
SR
2
@ SR Ich meine zu konzernieren. Ich habe diese Antwort vor 3 Jahren geschrieben. Ich weiß immer noch, was es bedeutet. Kein Problem da. Wenn C ++ eine eigene Überlastung bereitstellen könnte, wäre dies sogar noch besser. (und ja ::wird genommen;)
Aloisdg wechselt zu codidact.com
Im Allgemeinen definitiv nicht klar, dass v1 + v2dies keine Addition darstellt.
Apollys unterstützt Monica
@Apollys gut
Aloisdg Umzug zu codidact.com
Alternative wäre, @wie in F # zu verwenden
Aloisdg Umzug zu codidact.com
5

In Richtung Bradgonesurfing Antwort, hat oft ein nicht wirklich braucht zwei Vektoren verketten (O (n)), sondern nur mit ihnen arbeiten , als ob sie verkettet wurden (O (1)) . Wenn dies der Fall ist, können Boost-Bibliotheken benötigt werden.

Der Trick besteht darin, einen Vektor-Proxy zu erstellen: eine Wrapper-Klasse, die Verweise auf beide Vektoren manipuliert , die extern als ein einziger zusammenhängender Vektor betrachtet werden .

VERWENDUNG

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

IMPLEMENTIERUNG

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

Hauptnutzen

Es ist O (1) (konstante Zeit), um es zu erstellen, und mit minimaler zusätzlicher Speicherzuweisung.

EINIGES PERSONAL ZU ÜBERLEGEN

  • Sie sollten es nur versuchen, wenn Sie wirklich wissen, was Sie im Umgang mit Referenzen tun . Diese Lösung ist für den spezifischen Zweck der gestellten Frage gedacht, für die sie ziemlich gut funktioniert . Die Verwendung in einem anderen Kontext kann zu unerwartetem Verhalten führen, wenn Sie nicht sicher sind, wie Referenzen funktionieren.
  • In diesem Beispiel stellt AB keinen nicht konstanten Zugriffsoperator ([]) bereit. Fühlen Sie sich frei, es einzuschließen, aber denken Sie daran: Da AB Referenzen enthält, wirkt sich das Zuweisen von Werten auch auf die ursprünglichen Elemente in A und / oder B aus. Ob dies eine wünschenswerte Funktion ist oder nicht, es ist eine anwendungsspezifische Frage, die Sie stellen sollten sorgfältig überlegen.
  • Alle Änderungen, die direkt an A oder B vorgenommen werden (wie das Zuweisen von Werten, Sortieren usw.), "modifizieren" auch AB. Dies ist nicht unbedingt schlecht (tatsächlich kann es sehr praktisch sein: AB muss niemals explizit aktualisiert werden, um sich selbst mit A und B synchron zu halten), aber es ist sicherlich ein Verhalten, das man beachten muss. Wichtige Ausnahme: Wenn Sie die Größe von A und / oder B auf etwas Größeres ändern , werden diese möglicherweise im Speicher neu zugewiesen (für den Bedarf an zusammenhängendem Speicherplatz), was wiederum AB ungültig macht.
  • Da jedem Zugriff auf ein Element ein Test vorausgeht (nämlich "i <v1.size ()"), ist die VecProxy-Zugriffszeit, obwohl sie konstant ist, auch etwas langsamer als die von Vektoren.
  • Dieser Ansatz kann auf n Vektoren verallgemeinert werden. Ich habe es nicht versucht, aber es sollte keine große Sache sein.
Ronald Souza
quelle
2

Eine weitere einfache Variante, die noch nicht erwähnt wurde:

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

Und mit dem Merge-Algorithmus:

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

D. Alex
quelle
-1

Wenn Ihre Vektoren * sortiert sind, überprüfen Sie set_union unter <Algorithmus>.

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

Der Link enthält ein ausführlicheres Beispiel

* danke rlbond

Zahnrad
quelle
4
Außerdem funktioniert es nicht wie ein gerades Anhängen - die Elemente im Ausgabebereich sind eindeutig, was möglicherweise nicht das ist, was das OP wollte (sie sind möglicherweise nicht einmal vergleichbar). Es ist sicherlich nicht die effizienteste Art, dies zu tun.
Peter
-1

Alle Lösungen sind korrekt, aber ich fand es einfacher, einfach eine Funktion zu schreiben, um dies zu implementieren. so was:

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

Auf diese Weise können Sie die vorübergehende Platzierung wie folgt vermeiden:

ContainerInsert(vec, GetSomeVector());
user3360767
quelle