Frage zum Artikel-Forum (Rechte am Code)
-
std::map garantiert auch logarithmische Zeit beim Suchen.
-
crashterpiece schrieb:
Für die Theorie kann ich durchaus andere Quellen zitieren (eben diese Herren A, V und L wenns sein muss).
Ne schöne Alternative dazu ist auch "Introduction to Algorithms" Cormen, Leisersen, und noch zwei
und für die Implementierung würde ich dann wirklich auf std::map zurückgreifen. Kann gut sein, dass die sogar schneller sind als AVL-Bäume, da sie nicht so viel Zeit aufwenden um sich vollständig zu balancieren, sondern eben nur halbwegs balanciert sind (hat aber trotzdem noch O(log n) Zeit für Finden/Löschen/Einfügen).
-
Mit dem klitzekleinen Unterschied, dass ich bei einer Map(*) nach erfolgloser Suchen nach einer Einfuegestelle einen Pointer auf end() bekomme. In einem Baum bekomme ich die korrekte Einfuegestelle und kann diese direkt verwenden.
Naja, ich kanns ja mal mit einer (Q)Map testen, prinzipiell ändert sich nicht viel in meinem Code...
(*) ich denke mal, QMap von Qt wird sich da nicht soviel anders verhalten
-
crashterpiece schrieb:
(*) ich denke mal, QMap von Qt wird sich da nicht soviel anders verhalten
RTFM.
Btw. wie wärs mit QAVLTree? :p
-
gibt doch lower_bound, das liefert dir afaik nächstkleinere element
-
crashterpiece schrieb:
Mit dem klitzekleinen Unterschied, dass ich bei einer Map(*) nach erfolgloser Suchen nach einer Einfuegestelle einen Pointer auf end() bekomme. In einem Baum bekomme ich die korrekte Einfuegestelle und kann diese direkt verwenden.
Der operator[] legt direkt ein default-konstruiertes Objekt an der korrekten Stelle an, wenn er nichts findet.
-
Ein bisschen Off topic : Es würde mich durchaus interessieren wie das mit den Rechten nun steht.
-
Ben04 schrieb:
Ein bisschen Off topic : Es würde mich durchaus interessieren wie das mit den Rechten nun steht.
Marc++us und ich diskutierten die Lizenzproblematik bereits... hier mal ein Auszug einer E-Mail:
Marc++us schrieb:
Daher unterliegen die Artikel zur Zeit einer ganz einfachen Lizenz (nämlich dem deutschen Recht):
a) jeder der einen Artikel kopieren/veröffentlichen/modifizieren will, benötigt die Erlaubnis des Autors - wir haben damit gar nichts zu tun
b) wir haben das Nutzungsrecht
c) niemand darf ohne Erlaubnis von c++.de die Artikel als Paket kopieren und veröffentlichen (Urheberrecht auf "Datensammlung")
-
ich kann dazu sagen, dass meine DA ohnehin auf OpenSource-Software basiert (zB Qt und diverse andere Bibliotheken). Der Einsatz ist im medizinischen Bereich und definitiv auf einen kleinen Benutzerkreis eingeschränkt.
Vielleicht könnt ihr in euerer Diskussion ja einmal berücksichtigen, ob die Implementierung eines bekannten Verfahrens (hier AVL-Bäume) noch unter besondere Rechte des Eigentümers fallen oder ob dies nur für vom Autor "eigenständig" geschriebenen Code dienen soll?
-
crashterpiece schrieb:
Mit dem klitzekleinen Unterschied, dass ich bei einer Map(*) nach erfolgloser Suchen nach einer Einfuegestelle einen Pointer auf end() bekomme. In einem Baum bekomme ich die korrekte Einfuegestelle und kann diese direkt verwenden.
Das kommt ganz darauf an, wie du suchst - find() liefert dir im Fehlerfall end() zurück, lower_bound(), upper_bound() und equal_range() liefern dir Iteratoren "in der Nähe" der Zielposition.
(und insert() und operator[] suchen sich sogar selber ihre Zielposition)Zu den Rechten gilt im Zweifelsfall die Bemerkung, die ganz unten auf jeder Seite eingeblendet wird:
C++ Forum schrieb:
Die Vervielfältigung der auf den Seiten www.c-plusplus.net, www.c-plusplus.info, www.c-sar.de, www.c-plusplus.net und www.baeckmann.de enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.