std::set

[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?

[Werner Salomon]

testo schrieb:

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?

Also, Du hast int-arrays als Input und Output und kannst daran nichts ändern - richtig?!

Dann kopiere doch jedesmal das int-array, welches input und output ist, vorher in einen vector

int sizeOfIntArray = ??;
    int* first = ??;
    vector< int > tmp( arr, arr + sizeOfIntArray  ); // der Input als Kopie
    sort( tmp.begin(), tmp.end() ); // <-- nur wenn Du nicht sicher bist, dass das Array bereits sortiert war
    int* ende = set_difference( tmp.begin(), tmp.end(), second, second + sizeOfSecond, first );
    sizeOfIntArray = ende - first; // Achtung die Länge hat sich jetzt geändert

Gruß
Werner

[LordJaxom]

Dravere schrieb:

Jo, aber der Code ist falsch

Hättest Du noch die Güte, mir zu sagen, inwiefern? Abgesehen natürlich von den bereits angemerkten überflüssigen sets, den angeräusperten falschen Indizes bei der Initialisierung von second und dem ebenfalls bemängelten unsortierten Array second.

Dravere schrieb:

Hmmmm, Punkte in Arrays?

Mir fiel das Wort "Elemente" nicht ein

Dravere schrieb:

Mir ging es ja nur darum, dass niemand auf so eine Idee kommt:

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

Wenn wir schon Haare spalten: Ich sagte nirgends, dass die Iteratoren von Arrays genauso ansprechbar sind wie bei Containern :p

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.

Logisch. Wer diese Informationen beibehält (wie gesagt Funktionstemplate), hat das Problem nicht. Braucht aber auch den sizeof-Hack nicht mehr - wie immer muss man also wissen, was man tut.

Ich nutze bei Konstanten Daten / Objekten sehr häufig Arrays und arbeite direkt mit Algorithmen auf denen, statt sie zuvor in Container zu kopieren. Bin ich noch nicht mit auf die Nase gefallen. Natürlich gebe ich keine Zeiger von diesen Arrays nach aussen.

EDIT @Nexus:
Noch schönder fände (bald: finde :D) ich die konstante typsichere Größenfunktion für Arrays. Wobei ich den Namen anders wählen würde.

template <typename T, size_t Size>  
constexpr size_t countof(T (&)[Size])