std::set

Hallo,

ich habe 2 kurze fragen zu std::set:

Wird std::set immer nur über insert gefüllt und niemals zu begin gesagt wie groß die menge wird? Also sowas geht nicht oder? myset = new std::set<int>(5000) um speicher für 5000 elemente zu halten?
wie wird eine std::set die auf dem heap angelegt ist gelöscht? Über destructor? oder wird dieser automatisch aufgerufen? also ein eigenes delete [] set sozusagen muss nicht gemacht werden oder?

Danke

Nexus

testo schrieb:

Wird std::set immer nur über insert gefüllt und niemals zu begin gesagt wie groß die menge wird? Also sowas geht nicht oder? myset = new std::set<int>(5000) um speicher für 5000 elemente zu halten?

Nein, das macht bei assoziativen Containern aber auch nicht viel Sinn. Wieso eigentlich new ? Es scheint hier irgendwie Angewohnheit zu sein, selbst Container immer auf dem Heap zu erstellen...

testo schrieb:

wie wird eine std::set die auf dem heap angelegt ist gelöscht? Über destructor? oder wird dieser automatisch aufgerufen? also ein eigenes delete [] set sozusagen muss nicht gemacht werden oder?

Doch, natürlich muss es wieder explizit freigegeben werden. Deshalb sollst du Container im Allgemeinen auch auf dem Stack anlegen. Ausserdem wäre das delete und nicht delete[] .

ok danke.
Noch eine Frage in der Zwischenzeit: wie kann ich denn bei einem folgenden code erzwingen dass ich die differenz zweier mengen (z.B. zweier std::sets) erreiche die aber unterschiedlich groß sind. Und ich will die gesamte std::set hernehmen. Doch ein

it=set_difference (first, first.end(), second, second.end(), v.begin());

geht nicht weil ich keine iteratoren übergebe...

// set_difference example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it=set_difference (first, first+5, second, second+5, v.begin());
                                               // 5 15 25  0  0  0  0  0  0  0

  cout << "difference has " << int(it - v.begin()) << " elements.\n";

  return 0;
}

jencas

Wie wär es mit so etwas wie:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main () 
{
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  set<int> s1(first, first + 5);
  set<int> s2(second, second + 5);

  vector<int> v1, v2;

  set_difference (s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(v1));
  cout << "difference first - second has " << v1.size() << " elements: ";
  copy(v1.begin(), v1.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(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  cout << endl;

}

Live zu erleben unter http://codepad.org/EAYp1IPS

/Ergänzung:
Willst Du alle Werte haben, die nicht in beiden Sets vorkommen, nimmst Du statt der zwei Vektoren halt nur einen.

danke - die idee passt.

Mir ist allerdings nicht klar warum ich das ergebnis nicht in ein std::set schreiben lässt. wohl wegen den iteratoren. aber das muss doch irgendwie gehen...

pumuckl

testo schrieb:

Mir ist allerdings nicht klar warum ich das ergebnis nicht in ein std::set schreiben lässt.

Weils für std::set keinen back_inserter geben kann - es gibt nämlich kein push_back(). Eine Alternative ist std::inserter. Aufruf dann wie folgt:

/* ... */

std::set<int> s3;

set_difference (s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.end()));

oder ich hab ne andere frage:

ich würde gerne die idee mit dem set_difference auf 2 int-heap-arrays anwenden...und das ergebnis in ein int-heap-array kopieren. ginge das?

mit dem folgenden geht das aber net:

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

  vector<int> v1, v2;

  set_difference (s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(v1));
  cout << "difference first - second has " << v1.size() << " elements: ";
  copy(v1.begin(), v1.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(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  cout << endl;

}

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)

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 */

}

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

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

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

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

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