was braucht ein container, um ein containr zu sein?

otze

ich hab jetzt nicht den standard da, da stände das ja drin, und bei google war das alles auch nur sehr vage, drum wollte ich mal fragen, was ein container im allgemeinen haben muss,haben darf, und was ein container unbedingt vermeiden sollte, damit er ein container ist.

mir reicht hier ein einfacher link, aber bei google hab ich echt nichts gefunden...

Shade Of Mine

Ein Container muss Elemente eines bestimmten Typs beinhalten können.

Und das war es auch schon.

Sinvoll wäre noch ein Zugriff auf die Elemente
Weiters sind iteratoren auch oft nicht falsch.

dEUs

Muss er nciht Elemente eines beliebigen Typs beinhalten können?

phlox81

dEUs schrieb:

Muss er nciht Elemente eines beliebigen Typs beinhalten können?

Ein Template ist auch nur eine Vorlage, der Kompiler erzeugt daraus eine
konkrete Klasse mit einem bestimmten Typen.

Devil

Shade Of Mine

dEUs schrieb:

Muss er nciht Elemente eines beliebigen Typs beinhalten können?

beliebig wäre:

vec.push_back(3);
vec.push_back("hallo");
vec.push_back(new Foo());
vec.push_back(Bar(7));
...

otze

Shade Of Mine schrieb:

Ein Container muss Elemente eines bestimmten Typs beinhalten können.

Und das war es auch schon.

Sinvoll wäre noch ein Zugriff auf die Elemente
Weiters sind iteratoren auch oft nicht falsch.

war da nich nach der stl noch was mit den constructoren methoden etc, die ein container haben muss?
oder hab ich da was falsches gehört/gelesen?

dEUs

hm ... Aber so wie du es schreibst, hört man nciht raus, dass das ganze eine Templateklasse ist. Und ich dachte eigentlich, dass das eine Eigenschaft von Containern wäre.

Shade Of Mine

otze schrieb:

war da nich nach der stl noch was mit den constructoren methoden etc, die ein container haben muss?

iteratoren werden gebraucht. aber sonst?
vergleich mal zB boost::array mit std::multiset mit std::list - viel gemeinsamkeiten finden sich da nicht...

otze

Shade Of Mine schrieb:

otze schrieb:

war da nich nach der stl noch was mit den constructoren methoden etc, die ein container haben muss?

iteratoren werden gebraucht. aber sonst?
vergleich mal zB boost::array mit std::multiset mit std::list - viel gemeinsamkeiten finden sich da nicht...

list mit multiset zu vergleichen is ja auch hirnrissig, weil das ganz unterschiedliche containertypen sind, im gegensatz zu Vector und list...
haben alle ein clear/swap/begin/end/size/empty usw...
btw haben map und multimap auch diese sachen^^

DrGreenthumb

http://www.sgi.com/tech/stl/Container.html

otze

thanks a lot.
das war genau das, was ich gebruacht hab

//Edit hab mich beim link mal bis map vorgearbeitet....wie kann man es erreichen, dass schlüssel so geordnet sind, dass sie immer in logarithmischer zeit gefunden werden können??

ich meine linear würde mir einleuchten,man testet alle keys nacheinander, bis ne übereinstimmung vorhanden ist. aber streng logarithmisch? was für ne schandtat muss man denn dafür begehen?

ich meine, sogar mit nem baum kann man keine konstant logarithmische laufzeit erreichen...oder etwa doch?

(und iterieren ließ sich der ganze sch**** doch auch nicht oder? aufjedenfall nicht, ohne noch eine Sünde zu begehen)

otze

hmm, war grad dabei meine containerklasse nach den anforderungen der stl zu planen, sie sollte eine art multimap sein, die etwas mehr wert auf das "multi" legt(also darauf optimiert ist viele objekte mit dem selben Schlüssel zu speichern) und da kam mir dann die frage auf, ob sich der arbeitsaufwand überhaupt lohnt,oder ob man nicht gleich einfach ne multimap wrappen sollte.

andererseits wärs natürlich eine schöne und effiziente übung, weil ich dann seit langem mal wieder das Ergebnis meines "Werks" begutachten könnte(was bei einem größeren Projekt so selten genug passiert).

also was meint ihr, würde es sich lohnen einen container komplett neu aus dem Boden zu stampfen?
Oder sollte man zuerst versuchen eine implementation als übung zu machen und dann zum schluss die multimap doch wrappen, weil man eh nicht die effizienz einer map erreichen kann?
(oder 3. sagen: was intressiert mich wie ne map funktioniert, sie existiert und ist wrapbar-basta :p )

KPC

Vielleicht hab ichs übersehen, aber was stört dich an der std::multimap? Meinst du die ist nicht gut optimiert oder wie?

otze

std::multimap<int,string> map;
map.insert(std::pair<int,string>(5,"Hallo,"));
map.insert(std::pair<int,string>(5,"ich"));
map.insert(std::pair<int,string>(5,"bin"));
map.insert(std::pair<int,string>(5,"schwer"));
map.insert(std::pair<int,string>(5,"auszulesen"));

noch fragen?
//edit sorry, die bcb hilfe hat mich in die irre geführt...scheint mit equal range zu funktionieren, aber zufrieden bin ich damit nicht

Gute Quelle zu STL, Containern und dem ganzen zeuch: Komponenten entwerfen mit der C++ STL von Ulrich Breymann, kostenlos zum download.

SideWinder

@Sharde: boost::array ist imho auch kein vollwertiger STL-Container, oder? Der hat ja gar keinen Allokator...

MfG SideWinder

otze

hab nochmal über das ganze nachgedacht, jetzt wo ich die sache mit equal_range zufällig herausgefunden hab(in der bcb hilfe steht hinter dem befehl was ganz andres, dass beispiel war aber so wies sein soll).

Was mir an der multimap nicht gefällt ist, dass sie,obwohl sie multi ist,die Keys eines Wertes eher wie ballast behandelt, es fehlt irgendwie die funktionalität.Iterieren ist nur über einen Umweg möglich, einzelne Objekte mit gleichem Key rauszusuchen ist unmöglich;immer nur das Erste,oder alle.
genau das gleiche mit dem Löschen. Man muss zuerst alle Objekte eines Keys raussuchen,dann über die iteratoren, das objekt suchen, bzw sofort dahinspringen, und dann kann man das Objekt löschen.

Was mich dann noch en bissl aufregt ist, dass Gegenstände gleiches typs einfach im Baum gehalten werden-kann man das nicht als vector oder liste implementieren? dann währe wenigstens die iteration bei objekten mit gleichem Key ordentlich schnell(durch die Blätter eines Baums zu Iterieren KANN nicht so schnell sein).
Andererseits gäbe es dann ein Problem, dass man auch immer auf gleichheit der Keys testen müsste,aber ich glaub nicht, dass das so unheimlich viel kosten würde.

jo, das wär mal das, was mich so an multimap nervt.Nervt euch was an multimap, dann postet, mir fehlen nochn paar ideen

SideWinder schrieb:

@Sharde: boost::array ist imho auch kein vollwertiger STL-Container, oder? Der hat ja gar keinen Allokator...

MfG SideWinder

Class array fulfills most but not all of the requirements of "reversible containers" (see Section 23.1, [lib.container.requirements] of the C++ Standard). The reasons array is not an reversible STL container is because:

No constructors are provided.
Elements may have an undetermined initial value (see the section called “Design Rationale”).
swap() has no constant complexity.
size() is always constant, based on the second template argument of the type.
The container provides no allocator support.

It doesn't fulfill the requirements of a "sequence" (see Section 23.1.1, [lib.sequence.reqmts] of the C++ Standard), except that:

front() and back() are provided.
operator[] and at() are provided.

SideWinder

Eben

MfG SideWinder

Shade Of Mine

boost::array ist für mich dennoch ein echter Container. Der Standard beschreibt ja nur die Anforderungen an die STL Container. Aber es kann ja durchaus ein STL kompatibler Container existieren, der eben nicht zur STL gehört

Der STL fehlen viele Container - (array, ring, hashmap, rope,...) da kann man nicht so wählerisch sein

Zumal diese Anforderungen doch alle nur theoretisch sind. Praktisch haben sie keine Bedeutung... Denn ich kann array und vector sowieso nicht austauschen, genauso wenig wie ich map und multimap (sinnvollerweise) austauschen kann.