std::set

[LordJaxom]

testo schrieb:

und das ergebnis in ein int-heap-array kopieren. ginge das?

Ja, natürlich!

mit dem folgenden geht das aber net:

Also bei mir tut der Code, was ich erwarten würde. Ich meine, das muss nicht das sein, was Du erwartest, aber da Du uns nicht sagst, WAS Deiner Meinung nach nicht funktioniert.......

(Tipp: guck mal auf die Befüllung von second)

[testo]

ok ich versuchs nochmal:

ich hab vorhin nen vector als output gehabt möchte aber (bitte nicht fragen warum) ein int-heap-array als ergebnis.

natürlich haben int-arrays keine iteratoren (oder doch?) und deswegen geht der untere ansatz nicht.

Mir ist auch nicht klar warum ich die int-arrays in sets umkopieren muss über

set<int> s1(first, first + 6);
  set<int> s2(second, second + 5);

geht das nicht ohne eine Kopie direkt auf der eingabe?

Wie ich alles auf int-arrays umschreibe ist mir nicht ganz klar...

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>

using namespace std;

int main ()
{
  int* first = new int[6];
  first[0] = 5;
  first[1] = 10;
  first[2] = 15;
  first[3] = 20;
  first[4] = 25;
  first[5] = 60;

  int* second = new int[5];
  second[0] = 50;
  second[0] = 40;
  second[0] = 30;
  second[0] = 20;
  second[0] = 10;

  set<int> s1(first, first + 6);
  set<int> s2(second, second + 5);

  int* erg = new int[6];

  set_difference (s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(v1));
  cout << "difference first - second has " << v1.size() << " elements: ";
  copy(erg.begin(), erg.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
/*
  set_difference (s2.begin(), s2.end(), s1.begin(), s1.end(), back_inserter(v2));
  cout << "difference second - first has " << v2.size() << " elements: ";
  copy(erg.begin(), erg.end(), ostream_iterator<int>(cout, " "));
  cout << endl;*/

}

[LordJaxom]

testo schrieb:

natürlich haben int-arrays keine iteratoren (oder doch?)

Doch, Du benutzt sie bereits:

set<int> s1(first, first + 6);
  set<int> s2(second, second + 5);

Mir ist auch nicht klar warum ich die int-arrays in sets umkopieren muss

Warum meinst Du denn, das zu müssen?

EDIT:
Das einzige, was set_difference verlangt, ist, dass beide Sequenzen aufsteigend sortiert sind. Das kannst Du auch mit stdd::sort() direkt auf dem Array (wie oben) erreichen.

/* ... */

int main ()
{
  int* first = new int[6];
  first[0] = 5;
  first[1] = 10;
  first[2] = 15;
  first[3] = 20;
  first[4] = 25;
  first[5] = 60;

  int* second = new int[5];
  second[0] = 50;
  second[0] = 40; /* <- *räusper* */
  second[0] = 30;
  second[0] = 20;
  second[0] = 10;

  set<int> s1(first, first + 6);
  set<int> s2(second, second + 5);

  int* erg = new int[6];

  set_difference (first, first + 6, second, second + 5, erg);

  /* Rest bitte analog :D */

}

[testo]

ja danke....aber mit dem jetzigen ansatz funktioniert mein set_difference net...erg == first ?

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>

using namespace std;

int main ()
{
int* first = new int[6];
  first[0] = 5;
  first[1] = 10;
  first[2] = 15;
  first[3] = 20;
  first[4] = 25;
  first[5] = 60;

  int* second = new int[5];
  second[0] = 50;
  second[1] = 40; /* <- *räusper* */
  second[2] = 30;
  second[3] = 20;
  second[4] = 10;

  int* erg = new int[6];

  set_difference (first, first + 6, second, second + 5, erg); 

  cout << "erg: ";
  for( int i = 0; i < 6; i++)
        cout << erg[i] << " ";
  cout << endl;
}

[testo]

ah shit....die sortierung hat gefehlt....

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>

using namespace std;

int main ()
{
int* first = new int[6];
  first[0] = 5;
  first[1] = 10;
  first[2] = 15;
  first[3] = 20;
  first[4] = 25;
  first[5] = 60;

  int* second = new int[5];
  second[0] = 50;
  second[1] = 40; /* <- *räusper* */
  second[2] = 30;
  second[3] = 20;
  second[4] = 10;

  sort(second, second + 5);

  int* erg = new int[6];

  set_difference (first, first + 6, second, second + 5, erg); 

  cout << "erg: ";
  for( int i = 0; i < 6; i++)
        cout << erg[i] << " ";
  cout << endl;
}

[LordJaxom]

Siehe mein EDIT im letzten Beitrag

[testo]

was wäre denn eine möglichkeit wenn man nicht weiß welche der mengen größer ist...also die differenz unabhängig von der unterschiedlichen länge der mengen zu berechnen. Das ist ja jetzt alles hard-codiert...

[Dravere]

LordJaxom schrieb:

Siehe mein EDIT im letzten Beitrag

In deinem Code wird aber immer nocht std::set<int> verwendet, satt std::sort

Im übrigen wäre ich vorsichtig mit der Aussage, dass ein Heaparray auch Iteratoren hat. Grundsätzlich erfüllen einfach die Zeiger eines Arrays das Konzept des Random Access Iterator.

testo schrieb:

was wäre denn eine möglichkeit wenn man nicht weiß welche der mengen größer ist...also die differenz unabhängig von der unterschiedlichen länge der mengen zu berechnen. Das ist ja jetzt alles hard-codiert...

Du musst bei rohen C Arrays immer irgendwie die Grösse mitführen, anders geht es nicht. Deshalb verwendet man in C++ meistens gleich die STL Container.

Übrigens, es empfiehlt sich auch auf den Rückgabewert von set_difference zu acht, vor allem wenn du mit C Arrays herumspielst. Sonst gibst du am Ende womöglich noch zu viele Ergebnisse aus

Grüssli

[testo]

ginge denn sowas: also ohne zwischenkopie, d.h ich schaue first an und schreibe aber auch gleich in first rein....oder passiert dann was unschönes

set_difference (first, first + 6, second, second + 5, first);

[testo]

ich frage deshalb weil ich z.B. in einer schleife eine differenz von 100 int-arrays erreichen möchte und nicht in jeder iteration das erg-array neu aufsetzen will und das alte löschen. bzw. ich will nix rumkopieren...

[Dravere]

testo schrieb:

ginge denn sowas: also ohne zwischenkopie, d.h ich schaue first an und schreibe aber auch gleich in first rein....oder passiert dann was unschönes

Wenn du garantieren kannst, dass der Speicher hinter first gross genug ist, dann geht das. Sobald du über die Speichergrenzen schreibst, gibt es undefiniertes Verhalten.

Grüssli

[LordJaxom]

Dravere schrieb:

LordJaxom schrieb:

Siehe mein EDIT im letzten Beitrag

In deinem Code wird aber immer nocht std::set<int> verwendet, satt std::sort

Deshalb auch: Siehe mein EDIT, nicht siehe mein CODE
(Davon ab sind s1 und s2 nur stehengeblieben, sie werden nicht verwendet)

Im übrigen wäre ich vorsichtig mit der Aussage, dass ein Heaparray auch Iteratoren hat. Grundsätzlich erfüllen einfach die Zeiger eines Arrays das Konzept des Random Access Iterator.

Man kann also beliebige Punkte in Arrays durch etwas beschreiben, was sich wie ein RndIt verhält, ok?

Du musst bei rohen C Arrays immer irgendwie die Grösse mitführen, anders geht es nicht. Deshalb verwendet man in C++ meistens gleich die STL Container.

Bei *echten* Arrays funktioniert sizeof(array)/sizeof(*array) und ist auch ein etabliertes Konzept.

[Werner Salomon]

testo schrieb:

ginge denn sowas: also ohne zwischenkopie, d.h ich schaue first an und schreibe aber auch gleich in first rein....oder passiert dann was unschönes

set_difference (first, first + 6, second, second + 5, first);

Nein - laut Standard ist das nicht zulässig. Dort heißt es:

Requires: The resulting range shall not overlap with either of the original ranges.

Was ist hier mit:

#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>

using namespace std;

int main ()
{
    int first[] = { 5, 10, 15, 20, 25, 60 };
    int* firstEnd = first + sizeof(first)/sizeof(*first);
    int second[] = { 50, 40, 30, 20, 10 };
    int* secondEnd = second + sizeof(second)/sizeof(*second);

    sort( second, secondEnd );  // beide Mengen müsen sortiert sein

    set< int > erg;
    set_difference (first, firstEnd, second, secondEnd, inserter( erg, erg.begin() ));

    cout << "erg: ";
    for( set< int >::iterator i = erg.begin(); i != erg.end(); ++i)
        cout << *i << " ";
    cout << endl;
    return 0;
}

Gruß
Werner

[testo]

Nein - laut Standard ist das nicht zulässig

hmm...wie sollte dann eine schleife für unbeschränkte differenzen von mehreren arrays aussehen...

Und bekomme ihc irgendwie dabei heraus wie lang das ergebnis ist? ANgenommen ich initialisiere das ausgangsarray genügend groß und operiere nur auf einem Teil. Kann ich über set-difference irgendwie herausfinden wie groß mein array am ende ist?

[Dravere]

LordJaxom schrieb:

Deshalb auch: Siehe mein EDIT, nicht siehe mein CODE
(Davon ab sind s1 und s2 nur stehengeblieben, sie werden nicht verwendet)

Jo, aber der Code ist falsch

LordJaxom schrieb:

Man kann also beliebige Punkte in Arrays durch etwas beschreiben, was sich wie ein RndIt verhält, ok?

Hmmmm, Punkte in Arrays?
Mir ging es ja nur darum, dass niemand auf so eine Idee kommt:

int arr[4] = { /* .. */ };
std::sort(arr.begin(), arr.end());

LordJaxom schrieb:

Bei *echten* Arrays funktioniert sizeof(array)/sizeof(*array) und ist auch ein etabliertes Konzept.

Nur sind *echte* Arrays extrem flüchtig. Einmal an eine Funktion übergeben, welche kein Funktionstemplate darstellt, und schon ist das Array weg und man hat nur noch einen Zeiger.

Werner Salomon schrieb:

Nein - laut Standard ist das nicht zulässig. Dort heißt es:

Requires: The resulting range shall not overlap with either of the original ranges.

Hmm, tatsächlich. Aber wieso? Leuchtet mir grad nicht so ein.
Edit: Erklärung ist überflüssig. Ist mir grad klar geworden

Grüssli

[Wackeldackel]

Ich finde das eine komische Sache, da das Kopieren eines int-Werts dem eines Zeigers geschwindigkeitstechnisch nicht unterlegen sein sollte
Deshalb verzichte auf den ganzen Array-Firlefanz und verwende std::vector<int>

[Werner Salomon]

testo schrieb:

Nein - laut Standard ist das nicht zulässig

hmm...wie sollte dann eine schleife für unbeschränkte differenzen von mehreren arrays aussehen...

so wie im Code oben - das eine hat mit dem anderen nichts zu tun

testo schrieb:

Und bekomme ihc irgendwie dabei heraus wie lang das ergebnis ist? ANgenommen ich initialisiere das ausgangsarray genügend groß und operiere nur auf einem Teil. Kann ich über set-difference irgendwie herausfinden wie groß mein array am ende ist?

Verabschiede Dich doch endlich von diesem leidigen

new int[..]

benutze statt dessen std::vector<> oder die anderen Container, die kümmern sich dann schon um den Speicher. Mit einem vector sähe mein Beispiel so aus:

vector< int > erg;
    set_difference (first, firstEnd, second, secondEnd, back_inserter( erg ));

wie u.a. pumuckl es auch schon vorgeschlagen hat. Und da ist auch keine Größe fest vorgegeben.

Gruß
Werner

[Nexus]

Ich mag die typsichere Grössenfunktion für echte Arrays trotzdem:

template <typename T, size_t Size>
size_t ArraySize(T (&Array)[Size])
{
    return Size;
}

[testo]

ja...mir ist schon klar dass ich vector benutzen könnte.

Im Moment habe ich einen fertigen code vor mir der richtig tut und komplett auf int-arrays arbeitet. Und ich will nur eine Methode umschreiben weil ich glaube da performance rausholen zu können. Und dazu will set_difference bzw. set_union.

Und deswegen frag ich die ganze zeit nach der int-variante

[testo]

also ich komm nicht drauf....

ich hab ein 2D array welches lauter 1D arrays aus ints trägt. Aus allen diesen 1D arrays will ich ein set_difference oder set_union machen.
Dazu muss ich dcoh in jeder Iteration mindestens eine array-kopie machen weil ja nicht der speicher als input und output übergeben werden wie werner geschrieben hat....hat jemand eine idee?