ringliste -> designfrage

volkard

also nach außen doch nur eine queue. nur innendrin ein ring.

struct NodeBase{
  NodeBase* prev;
  NodeBase* pred;
};
struct Node:public NodeBase{
  double data;
  Node(double const& d)
  :data(d)
  {
  }
};
class Queue{
  NodeBase anchor;
  public:
  Queue(){
    anchor->prev=&anchor;
    anchor->pred=&anchor;
    //ab jetzt ist der ring geschlossen und wird es immer bleiben. 
  }
};

manchmal mit static_cast aus dem NodeBase* den gesuchten Node* machen. ansonsten geht dieser ansatz sehr schön auf, push_back, push_front und die beiden pops gehen ohne if, denn es gibt niemals den leeren ring. das konzept ist erprobt.

unskilled

danke

volkard schrieb:

also nach außen doch nur eine queue. nur innendrin ein ring.

ne - nach außen nich nur eine queue - aber möchte auch die möglichkeit haben, das ganze einmal von vorn bis hinten auszugeben...
oder meinst du, dass das dann der falsche weg wäre?

bb

volkard

Iterator begin() {return anchor->pred;}
Iterator end() {return &anchor};
RIterator rbegin() {return anchor->prev;}
RIterator rend() {return &anchor};

oder sowas. du kannst da prima durchlaufen.

freaky

volkard kann es sein das du die letzte Zeit ein wenig Java gecodet hast ? Ich frage nur wegen deinem Codestil.

Jester

volkard schrieb:

Dravere schrieb:

Mach end zu einem Zeiger und initialisiere ihn mit 0.

bei einigen ringen kann man das vermeiden und vermeidet damit böse teure fallunterscheidungen. mit ein wenig geschick sogar alle.

Wir doch Zeit, dass endlich mal jemand den Listenartikel zu Ende schreibt, damit sich endlich die Kunde in der Welt verbreitet, wie man eine Liste implementieren sollte.

unskilled

iteratoren

so meinte ich das ja auch ^^

allerdings hab ich noch ein wenig über deine bemerkung nachgedacht und dann ist mir eingefallen, dass ichs doch net so machen kann - nachdem mir bewusst geworden ist, wie du es gemeint hattest ^^

naja - werd ich wo doch die "übliche" struktur nehmen - weils so doch alles ne so recht klappt - hab iwie nur an die hälfte gedacht - und die andere nich nur nicht berücksichtigt, sondern iwo nen denkfehler gemacht gehabt ^^

auf jeden fall danke

volkard

unskilled schrieb:

iteratoren

so meinte ich das ja auch ^^
allerdings hab ich noch ein wenig über deine bemerkung nachgedacht und dann ist mir eingefallen, dass ichs doch net so machen kann - nachdem mir bewusst geworden ist, wie du es gemeint hattest ^^
naja - werd ich wo doch die "übliche" struktur nehmen - weils so doch alles ne so recht klappt - hab iwie nur an die hälfte gedacht - und die andere nich nur nicht berücksichtigt, sondern iwo nen denkfehler gemacht gehabt ^^
auf jeden fall danke

oder sag, was nicht klappt. vielleicht kenne ich ja eine lösung, um doch die genannten vorteile einheimsen zu können.

unskilled

hmm... wo fang ich am besten an.. ich glaub, ich muss ziemlich weit ausholen:

naja - also die aufgabe ist in etwa so:

es ist ein netzwerk gegeben - die switchs sind dabei die ringliste:

switch1 <---> switch2
<--> switch 3 <-->

nat. variabel viele...

dann hat jeder switch wiederrum ganz viele user (allerdings hier als doppelt verkettete liste zu sehen - und so ist es auch zu sehen: jeder pc hat 2 netzwerkkarten - mir fällt der name der netzwerk-struktur gerad nich ein - bei wikipedia steht auch nur "Linie" da, was aber eher die Form beschreiben soll ^^)...

und meine aufgabe ist es, dies zu implementieren und dann einen algo zu schreiben, der so etwas wie nen tracert emuliert (eine liste der ips wiedergibt, die die verbindung durchläuft) - ist ja alles kein problem, die fkt würde wahrscheinlich so in etwa aussehen:

std::vector<my::IPv4> Tracert(const my::cycle_list<my::IPv4> &list, const my::IPv4 &src, const my::IPv4 &dest)
{
  my::cycle_list<my::IPv4>::const_iterator my_switch = ...; //zugehörigen switch aus liste suchen (gleiches subnetz, also über die ip)

  list<my::IPv4> &src_subnet = ...; //dann src aus der liste im switch suchen
  //liste nach unten durchgehen. gefunden? wenn ja, dann sind wir im prinzip fertig: vector füllen + return

  for(my::cycle_list<my::IPv4>::const_iterator i(++my_switch--), e(my_switch); i != e; ++i)
  {
    //gucken, ob src im jeweiligen subnet liegt - wenn ja, dann ips dazwischen in den vector schreiben und fertig...
  }

//wenn nix gefunden wurde:
  return std::vector<my::IPv4>(); //leerer vector
}

Das hier hab ich ma mithin geschrieben, damit du die Aufgabe bissl besser verstehst - ich hab nämlich den Verdacht, schon wieder iwas vergessen zu haben

Und außerdem hatte ich gehofft, dass du mir sagen würdest, wie du in Zeile 8 das i initialisieren würdest (beim nächsten switch anfangen - aber dabei sollte switch danach noch immer auf den richtigen switch zeigen - is eigtl net so wichtig, aber ich fänds komisch ^^)

Könnte max. noch über std::advance gehen - allerdings is das wahrscheinlich au nich so toll?!

Allerdings ist die for-schleife auch das Problem, wieso es mit dem end nicht geht...
Und außerdem eben auch die Logik - die Switchs kommen genau so nacheinander wie auch der 2. und 3. - also kann da auch kein dummy-element dazwischen sein?! ^^

bb

volkard

oh, naja, das hat dann recht wenig mit dem zu tun, was ich sagte.

wenn du diesen ring aufbrichst und einen pseudoknoten reinmachst, entfernst du dich zu weit vom ring-geschehen, fürchte ich. wenn von einem der clients ein paket in den ring reinläuft, dann soll es ja von da aus rundherum und irgendwie magisch den pseudoknoten überspringen.

ich probiere mal was ohne pseudoknoten.
die schleife ist bei so einem echten ring immer ein wenig doof, weil anfang und ende die selben sind.

deswegen nicht

for(Rechner* i=ring.start;i!=ring.start;i=i->rechts)
  tuwas(i);

sondern

if(Rechner* i=ring.start)
  do{
    tuwas(i);
    i=i->rechts;
  }while(i!=ring.start);
//mist, auch falsch.

das würde dann aber nicht mehr erlauben, daß die Rechner* dann iterator genannt werden, weil sie sich nicht mehr wie iteratoren anfühlen (eben nicht in mit der normalen for-schleife gehen).

außerdem ist fraglich, ob man dafür überhaupt eine datenstruktur macht, oder ob man die rechner per hand verkettet.

kannst natürlich auch iteratoren dafür basteln, die müßten dann zum beispiel sowas machen

Iterator(Rechner* start)
{
  myStart=start;
  myPos=start;
}
Rechner& operator*()
{
  return *myPos;
}
Iterator& operator++()
{
  myPos=myPos->rechterNachbar;
  if(myPos==myStart)
    myPos=0;
}
Iterator ring::begin()
{
  return Iterator(anker);//kein pseudoknoten, sondern anker ist zeiger 
    //auf einen echten
}
Iterator ring::end()
{
  return Iterator(0);
}

jeder pc hat 2 netzwerkkarten - mir fällt der name der netzwerk-struktur gerad nich ein - bei wikipedia steht auch nur "Linie" da, was aber eher die Form beschreiben soll ^^)...

es gibt so was ähnliches unter dem namen "Token Ring"

unskilled

Sieht gut aus, was du da gemacht hast

Allerdings sind dann noch paar Fragen:

Wird so etwas (solche iteratoren) auch in der Praxis so implementiert?
das kommt mir nämlich komisch vor:

cycle_list <int> liste;
liste.push_front (3);
liste.push_front (2);
liste.push_front (1);
iterator i1 = liste.begin(); ++i1; ++i1;
iterator i2 = liste.find (3);
//i1 == i2
++i1;
++i2;
//i1 != i2

ist eben ein wenig unlogisch, wenn man es einfach nur so sieht - und kopieren bzw. Zuweisen wird (dadurch) evtl auch ein wenig unintuitiv...
ich weiß nicht - es gefällt mir irgend wie alles nicht so richtig -.-

aber iteratoren irgendwie komplett weglassen möcht ich auch nicht...
mir würden höchstens noch "normale" iteratoren einfallen - da ich die schleife nie komplett durchgehen muss, würd das ja auch gehen - oder meinst du, dass iteratoren implizieren, dass es ein begin() und end() gibt und man (genau) einmal komplett über den Container iterieren kann?

bb

volkard

unskilled schrieb:

[/cpp]
//i1 == i2
++i1;
++i2;
//i1 != i2
[/cpp]
ist eben ein wenig unlogisch, wenn man es einfach nur so sieht - und kopieren bzw. Zuweisen wird (dadurch) evtl auch ein wenig unintuitiv...
ich weiß nicht - es gefällt mir irgend wie alles nicht so richtig -.-

nee, find liefert einen Iterator zurück, dessen myStart gleich begin() ist.

unskilled schrieb:

mir würden höchstens noch "normale" iteratoren einfallen - da ich die schleife nie komplett durchgehen muss, würd das ja auch gehen - oder meinst du, dass iteratoren implizieren, dass es ein begin() und end() gibt und man (genau) einmal komplett über den Container iterieren kann?

naja, wenn es begin() und end() gibt, müssen die auch wie erwartet funktionieren, sonst gibts bald ungeklärte abstürze. aber wenn du einfach kein end() anbietest, ists auch ok. dann mußt du halt alle schleifen mit solchen iteratoren anders abbrechen, zum beispiel weil die bridge dieses paket schon gesehen hat oder wasauchimmer. da hätte ich kein schlechtes gewissen, glaub ich. doch, der name "iterator" würde mir nicht gefallen.

unskilled

Hmm.. OK - dann biete ich das end() einfach nicht an - begin() brauch ich imho auch nicht wirklich...
Gibt dann halt nur ein iterator find(const_reference val) ...

Und welchen Namen würdest du dafür verwenden? Ich finde iterator passt eigtl noch immer... Hab zwar nur eine Definition gefunden, aber die sagt auch nicht, dass iterator noch bestimmte Eigenschaften hätte, die ich nicht erfüllen werde:

<a href= schrieb:

http://de.wikipedia.org/wiki/Iterator">
Der Begriff Iterator (manchmal auch Cursor) stammt aus dem Bereich der Softwareentwicklung und bezeichnet einen Zeiger, mit dem über die Elemente einer Liste bzw. durch die Elemente einer Menge iteriert werden kann.
Der Iterator steht dabei im Gegensatz zu einem Index oder Schlüssel:

Über einen Iterator kann man direkt auf das zugehörige Element zugreifen ohne die Datenstruktur selber zu kennen. Bei einem Index benötigt man immer Index und Datenstruktur.

Ein Iterator ist nur für genau eine Datenstruktur gültig. Ein Index kann auf andere Datenstrukturen übertragen werden.

Iteratoren lassen sich nicht serialisieren. Sie müssen dazu erst zu einem Index gewandelt werden.

bb

Nexus

unskilled schrieb:

Hmm.. OK - dann biete ich das end() einfach nicht an - begin() brauch ich imho auch nicht wirklich...
Gibt dann halt nur ein iterator find(const_reference val) ...

Nur so zwei Fragen:

Was soll find() zurückgeben, wenn nichts gefunden wurde, und du keinen end() -Iterator zum Vergleichen hast?
Wie willst du die ganze Sequenz einmal durchiterieren? Oder brauchst du diese Funktionalität gar nicht?

Meiner Ansicht nach sind begin() und end() ganz eng mit dem Iteratoren-Konzept verbunden (auch aufgrund der Algorithmen). Aber ich kenne deine Anforderungen an den Container auch zu wenig...

unskilled

find() gibt nen iterator(nullptr) zurück, wenn nix gefunden wird...

dann überlad ich noch den konvertierungsoperator (oder wie auch immer man das nennt ^^) zu bool (bzw void*, weil safebool-idiom) und schon ist das Problem mit dem nichts-findenden find() gelöst

durchiterieren sieht noch ein wenig hässlich aus:

my::cycle_list<my::IPv4>::const_iterator my_switch = find(...);
if (!my_switch) return false;

for(my::cycle_list<my::IPv4>::const_iterator i(++my_switch--), e(my_switch); i != e; ++i)

Vll biet ich noch ne Fkt iterator Next(iterator val) an - dann würde die for-schleife scho ma ne mehr ganz so doof aussehen ^^

for(my::cycle_list<my::IPv4>::const_iterator i( Next(my_switch) ), e(my_switch); i != e; ++i)

werden... Das geht deshalb, weil ich nicht mehr in my_switch suchen muss, weil ich davor schon getestet habe, ob dort der gesuchte knoten liegen könnte oder eher nicht...

bb

ringliste -&gt; designfrage

ringliste -> designfrage