3. was braucht ein container, um ein containr zu sein?

was braucht ein container, um ein containr zu sein?

  • O

    SideWinder schrieb:

    BTW: Der Zugriff auf vector ist verständlicherweise lansgamer da der Speicher nunmal nicht am Prorgammstack liegt sondern am Heap.

    Nachtrag: Zudem ist ein vector am Beginn (je nach Allokator-Implementation natürlich) nur 0 Elemente groß. Das heißt, dass für jeden insert ein neues Array erstellt werden muss, oder?

    MfG SideWinder

    vector hat am anfang eine größe von 20 oder so.
    ist auf jedenfall nicht 0.
    wenn du dann 20 elemente drin hast, wird der vector dann auf 40 erweitert.
    desweiteren ist der zugriff auf speicher der auf dem heap liegt genauso schnell wie der zugriff auf speicher, der aufm stack liegt, nur das allokieren des speichers ist langsam.

    0
  • S

    Ja bei dieser vector-Implementation, der Standard schreibt aber keine 20 Elemente vor. Und sagen wir du willst 10000 Objekte einfügen, dann musst du 500 Mal neu Speicher reservieren. Also wenn das nicht langsamer ist als einmal 10000...

    MfG SideWinder

    0
  • J

    Wieso 500 mal? Normalerweise wird der Speicher, wenn er voll ist verdoppelt oder zumindest mal 1,5 genommen. Dadurch wird auch bei großen Elementmengen nicht so oft neu alloziiert. Und genau dafür gibt es ja reserve. Wenn ich schon weiß, daß ich jetzt ein paar Tausend Elemente brauche, dann alloziiere ich auch für diese den Platz.

    MfG Jester

    0
  • O

    SideWinder schrieb:

    Ja bei dieser vector-Implementation, der Standard schreibt aber keine 20 Elemente vor. Und sagen wir du willst 10000 Objekte einfügen, dann musst du 500 Mal neu Speicher reservieren. Also wenn das nicht langsamer ist als einmal 10000...

    MfG SideWinder

    gehen wir mal bei der vector implementation von deinen 0 werten aus...
    dann verhällt sich der vector so(die zahlen stehen für die anzahl der elemente, ab denen der vector neu allokiert)
    1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384.
    es wird also bei 10k elementen 15 mal neu allokiert,also ist das nicht bei "jedem" insert, wie du es behauptet hast.

    0
  • ?

    Naja, für sowas gibts ja genau nen Konstruktor. Was mich bei vector schon eher stört, ist, dass es nicht gerade ratsam ist, Zeiger auf die Elemente zu haben.
    Ich mag vector halt einfach nicht. Ohne Begründung. 🤡

    0
  • J

    Nö, sonst wäre ja anfügen an den Vektor nicht mehr O(1). Denn es müßten immer die n vorherigen Elemente kopiert werden => O(n).

    Genau genommen ist anfügen nicht O(1), sondern nur O(1) amortisiert, das heißt:

    Einfügen geht die meiste Zeit in O(1), nur alle n-mal einfügen zahlen wir O(n) und damit haben wir im Durchschnitt O(1).

    MfG Jester

    0
  • T

    Optimizer schrieb:

    Was mich bei vector schon eher stört, ist, dass es nicht gerade ratsam ist, Zeiger auf die Elemente zu haben.

    Das ist aber erforderlich, sonst ist es kein container 😉
    http://www.gotw.ca/publications/mill09.htm

    0
  • O

    ich bin ja grad an meiner implementation der "multimap" dran, und da kam bei mir das problem der zuordbarkeit der Elemenete auf:
    wenn jemand ein objekt in eine multimap einfügt, dann hat er ja weitestgehend ein ziel dabei,bei einer multimap-so meine auffassung-kommt es dem programmierer nicht mehr unbedingt auf die zuordbarkeit an, das bedeuted, wenn er zufälligerweise unbedingt einen zeiger auf ein solches objekt braucht, hat er sogut wie keine möglichkeit, rauszubekommen, welches objekt nun das gesuchte ist.

    Klar gibt es die möglichkeit,den iterator abzuspeichern,der von der insert funktion zurückgegeben wird, aber soweit ich weis, kann sich ja die position des objekts innerhalb der map verändern-ausser der iterator stellt einfach nur einen pointer auf das objekt da,was aber auch nicht sein darf-aufjedenfall kam mir dann eine fixe idee, die ich schon zu nem anderen thema in letzter zeit hatte, und die ich jetzt mal versuchen wollte sie als containerform(wenn mans noch container nennen kann) zu schreiben.
    Ich brauch halt nur eure Meinung, ob es das wirklich bringt...

    also, in den container soll man wie gewohnt, mithilfe von schlüsseln und werten neue Einträge einfügen können.
    Die idee ist nun, es zu ermöglichen, verschiedene container zu einem großen zu verknüpfen, sodass man im einzelcontainer zwar noch die vollkommene kontrolle über die einzelnen elemente hat,inklusive einer halbwegs vernünftigen zuordbarkeit,man aber auch im großen verknüpften container die möglichkeit hat, sachen mit dem gesamten zu machen.

    Anwendbarkeit: zb, wenn man das Objekt "KaufhausArtikel" verwalten will,kann man einerseits gruppen bilden, man hat aber auch die möglichkeit, einfach alles sortiert anzuzeigen.
    generell könnte man sowas sehr schön in Datenbanken benutzen.
    Andere Anwendung wär zb ein Grafikprogramm, welches "zusammengesetzte" Objekte unterstützt(wer warzone2100 kennt weis was ich in etwa meine).

    Was haltet ihr denn von der idee?Könnte man dies noch als Container bezeichnen?

    0
  • T

    Hmmm, in diesem Fall würde ich mehrere Container vorschlagen: einen Container, der mehrere vereinigt (das multiset/multimap) und einen anderen, der wie eine normale map funktioniert. Letzterer leitet dann alle Operationen a) an eine map und b) an den großen Container weiter, so dass die beiden immer synchron gehalten werden.

    0
  • O

    tag schrieb:

    Hmmm, in diesem Fall würde ich mehrere Container vorschlagen: einen Container, der mehrere vereinigt (das multiset/multimap) und einen anderen, der wie eine normale map funktioniert. Letzterer leitet dann alle Operationen a) an eine map und b) an den großen Container weiter, so dass die beiden immer synchron gehalten werden.

    so in etwa solls funktionieren,nur dass der große container, kein verbund, aus maps/multimaps sein darf, weil sonst ein allgemeines sortieren der Objekte nicht mehr möglich ist.Vorallem dürfen die objekte der einzelnen container nicht einfach in den großen Kopiert werden, da sonst interne änderungen der objekte nicht weitergeleitet werden könnten, also müssten sich die container drauf beschränken, zeiger auf mit new erstellten Objekten zu verwalten.

    die frage ist, ob man nur folgendes ermöglichen soll:
    a,b,c,d,e container:
    a+b sind teil von c

    sondern auch
    a+b sind teil von c;c+d sind teil e

    bei letzterem kann man natürlich eine viel feinere abstufung machen, man kann richtige bäume erstellen, das hat aber den nachteil, dass das einfügen von Objekten immer langsamer wird, je verzweigter der Baum ist.

    0
  • T

    Wohl wahr... Wenn du den übergreifenden Container allerdings nur Schrittweise durchlaufen willst, dann könntest du auch mit einem angepassten Iterator auskommen: Der Iterator merkt sich die Positionen in allen Untercontainern und entscheidet dann im operator++, welcher Eintrag aus allen Containern als nächstes dran kommt. Das geht aber auch nur, wenn das Sortierkriterium bei allen gleich ist.
    Wenn sich das Sortierkriterium ändert, wirst du IMHO sowieso nicht an einem neuen Container vorbei kommen...
    Auf jeden Fall solltest du dann aber iteratoren o.Ä. im übergeordneten Container speichern

    0
  • O

    ich fang einfach mal an...
    wird ne interessante erfahrung 😉

    0
Anmelden zum Antworten