Wie definiere ich Mengen in c++

Kann mir jemand sagen wie ich in c++ Mengen definiere?
Nehmen wir mal an Menge 1 = n ist element der Natürlichen Zahlen wobei 0<n<11 also {1,2,3,4,5,6,7,8,9,10}
Menge 2 = {7,8,9,10,11,12,13,14}
muss ich da jedem Element Jeder Menge eine Variable zuweisen?
Also für Menge 1 dann
int a,b,c,d,e,f,g,h,i,j;(also 10 Variablen)
UND WIE FASS ICH DAS DANN ZU EINER MENGE ZUSAMMEN
Dass wär mal das wichtigste wenn mir da jemand helfen kann würde ich mich schon sehr freuen.

Für den Anfang reicht es mir bei den natürlichen Zahlen zu bleiben.
Und wenn ich mit Mengen rechnen will deren größe man vorher im Programm definiert hat z.B. 0 < n < 99.000.000, oder sogar zwischen 0 und unendlich, ist das nich ein bisschen viel verlangt unendlich viele Variabeln zu definieren?

Oder geht das irgendwie mit ner for schleife? z.B.
int a
for(a = 1; a < 11; a++) (für menge 1)
und wie fass ich das dann zu ner menge zusammen

oder wenn die mengengröße selbst definieren will, dan eben
{
int a;
int b;
cout <<" Geben sie die letzte Zahl ein die, diese Menge bestehen aus den Natürlichen Zahlen als Element nicht mehr enthalten soll\n";
cin >> b;
for (a = 1; a < b; a++)

Wenns zu kompliziert wird lohnt sich die Beantwortung der Fragen nicht, da ich noch ein absoluter beginner bin, was Programmieren angeht.
Kennt jemand ne Adresse wo es Quellcods gibt für so selbstgeschriebene Mengenrechnungsprogramme.

vielen dank für die Hilfe

Jester

Sowas wie eine mathematische Menge bietet Dir C++ per se nicht. Das kannst Du entweder selber schreiben, oder Dir für den Anfang mit std::set behelfen. Damit kannst Du allerdings keine unendlichen Mengen darstellen.

MfG Jester

Korbinian

man könnte unendliche mengen anhandl regeln definieren, die man entweder hardcoded oder irgendwie modular hält. letzeres wär mal eine nette herausforderung

Jester

Wieso? Ein Funktionsobjekt, das mit true/false antwortet. Das übergibt man der Menge per Konstruktor. Vereinigung, Differenz etc. ließe sich dann rekursiv über gewisse Regeln erledigen.

Quasi ein Konstruktor, der zwei Mengen entgegennimmt und istElement ausgibt, wenn beide sagen istElement würde dann den Schnitt darstellen.

Allerdings ist nicht sicher, ob das so sinnvoll ist. Bei endlichen Mengen würde man vielleicht gerne drüber iterieren... bei unendlichen macht sowas keinen Sinn etc.

MfG Jester

volkard

Grimblegrumbl schrieb:

Kann mir jemand sagen wie ich in c++ Mengen definiere?
Nehmen wir mal an Menge 1 = n ist element der Natürlichen Zahlen wobei 0<n<11 also {1,2,3,4,5,6,7,8,9,10}
Menge 2 = {7,8,9,10,11,12,13,14}
muss ich da jedem Element Jeder Menge eine Variable zuweisen?

nein. es gibt schon typen, die sich für mengen eignen. allem voran std::set.
manche typen haben sogar vereinigung und schnitt als fertige funktionen dabei.
normalerweise sind die mengen als bäume implementiert, damit man schnell einfügen und löschen kann.
mengen sich selber zu schreiben, und zwar als verkettete liste, sind ein beliebtes übungsbeispiel für die grundlagenvorlesung über programmieren.

Also für Menge 1 dann
int a,b,c,d,e,f,g,h,i,j;(also 10 Variablen)
UND WIE FASS ICH DAS DANN ZU EINER MENGE ZUSAMMEN
Dass wär mal das wichtigste wenn mir da jemand helfen kann würde ich mich schon sehr freuen.
Für den Anfang reicht es mir bei den natürlichen Zahlen zu bleiben.

das ist gut. für mengen über natürlichen zahlen hat uns der herr nämlich bitfelder geschent. die mathematiker sagen glaub ich "characteristischer string" statt "bitfeld".
also
m1={1,2,3,4,5,6,7,8,9,10}
m2={7,8,9,10,11,12,13,14}
dann würde ich in c++ schreiben:
int m1=0x7fe;//kann falsch sein, habs nur im kopf gerechnet
int m2=7f40;
und die schnittmenge
int s=m1&m2;
und die vereinigungsmenge
int v=m1|m2;
die geschwindigkeit ist kaum zu schlagen, denn 32-bittige bitfelder kann der prozessor in einem takt verknüpfen. und größere bastelt man vielleicht am besten aus 32-bittigen zusammen.

wenn es irgendwie um performanz geht, sollte man bitfelder benutzen. ich hab mal ein wenig mit begrifflichen wissenssystemen rumgemacht, da mußte sehr viel geschnitten und vereinigt werden. und die mengen waren endlich und sogar klein. beim laden wurden die namen der möglichen elemente eh gelesen, da hat schon gar keiner mehr drüber nachgedacht, daß wir statt der namen deren arrayindizes nahmen (die elemente selbst gabs eh nicht).

Und wenn ich mit Mengen rechnen will deren größe man vorher im Programm definiert hat z.B. 0 < n < 99.000.000,

ist für bitfelder noch einfach zu handhaben. 99.000.000 bits wäre bloß 12.375.000 bytes. es gibt ne fertige klasse namens bitfield oder so, die kann aber nur größen, die zur compilezeit schon bekannt sind (auch 99.000.000). und es gibt vector<bool>, der kann auch andere größen. und sich selber bitfelder zu bauen, geht zur not auch.

oder sogar zwischen 0 und unendlich, ist das nich ein bisschen viel verlangt unendlich viele Variabeln zu definieren?

jesters mengenbeschreibende funktionen sind für unendliche mengen wohl der köngsweg (in c++).

Oder geht das irgendwie mit ner for schleife? z.B.
int a
for(a = 1; a < 11; a++) (für menge 1)
und wie fass ich das dann zu ner menge zusammen

template<typename Grundmenge>
struct Schnitt{
   Menge<Grundmenge> *a;
   Menge<Grundmenge> *b;
   bool hat(Grundmenge const& key){
      return a->hat(key) && b->hat(key);
   }
};
/*ungewöhnlich, nen typen als menge zu sehen, aber ganz korrket, würde ich sagen. das mitschleppen der grundmenge im eigenen mengentyp erlaubt auch 
endlich ne zwanglose komplementbildung. das hat mich in der schule schon 
immer genervt, daß der ganze mengenkram harmonisch ging ohne wissen um die 
grundmenge und wenn der lehrer irgendwann das komplement haben wollte 
fragte ich nach der grundmenge. und die anderen schüler fragten nicht. die 
vermuteten einfach, daß das komplement von {2,5,6,7} wohl {1,3,4,8,9,10} 
sein müsse und bekamen sogar recht.*/

damit würde man jede rechnung verschieben bis auf den finalen punkt am programmende irgendwann, wo bei der ausgabe alles gerechnet wird. nicht gut geeignet für verfahren wie sagen wir mal das berechnen einer transitiven hülle. (ok, die berechnet man auf ner relation, aber vielleicht ist die relation mal ne menge von paaren.)

die version mit ner aufzählung, sagen wie mal die aufzählung sei recht dünn besetzt: (bei dicht besetzer aufzählung nimmt man eh bitfeld)

typedef vector<int> Menge;//mengen seien als sortierte vectoren mit int drin 
   //dargestellt. hat() kostet mit binärer suche O(log(n)), enfügen/löschen 
   //kostet O(n), einfügen/löschen am ende kostet O(1), vereinigung/schnitt
   //kostet O(n)
Menge schnitt(Menge const& a,Menge const& b){
   //ohne was fertiges zu nehmen und mit integers als indizes statt iteratoren
   //damits erstmal leichter nachzuvollziehen ist, was innen passiert
   Menge c;
   int apos=0;
   int bpos=0;
   while(apos<a.size() && bpos<b.size()){
      if(a[apos] < b[bpos])
         c.push_back(a[apos++]);
//<edit>
      else if(a[apos]==b[bpos]){
         c.push_back(a[apos++]);
         bpos++;
      }
//</edit>
      else
         c.push_back(b[bpos++]);
   }
   while(apos<a.size())
      c.push_back(a[apos++]);
   while(bpos<b.size())
      c.push_back(b[apos++]);
   return c;
}

genau wegen dieser funtion wurde die mengendarstellung als sortiertes array gewählt, weil das dann so schnell geht.
natürlich gips noch hundert andere möglichkeiten, mengen darzustellen. afair nicht unerwähnt bleiben dürfen fibonacci heaps. irgend jemand benutze die sehr gern für mengen.

oder wenn die mengengröße selbst definieren will, dan eben
{
int a;
int b;
cout <<" Geben sie die letzte Zahl ein die, diese Menge bestehen aus den Natürlichen Zahlen als Element nicht mehr enthalten soll\n";
cin >> b;
for (a = 1; a < b; a++)

als bitfeld:

Bitfeld erzeugeMengeDerNatürlichenZahlenBis(int obergrenze){
   Bitfield b(obergrenze);
   b.invert();//da normalerweise alle bits auf 0 stehen nach dem erzeugen
   //invert sollte je 32 bits auf einmal umklappen können, also recht schnell sein
   return b;
}

als sortiertes array:

vector<int> erzeugeMengeDerNatürlichenZahlenBis(int obergrenze){
   vector<int> v;
   for(int i=0;i<obergrenze;++i)
      v.push_back(i);
   return v;
}

also funktionalobjekt

template<typename Grundmenge>
struct Inervall{
   Grundmenge untergrenze;
   Grundmenge obergrenze;
   Intervall(Grundmenge const& u,Grundmenge const& o):
   untergrenze(u),
   obergrenze(o):{
   }
   bool hat(Grundmenge const& key){
      return untergrenze<=key && key<=obergrenze;
   }
};
Intervall<int> erzeugeMengeDerNatürlichenZahlenBis(int obergrenze){
   return Intervall<int>(0,obergrenze);
}

Wenns zu kompliziert wird lohnt sich die Beantwortung der Fragen nicht, da ich noch ein absoluter beginner bin, was Programmieren angeht.

dann interessiert es jemand anderen, der sich nur noch nicht zu fragen traute.

Kennt jemand ne Adresse wo es Quellcods gibt für so selbstgeschriebene Mengenrechnungsprogramme.

kenne nix. ich hab irgendwo für das sieb des eratosthenes ein halbfertiges bitfield auf der platte liegen. das würde ich nehmen und ausbauen, wenn ich mal wieder ein bitfielb bräuchte (ich schreibe klassen selten fertig, sondern baue nur das, was ich echt brauche).

fertige klassen für mengen gibts wie gesagt als std::set. die ist ganz ok. falls das jemals nicht schnell genug sein sollte, mußte eh was ganz eigenes bauen, was genau zu deiner anwendung passt. da würde auch keine fertige menge helfen.

volkard

Jester schrieb:

Allerdings ist nicht sicher, ob das so sinnvoll ist. Bei endlichen Mengen würde man vielleicht gerne drüber iterieren... bei unendlichen macht sowas keinen Sinn etc.

falls man über die grundmenge iterieren kann (und das kann man evtl sogar bei allen auf dem rechner darstellbaren typen), dann auch über unsere menge.
fein wäre es, die mengen würden zum iterieren auch nich begin() und end() haben. für int halt MIN_INT und... (nochmal MIN_INT, mist!).
die zusammengesetzen menen könnten auch leicht begin() und end() mitschleppen. begin von a{vereinigt mit}b ist min(a.begin(),b.begin()) usw.

Jester

volkard schrieb:

falls man über die grundmenge iterieren kann (und das kann man evtl sogar bei allen auf dem rechner darstellbaren typen), dann auch über unsere menge.

Jein, ich dachte jetzt an sowas wie die Menge aller geraden Zahlen. Das läßt sich mit obigem Modell wunderbar darstellen, aber nicht iterieren. Dennoch macht die Menge Sinn, wenn man sie zum Beispiel mit der Menge aller Zahlen < 1000 schneiden möchte... Auch die Menge der Primzahlen ist durchaus sinnvoll zu beschreiben.

volkard schrieb:

fein wäre es, die mengen würden zum iterieren auch nich begin() und end() haben. für int halt MIN_INT und... (nochmal MIN_INT, mist!).
die zusammengesetzen menen könnten auch leicht begin() und end() mitschleppen. begin von a{vereinigt mit}b ist min(a.begin(),b.begin()) usw.

Dann setzt Du zusätzlich aber noch eine Ordnung voraus. Das kommt aber darauf an, wie allgemein man die Menge halten möchte.

MfG Jester

Nox

Nur mal so als tipp:
das stichwort lautet enum.
Damit kann man seinen eigenen Datentyp definieren und dabei auch den bereich festlegen......

volkard

jester schrieb:

Jein, ich dachte jetzt an sowas wie die Menge aller geraden Zahlen. Das läßt sich mit obigem Modell wunderbar darstellen, aber nicht iterieren.

nicht?

Grundmenge begin(){
   return findFirstOf(Grundmenge::begin(),Grundmenge::end(),*this);
}

oder so.
sieht nach der default-implementierung für begin() aus.

[quote]
[quote]
fein wäre es, die mengen würden zum iterieren auch noch begin() und end() haben. für int halt MIN_INT und... (nochmal MIN_INT, mist!).
die zusammengesetzen menen könnten auch leicht begin() und end() mitschleppen. begin von a{vereinigt mit}b ist min(a.begin(),b.begin()) usw.

Dann setzt Du zusätzlich aber noch eine Ordnung voraus. Das kommt aber darauf an, wie allgemein man die Menge halten möchte.

ursprünglich nicht. beim iterieren dachte ich noch daran, daß man bei doubles nicht klasse alle abdeckt, wenn man mit ++i weiterläuft. aber die laufreihenfolge is bei mengen ja egal, bis auf ein paar ungültige doubles kann ich auch fein mit ((int64)&i)++ laufen.
und dann braucht man auch keinen op<=, keine ordnung mehr, kein min für die elemente. man braucht nur ne möglichkeit, die binären repräsenationen im rechner zu ordnen. ich schätze, die ist für alle im rechner darstellbaren objekte gegeben.

und wenn's mal nicht klappt, oder irrelevant ist, bietet man eben kein begin()/end() an. kommt ja auch oft genuf vor, daß man nur gucken will, ob ein paar konkrete objekte in ner komplexen menge stecken.

volkard

Nox schrieb:

Nur mal so als tipp:
das stichwort lautet enum.
Damit kann man seinen eigenen Datentyp definieren und dabei auch den bereich festlegen......

echt? glaub ich nicht, daß das was mit mengen zu tun hat.

Nox

Hmm okay er mag constanten nit sonderlich daher -> mein fehler....

Jester

@volkard: Jetzt verstehe ich was Du meinst. Klingt recht interessant (vom Standpunkt eines Informatikers) und recht unnatürlich (vom Standpunkt eines Mathemmatikers). Vielleicht sollte ich mich doch irgendwann mal festlegen...