c++.de :: Unterschiede zweier std::vectoren in weiterem vector anfügen

Unregistrierter

Hallo zusammen,

folgendes Problem: Ich habe zwei vectoren v1 und v2. Nun sollen alle Items, die in v2 vorhanden und in v1 nicht vorhanden sind, in einen weiteren vector kopiert werden (bzw. würden nur die Referenzen/Indizes reichen).
Die beiden vectoren sind sortiert.
Ich würde das jetzt schnell mit einer kleinen Hilfsfunktion machen, versuche mich aber gerade auch weiter in die Standardbibliothek einzuarbeiten. Daher die Frage, ob diese entsprechendes bereit stellt.

Achja, die Einträge sind Klassen, die einen operator==(const T&) anbieten.

Ideen, Vorschläge?

Unregistrierter

http://en.cppreference.com/w/cpp/algorithm/set_difference

Unregistrierter

So vielleicht?

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24	#include <iostream> #include <algorithm> #include <iterator> #include <sstream> #include <vector> using namespace std; int main() { int ar1[] = {0,1,4,8,9}; vector<int> v1(ar1,ar1+5); int ar2[] = {0,1,2,3,4,5,6,7,8,9}; vector<int> v2(ar2,ar2+10); vector<vector<int>::iterator> iters; for(vector<int>::iterator it=v2.begin(); it!=v2.end(); ++it) { vector<int>::iterator found = find(v1.begin(),v1.end(),*it); if( found==v1.end() ) iters.push_back(it); } }

Unregistrierter

Ah, da hat schon jemand eine bessere und schnellere Antwort geliefert.

Unregistrierter

Danke schon mal für die Antworten. set_difference hatte ich bislang noch nicht verwendet, hier ein erster Versuch:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31	struct T { int i; T(int i) : i(i) {} bool operator==(const T& t) const {return i==t.i;} }; bool operator!=(const T& t1, const T& t2) { return !(t1.operator==(t2)); } int main() { vector<T> v1; vector<T> v2; for(int i=0;i<40;++i) { v2.push_back(i); if(i&1) v1.push_back(i); } vector<T> out; std::set_difference(v2.begin(),v2.end(), v1.begin(),v1.end(), std::back_inserter<std::vector<T> >(out), std::not_equal_to<T>()); for(size_t i=0;i<out.size();++i) cout << out[i].i << endl; }

Klappt ja schon mal.
Eine Funktion, die nur die Referenzen oder Indizes speichert, muss man sich dann wahrscheinlich, wie out es gemacht hat, selber schreiben. Die Objekte sind nämlich nicht so einfach zu kopieren wie im obigen Beispiel.

Durch die Sortierung müsste das natürlich noch etwas besser gehen.

Ich kann ja dann mal meine Lösung posten (falls es jemanden interessiert).

Besten Dank.

ZuK Mitglied 14:43:38 20.08.2012 Titel:

comparor schrieb:

Durch die Sortierung müsste das natürlich noch etwas besser gehen.

Soviel ich weiss müssen die beiden vectoren/sets/listen was auch immer, sortiert sein.
Kurt

krümelkacker Mitglied 15:50:45 20.08.2012 Titel:

comparor schrieb:

C++:
std::back_inserter<std::vector<T> >(out)

Nö. back_inserter ist ein Funktionstemplate. Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen -- so wie auch hier:

C++:
std::back_inserter(out)

comparor schrieb:

Durch die Sortierung müsste das natürlich noch etwas besser gehen.

die Mengen-Operationen verlangen sogar geordnete Sequenzen. Es "geht" also überhaupt erst, wenn sie geordnet sind. Da hast du in deinem Fall Glück wohl gehabt.

Unregistrierter

comparor schrieb:

Eine Funktion, die nur die Referenzen oder Indizes speichert, muss man sich dann wahrscheinlich, wie out es gemacht hat, selber schreiben. Die Objekte sind nämlich nicht so einfach zu kopieren wie im obigen Beispiel.

Für das Speichern ist in deinem Beispiel nicht die Funktion, sondern der back_insert_iterator zuständig. Du brauchst also nur ihn zu ändern:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60	#include <iostream> #include <algorithm> #include <vector> #include <iterator> // -- 15 neue Zeilen ----------------------------------------------------------- template <typename T> struct pointer_traits; template <typename T> struct pointer_traits<T> { typedef T element_type; }; template <typename C, template<class> class Inserter> struct pointer_insert_iterator : Inserter<C> { pointer_insert_iterator(C& c) : Inserter<C>(c) {} pointer_insert_iterator& operator= (typename pointer_traits<typename C::value_type>::element_type& value) { static_cast<Inserter<C>&>(this) = &value; return this; } pointer_insert_iterator& operator() { return this; } pointer_insert_iterator& operator++() { return this; } pointer_insert_iterator operator++(int) { return this; } }; template <typename C> pointer_insert_iterator<C, std::back_insert_iterator> pointer_back_inserter(C& c) { return pointer_insert_iterator<C, std::back_insert_iterator>(c); } // ----------------------------------------------------------------------------- using namespace std; // -- 2 Änderungen-------------------------------------------------------------- struct T { int i; T(int i) : i(i) {} bool operator==(const T& t) const {return i==t.i;} }; bool operator!=(const T& t1, const T& t2) { return !(t1.operator==(t2)); } int main() { vector<T> v1; vector<T> v2; for(int i=0;i<40;++i) { v2.push_back(i); if(i&1) v1.push_back(i); } vector<T *> out; // (1) Pointer anstatt Werte std::set_difference(v2.begin(),v2.end(), v1.begin(),v1.end(), pointer_back_inserter(out), // (2) mein Iterator, nicht std::back_iterator std::not_equal_to<T>()); for(size_t i=0;i<out.size();++i) cout << out[i]->i << endl; }

knivil Mitglied 17:36:25 20.08.2012 Titel:

Zitat:

Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen

Mein aktuelles Beispiel: VS 2010 schafft es nicht bei std::sort aus dem Iterator heraus die Parameter des Vergleichsoperators abzuleiten.

Unregistrierter

Danke registrarius :live:

!

Ich muss mich wirklich noch tiefer einarbeiten - auf diese Lösung wäre ich nicht so schnell gekommen.

@kk: Ich bezog mich darauf, dass out in seinem Code immer den vector von Anfang an durchsucht hat - mein Ansatz wäre gewesen, immer den letzten gültigen Iterator zu speichern und ab diesem zu suchen.
Mit der kürzeren Schreibweise beim back_inserter hast du natürlich Recht.

Auch allen anderen natürlich Danke.