random access container map...

RussianTux

Tach alle zusammen,

Da ich die Architektur von std::map nicht kenne, würde ich euch gerne fragen, wie performant:

1. ein Direktzugriff auf den Inhalt eines Keys
2. eine Suche nach einem Key
3. eine write/erase-Funktion

mit der Bedingung "front, end, inside = constant time" ist...

ist eine std::map dazu geeignet Speicher-effizient mehrere Tausend Objekte + deren Keys zu lagern und zu verwalten,
oder kommt man bei solchen Anforderungen um eine eigene Lösung nicht herum?

SeppJ

Mehrere Tausend? Also praktisch nix? Das ist weit unterhalb aller Grenzen, wo man sich irgendwelche großen Performancegedanken machen müsste. $log_2(1000)\approx 10$ , das ist nicht besonders tief. Da sollte man noch ein paar Größenordnungen mehr haben, bevor sich eine Hashmap richtig lohnt. Und die programmiert man dann auch nicht selber! Gibt's schließlich auch in der Standardbibliothek (tr1 bzw. C++11 oder falls man einen Compiler von vor 10 Jahren hat eben mit Boost).

Für dein Überlegungen darfst du übrigens davon ausgehen, dass map intern eine klassische Baumstruktur, meistens ein Rot-Schwarz-Baum, ist. Garantierte Zugriffszeiten zu jeder Funktion findest du in Referenzen oder im Standard. Und der Speichweroverhead ist auch nicht so dramatisch, rechne mal mit um die 32 Byte pro Objekt und nochmal 32 Byte für die map selber, ich denke diese 32 kB kannst du dir leisten.

RussianTux

SeppJ schrieb:

Mehrere Tausend? Also praktisch nix? Das ist weit unterhalb aller Grenzen, wo man sich irgendwelche großen Performancegedanken machen müsste.

Verstehe, ich scheine die Hardware sehr zu unterschätzen, ABER ich will diesen Code auch in Zukunft nutzen, und da könnten es schon locker mehrere Millionen Objekte werden, das ist der Grund dafür warum ich mir schon jetzt Gedanken über die Performance mache.

SeppJ schrieb:

Da sollte man noch ein paar Größenordnungen mehr haben, bevor sich eine Hashmap richtig lohnt.

Also.. Stichwort: "Hashmap"?

SeppJ

Genaueres Stichwort:
Google: unordered_map c++

Das steht und fällt aber mit der Qualität der Hashfunktion. Ist diese schlecht, dann bist du leicht 1000x langsamer als die map mit ihrer garantierten logarithmischen Zugriffszeit. Ist sie gut, dann bekommst du annähernd konstante Zugriffszeit. Also informier dich unbedingt, wie man gute Hashfunktionen entwirft und teste sie aus! Erfahrungsgemäß solltest du ab ein paar Tausend Elementen Vorteile beobachten können, wenn die Hashfunktion gut ist, darunter gewinnt die einfachere Grundstruktur der klassischen map (und darunter (d.h. so 10-50 Elemente) gewinnt ein einfacher vector mit Brute-Force-Suche).

RussianTux

SeppJ schrieb:

Genaueres Stichwort:
Google: unordered_map c++

Das steht und fällt aber mit der Qualität der Hashfunktion. Ist diese schlecht, dann bist du leicht 1000x langsamer als die map mit ihrer garantierten logarithmischen Zugriffszeit. Ist sie gut, dann bekommst du annähernd konstante Zugriffszeit. Also informier dich unbedingt, wie man gute Hashfunktionen entwirft und teste sie aus! Erfahrungsgemäß solltest du ab ein paar Tausend Elementen Vorteile beobachten können, wenn die Hashfunktion gut ist, darunter gewinnt die einfachere Grundstruktur der klassischen map (und darunter (d.h. so 10-50 Elemente) gewinnt ein einfacher vector mit Brute-Force-Suche).

Ich habe deinen Rat befolgt und mich einwenig mit der unordered_map auseinandergesetzt, jedoch komme ich wieder nicht weiter...

#include <map>

class Class
{
private:
	const char* name;
	std::map <const char*, Class> ClassMap;
public:
	Class(const char* new_name = "default")
	{
		name = new_name;
	}
};

Der oben beschriebene Code kompiliert und funktioniert prächtig...

#include <tr1/unordered_map>

class Class
{
private:

	const char* name;
	std::tr1::unordered_map <const char*, Class> ClassMap;

public:

	Class(const char* new_name = "default")
	{
		name = new_name;
	}
};

Der Einsatz einer unordered_map jedoch scheitert schon beim Kompilieren mit der folgenden Fehlermeldung:

In file included from /usr/include/c++/4.6/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/4.6/bits/char_traits.h:41,
                 from /usr/include/c++/4.6/ios:41,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from protocol.cpp:2:
/usr/include/c++/4.6/bits/stl_pair.h: In Instanziierung von »std::pair<const char* const, Class>«:
/usr/include/c++/4.6/bits/stl_function.h:486:12:    instanziiert von »std::_Select1st<std::pair<const char* const, Class> >«
/usr/include/c++/4.6/tr1/hashtable_policy.h:708:20:    instanziiert von »std::tr1::__detail::_Hash_code_base<const char*, std::pair<const char* const, Class>, std::_Select1st<std::pair<const char* const, Class> >, std::equal_to<const char*>, std::tr1::hash<const char*>, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, false>«
/usr/include/c++/4.6/tr1/hashtable.h:108:11:    instanziiert von »std::tr1::_Hashtable<const char*, std::pair<const char* const, Class>, std::allocator<std::pair<const char* const, Class> >, std::_Select1st<std::pair<const char* const, Class> >, std::equal_to<const char*>, std::tr1::hash<const char*>, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, std::tr1::__detail::_Prime_rehash_policy, false, false, true>«
/usr/include/c++/4.6/tr1/unordered_map.h:43:11:    instanziiert von »std::tr1::__unordered_map<const char*, Class, std::tr1::hash<const char*>, std::equal_to<const char*>, std::allocator<std::pair<const char* const, Class> >, false>«
/usr/include/c++/4.6/tr1/unordered_map.h:180:11:    instanziiert von »std::tr1::unordered_map<const char*, Class>«
protocol.cpp:11:47:   instanziiert von hier
/usr/include/c++/4.6/bits/stl_pair.h:93:11: Fehler: »std::pair<_T1, _T2>::second« hat unvollständigen Typen
protocol.cpp:6:7: Fehler: Vorwärtsdeklaration von »class Class«

Es scheint unmöglich eine Klasse rekursiv innerhalb der unordered_map zu deklarieren, was aber mein Ziel ist, wie kann ich das Problem lösen?

MfG RussianTux

wxSkip

Mit der Fehlermeldung kann ich nicht viel anfangen, aber ich vermute, es wird versucht, in der map ein Objekt vom Typ Class anzulegen, das dann wieder eine map mit einem Objekt mit einer map usw. enthalten würde. Versuch mal, die map dynamisch zu erstellen (also ein Pointer (z.B. unique_ptr) und dann mit new() instantiieren).

Ein C-String als key wird auch in einer Hash Map nicht das machen, was du erwartest. Warum benutzt du nicht std::string?

SeppJ

Der Code ist in beiden Fällen nicht standardkonform:

C++-Standard: 17.4.3.6 schrieb:

In certain cases (replacement functions, handler functions, operations on types used to instantiate standard library tem-
plate components), the C++ Standard Library depends on components supplied by a C++ program. If these components
do not meet their requirements, the Standard places no requirements on the implementation.

In particular, the effects are undefined in the following cases:
[...]
— if an incomplete type (3.9) is used as a template argument when instantiating a template component.

Du hast quasi nur "Glück", dass deine Lösung mit map funktioniert.

Die Lösung wäre, Zeigerähnliche Objekte in der map zu speichern. Ist das nicht sowieso das was du möchtest? Es ist schon leicht ungewöhnlich, wenn ein Objekt weitere Instanzen seiner Klasse in sich speichert.

Mechanics

RussianTux schrieb:

ABER ich will diesen Code auch in Zukunft nutzen, und da könnten es schon locker mehrere Millionen Objekte werden

Selbst Millionen von Objekten sind an sich überhaupt kein Problem für eine Map. Die Frage ist, was du damit machen willst. Wenn du da einmal ein Objekt nachschlagen willst, ist es kein Problem. Wenn du eine Schleife mit Millionen Durchläufen hast und jedesmal in der Map nachschauen willst, wärst du mit einer Hashmap evtl. besser beraten. Aber das muss man im Einzelfall prüfen, was ja auch nicht weiter schwer wäre.