was braucht ein container, um ein containr zu sein?
-
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^^
-
-
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)
-
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 )
-
Vielleicht hab ichs übersehen, aber was stört dich an der std::multimap? Meinst du die ist nicht gut optimiert oder wie?
-
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.
-
@Sharde: boost::array ist imho auch kein vollwertiger STL-Container, oder? Der hat ja gar keinen Allokator...
MfG SideWinder
-
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.
-
Eben
MfG SideWinder
-
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.
-
Shade Of Mine schrieb:
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.
man kann aber vector und list austauschen, wenn man nur hinten einfügt, und nur über die iteratoren drauf zugreift.
genauso kannst du map und multimap austauschen.
deshalb hat die stl ja auch die container in assoziativ und sequentiell eingeteilt, damit man zwischen denen wenigstens eine austauschbarkeit erzeugen kann.
btw: was ist der unterschied zwischen vector und array, bzw list und rope?
(hoffe ich vergleich jetzt nichts absolut unterschiedliches, aber rein von der assoziation der namen kommt bei mir dieselbe struktur zustande)
-
vector und list kannst du ganz sicher nicht so ohne weiteres austauschen. Eher noch vector und deque. Die list funktioniert völlig anders, IMHO.
btw: was ist der unterschied zwischen vector und array
Wenn du ein array fester Größe willst, dann saugt der vector, zumindest bei mir. Bei mir ist der Zugriff signifikant langsamer, obwohl ich mir eigentlich nicht erklären kann, warum das so ist. Ein boost::array ist auf jeden Fall nicht viel mehr als ein Wrapper um ein C-Array. Noch ein assert in den operator[] und es ist godlike.
-
ist boost::array ein array welches schon zur compile time feststeht(also eine mit templates bestimmte größe), oder ist das ein array, welches mit new arbeitet?
-
Es steht zur Compilierzeit fest.
-
*kopfkratz*
und wieso nicht dann gleich ein c-array?
-
Weil C-Arrays irgendwie ganz schön kaputt sind, vor allem was die Übergabe als Parameter oder Rückgabewert angeht... Außerdem hat boost::array dann eben das STL-Interface; begin, end, die typedefs...
-
operator void schrieb:
Weil C-Arrays irgendwie ganz schön kaputt sind, vor allem was die Übergabe als Parameter oder Rückgabewert angeht... Außerdem hat boost::array dann eben das STL-Interface; begin, end, die typedefs...
ok, damit haste recht, da übergibt man ein array als rückgabewert, und steht dann plötzlich mit nicht allokiertem speicher da
.
und die preisfrage: hab ich nun genug speicher oder nicht" bei übergabe eines char arrays is auch..naja ich red lieber nich weiter^^
-
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