stl-container für warteschleife

picocat

folgendes problem, für welche ich einen passenden standard template library-container brauche.

ich möchte eine "warteschleife" implementieren, die den folgenden anforderungen genügen soll

jeder eintrag besteht aus einer zeit-struktur (von mir angelegt) sowie zwei nicht unbedingt eindeutige id's zur identifikation der einträge
die zeit-struktur sieht so aus ungefähr aus:

struct Mytime
{
  int hour,min,sec;
  int day,mon,year;
};

und steht in einer header-datei drin.

eingefügt werden einträge irgendwo in der liste
gelöscht nur am anfang
die einträge sollen nach zeit geordnet werden, sprich z.b.
1. "01.01.2000 00:01", 5, 3 (zeit, id, id)
2. "02.01.2000 12:00", 5, 9
3. ...
neue einträge sollen automatisch einsortiert werden oder notfalls von mir mit hilfe einer passenden funktion, wäre kein problem.
es können auch gleiche uhrzeiten vorhanden sein

ich hatte schon an (multi)map bzw. priority-queue gedacht. aber da habe ich das problem, dass ja für das struct kein passender vergleichsoperator zur verfügung steht. was kann man da machen? etwa von map und priority-queue mir selber einen container ableiten und entsprechend anpassen? oder eine klasse "mytime" schreiben und da operatoren überladen (bei beiden möglichkeiten wüsste ich nicht, wie ich das anstellen sollte)...

hoffe ihr könnt mir helfen, danke

leech

irgendwie weiß ich nicht, wo nun das problem ist...

Lars Hupel schrieb:

# eingefügt werden einträge irgendwo in der liste
# gelöscht nur am anfang
# die einträge sollen nach zeit geordnet werden, sprich z.b.
1. "01.01.2000 00:01", 5, 3 (zeit, id, id)
2. "02.01.2000 12:00", 5, 9
3. ...
neue einträge sollen automatisch einsortiert werden oder notfalls von mir mit hilfe einer passenden funktion, wäre kein problem.
# es können auch gleiche uhrzeiten vorhanden sein

diese sachen soll der STL container können... warum nimmst du dann nicht einfach eine list?

- für dein struct Mytime überlädst du einfach den operator< und kannst dann später auf der list die sort() funktion anwenden...
- am anfang löscht du einträge mittels pop_front()
-die list ist besser als ein vector, da man hier nicht alle elemente verschieben muss, wenn man das erste element löscht... das selbe gilt für das einfügen an beliebiger stelle

volkard

Lars Hupel schrieb:

ich hatte schon an (multi)map bzw. priority-queue gedacht.

priority-queue ist die richtige wahl.

aber da habe ich das problem, dass ja für das struct kein passender vergleichsoperator zur verfügung steht. was kann man da machen?

einen machen, wie bereits vorgeschlagen. nur sollste nicht nach vector abdriften.

etwa von map und priority-queue mir selber einen container ableiten und entsprechend anpassen?

nein. den op< deiner datensrtruktur überladen.

oder eine klasse "mytime" schreiben und da operatoren überladen (bei beiden möglichkeiten wüsste ich nicht, wie ich das anstellen sollte)...

struct Mytime
{
  int hour,min,sec;
  int day,mon,year;
  friend bool operator<(Mytime const& a,Mytime const& b){
    if(a.year<b.year) return true;
    if(a.year>b.year) return false;
    if(a.mon<b.mon) return true;
    if(a.mon>b.mon) return false;
    ...
  }
};

picocat

danke erstmal!

bei der möglichkeit muss ich aber "Mytime" noch zwei Variablen

int id1,id2;

hinzufügen, sonst kann ich ja nur eine zeit sortieren... ich will ja noch die id's verwalten.

volkard

Lars Hupel schrieb:

danke erstmal!

bei der möglichkeit muss ich aber "Mytime" noch zwei Variablen
int id1,id2;
hinzufügen, sonst kann ich ja nur eine zeit sortieren... ich will ja noch die id's verwalten.

jo. oder MyTime so lassen und benutzen

struct MyData
{
private:
   MyTime time;
   int id1;
   int id2;
public:
   friend bool operator<(MyData const& a,MyData const& b){
      if(a.time<b.time) return true;
      if(a.time>b.time) return false;
      if(a.id1<b.id1) return true;
      ...
   }
};

aber warum eigentlich. wolltest du nicht nur nach time sortieren?

struct MyData
{
private:
   MyTime time;
   int id1;
   int id2;
public:
   friend bool operator<(MyData const& a,MyData const& b){
      return a.time<b.time;
   }
};

picocat

ok, danke erstmal.

1. erklär mir aber bitte noch mal schnell, was das "friend" da bedeutet.
2. kann ich auch den operator <= überladen? welchen algorithmus aus <algorithm> zum vergleich nehmen?

volkard

Lars Hupel schrieb:

ok, danke erstmal.
1. erklär mir aber bitte noch mal schnell, was das "friend" da bedeutet.

der op< ist global. er steht außerhalb der klasse. aber er greift auf private members zu, deswegen muss er innerhalb der klasse als friend deklariert werden.
also

struct MyData
{
private:
   MyTime time;
   int id1;
   int id2;
public:
   friend bool operator<(MyData const& a,MyData const& b);
}; 
bool operator<(MyData const& a,MyData const& b){
   return a.time<b.time;
}

jetzt darf ich mir aber erlauben, die definition gleich an die friend-deklaration zu hängen, dann gehts auch und bedeutet das gleiche.

2. kann ich auch den operator <= überladen?

klar.

friend bool operator<=(MyData const& a,MyData const& b);
}; 
bool operator<(MyData const& a,MyData const& b){
   return a.time<=b.time;
}

welchen algorithmus aus <algorithm> zum vergleich nehmen?

verstehe die frage nicht.

otze

Lars Hupel schrieb:

welchen algorithmus aus <algorithm> zum vergleich nehmen?

die priority queue sortiert selber, du musst nur den operator< überladen, das wars. Der rest ist magie

picocat

damit meine ich, dass es solche funktionen wie less und greater gibt. etwa auch lessequal oder so was in der art?

volkard

Lars Hupel schrieb:

damit meine ich, dass es solche funktionen wie less und greater gibt. etwa auch lessequal oder so was in der art?

tut nicht not.
statt lessequal(a,b) kann man auch !less(b,a) schreiben.
also
op< ist für die meisten sachen völlig ausreichen.
wegen
a<b definiert
a>b b<a
a>=b !(b<a)
a<=b !(a>b)
a!=b a>b||a<b
a==b !(a>b||a<b)

aus performancetechnischen gründen benutzen mache leet haxors auch noch den op==. aber mehr als zwei (less und equal) braucht keiner.

picocat

volkard schrieb:

aus performancetechnischen gründen benutzen mache leet haxors auch noch den op==. aber mehr als zwei (less und equal) braucht keiner.

//Edit sorry zuviel zitiert

otze

Lars Hupel schrieb:

volkard schrieb:

aus performancetechnischen gründen benutzen mache leet haxors auch noch den op==. aber mehr als zwei (less und equal) braucht keiner.

a==b !(a>b||a<b)

wenn etwas weder größer noch kleiner als etwas anderes ist, so muss es zwangsläufig gleich sein ;). sind halt im gegensatz zu op== immer 2 operator aufrufe, was normalerweise langsamer sein sollte, als direkt zu testen, ob a==b ist.

picocat

is mir klar, aber wer oder was sind leet haxors?

Green_Ghost

Wie sortiert der priority_queue?
kleinstes Top, Groesstes end? (bei int werten)

Wie benutzt man einen priority_queue?
priority_queue<MyStruct> bla; ???

Danke fuer Tipps und gedanken,
MFG Ghost

picocat

also da wird bei pop() immer das element mit der höchsten priorität gelöscht. wie die elemente intern sortiert sind, ist ja eigentlich wurscht.

aber wie kann man nun auf das 0. element (sprich das welches als nächstes durch pop gelöscht wird) zugreifen container[0]

Ponto

Lars Hupel schrieb:

also da wird bei pop() immer das element mit der höchsten priorität gelöscht. wie die elemente intern sortiert sind, ist ja eigentlich wurscht.

aber wie kann man nun auf das 0. element (sprich das welches als nächstes durch pop gelöscht wird) zugreifen container[0]

top()