C/C++ Forum :: Nochmal: vector vs map für Mapping

Eisflamme Mitglied 11:50:05 01.02.2012 Titel:

Hi,

sorry, ich weiß, die Diskussion gab es schon Mal, aber mir ist das noch immer nicht ganz klar geworden.

Die map ist ja zuweilen etwas verpöhnt, wenn es um kurze Mappings geht. Ich habe diverse Konstanten, die man mit | verschachteln kann. Jetzt möchte ich gerne diesen Flags Strings zuweisen, um sie artgerecht auf einem UI darzustellen.

Wenn ich einen vector nehme, hab ich eine worst-case Laufzeit von O(N) bzw. O(log(N)) mit binärer Suche. Bei einer map ist diese O(log(N)), richtig? Dann wäre doch eine map zumindest genau so gut und vom Zugriff eben noch einen Tick einfacher. Wieso dann nicht die map?

Tut mir nochmals Leid, aber hört auch mein danke.

cooky451 Mitglied 12:08:43 01.02.2012 Titel:

Die map ist intern ähnlich einer Liste. Das bedeutet, dass du schneller einfügen/entfernen kannst, aber beim Zugriff mehr Indirektionen und mehr Cache-Misses (vector liegt im Speicher ja am Stück) hast.

Eisflamme Mitglied 12:12:51 01.02.2012 Titel:

Ah gut, richtig... Also ist vector mit binärer Liste wohl mein Kandidat.

Wenn man schnell lesen will und die Einfüge/Lösch-Geschwindigkeit irrelevant ist, sollte man dann überhaupt je die map nutzen?

Ich kenn diesen Graphen für Container-Verwendung, der aber zwischen Mapping/Nicht-Mapping unterscheidet, sodass man im Mapping-Fall ja immer map oder set nehmen würde... demnach bietet er sich nicht an. Gibt es denn auch so eine schöne Container-Übersicht unter Berücksichtigung der Tatsache, dass man Mapping leicht mit vector emulieren kann?

cooky451 Mitglied 12:28:01 01.02.2012 Titel:

Eisflamme schrieb:

Gibt es denn auch so eine schöne Container-Übersicht unter Berücksichtigung der Tatsache, dass man Mapping leicht mit vector emulieren kann?

Ich glaube nicht, diese Karte ist ja eher eine Orientierung für Anfänger. Selbst denken ist immer besser.

Eisflamme schrieb:

sollte man dann überhaupt je die map nutzen?

Ja. Wenn du eben viele Daten hast und ab und zu etwas einfügen/entfernen willst, dann ist eine Liste schneller. Oder wenn dir Performance egal ist und du das einfachere Interface möchtest.

Bashar Mitglied 12:33:06 01.02.2012 Titel:

cooky451 schrieb:

und du das einfachere Interface möchtest.

Das ist kein Hindernis, man kann sich ja eine auf sortierten Vektoren basierende map bauen.

cooky451 Mitglied 12:44:39 01.02.2012 Titel:

Bashar schrieb:

Das ist kein Hindernis, man kann sich ja eine auf sortierten Vektoren basierende map bauen.

Ja, das meinte ich aber nicht, war schlecht formuliert; sollte heißen: "Oder wenn dir Performance egal ist und du dich nicht darum kümmern möchtest."
Der Vektor ist im jeweils schlechtesten Fall halt wesentlich langsamer.

megaweber Mitglied 17:29:13 01.02.2012 Titel:

Vielleicht gibt es ja auch eine Möglichkeit die Flags als int's zu verwenden oder zu interpretieren, dann kannst Du mit einem vector natürlich ohne Suche auf die Elemente zugreifen...

Eisflamme Mitglied 18:51:52 01.02.2012 Titel:

Es sind halt 32 Flags, die alle beliebig kombiniert werden können, der Vector wäre dann etwas arg groß. ^^

314159265358979 Mitglied 19:13:10 01.02.2012 Titel:

Dafür ist sowohl vector, als auch map falsch. Dafür nimmt man 2 rohe C-Arrays, die bereits entsprechend vorsotiert sind. Die Suche des Flags im ersten Array liefert dann den Index des entsprechenden Strings im zweiten.

314159265358979 Mitglied 19:59:09 01.02.2012 Titel:

Und wer ganz flotten Lookup in O(1) haben möchte, der machts so:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	unsigned log2(unsigned x) { unsigned y; asm("bsr %1, %0" : "=r"(y) : "r"(x)); return y; } #define FLAG(name, value) unsigned const name = value; FLAG(foo, 1) FLAG(bar, 2) FLAG(baz, 4) FLAG(qux, 8) // usw... #undef FLAG char const* const stringvals[] = { "foo", "bar", "baz", "qux" }; char const* flag_to_string(unsigned flag) { return stringvals[log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	unsigned log2(unsigned x) { unsigned y; asm("bsr %1, %0" : "=r"(y) : "r"(x)); return y; } #define FLAG(name, value) unsigned const name = value; FLAG(foo, 1) FLAG(bar, 2) FLAG(baz, 4) FLAG(qux, 8) // usw... #undef FLAG char const* const stringvals[] = { "foo", "bar", "baz", "qux" }; char const* flag_to_string(unsigned flag) { return stringvals[log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	unsigned log2(unsigned x) { unsigned y; asm("bsr %1, %0" : "=r"(y) : "r"(x)); return y; } #define FLAG(name, value) unsigned const name = value; FLAG(foo, 1) FLAG(bar, 2) FLAG(baz, 4) FLAG(qux, 8) // usw... #undef FLAG char const* const stringvals[] = { "foo", "bar", "baz", "qux" }; char const* flag_to_string(unsigned flag) { return stringvals[log2(flag)]; }

pumuckl Moderator 19:59:21 01.02.2012 Titel:

314159265358979 schrieb:

Dafür ist sowohl vector, als auch map falsch. Dafür nimmt man 2 rohe C-Arrays

Kommt immer drauf an.
Wenn du ein fixes mapping hast, ohne einfügen und löschen, dann reicht ein statisches C-Array mit den Schlüssel-Wert-Paaren (Wozu du da zwei Arays nehmen willst ist mir schleierhaft). Wers möchte kann das natürlich auch in ein std::array packen, aber das ist nur Syntax-Candy.
Wenn man Schlüssel-Wert-Paare einfügen/löschen möchte, braucht man entsprechend dynamische Strukturen, da sind rohe C-Arrays Blödsinn.

Allgemein wäre ich mit solchen Absolut-Aussagen "Das ist falsch, das macht man anders" immer vorsichtig. Vor allem wenn die Rahmenbedingungen nicht genau feststehen.

Zum "einfacheren Zugriff" auf maps: kann man sich für statische Tabellen auch selber schreiben

314159265358979 Mitglied 20:11:01 01.02.2012 Titel:

Dass es Flags sind, impliziert eigentlich für mich, dass zur Laufzeit keine hinzukommen. Eine Methode mit einem einzigen Array habe ich gerade gezeigt, würde mich interessieren, wie du das gelöst hättest.

Eisflamme Mitglied 12:42:42 02.02.2012 Titel:

Die Flags sind natürlich statisch, die Texte erstmal auch. Aber bald hab ich vor das zu internationalisieren und dann sind die natürlich nicht mehr statisch. Wobei ich noch nicht sicher bin, ob man die Sprache live umstellen können soll.

Wieso nutzt Du im Code ein Makro für die Konstantendefinition? Tipparbeit ersparen?

Ansonsten geht log2 natürlich ganz gut... kann man ja sogar noch als Template implementieren.

314159265358979 Mitglied 13:39:48 02.02.2012 Titel:

Schreibfaulheit

Wenn du verschiedene Sprachen hast, dürfte das ebenfalls kein Problem sein. Dann steckst du die Arrays jeder Sprache nochmal in ein Array und gibst der Funktion für die Umwandlung als Parameter den Index des äußeren Arrays mit. Etwa so:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10	#define DEFCONST(name, value) unsigned const name = value; // natürlich bin ich schreibfaul ;) DEFCONST(de, 0) DEFCONST(en, 1) #undef DEFCONST char const* const stringvals[][] = { { "foo", "bar" }, { "baz", "qux" } }; char const* flag_to_string(unsigned flag, unsigned lang) { return stringvals[lang][log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	#define DEFCONST(name, value) unsigned const name = value; // natürlich bin ich schreibfaul ;) DEFCONST(de, 0) DEFCONST(en, 1) #undef DEFCONST char const* const stringvals[][] = { { "foo", "bar" }, { "baz", "qux" } }; char const* flag_to_string(unsigned flag, unsigned lang) { return stringvals[lang][log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	#define DEFCONST(name, value) unsigned const name = value; // natürlich bin ich schreibfaul ;) DEFCONST(de, 0) DEFCONST(en, 1) #undef DEFCONST char const* const stringvals[][] = { { "foo", "bar" }, { "baz", "qux" } }; char const* flag_to_string(unsigned flag, unsigned lang) { return stringvals[lang][log2(flag)]; }

Wobei, für eine Sprache kannst du auch ein enum nehmen, wie auch immer. Ich bin mir gerade allerdings nicht sicher, ob MSVC schon enum classes unterstützt.

Nebenbei sollte die Funktion log2 wohl eher log2_minus_one heißen.

Mit enum class vielleicht so:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10	enum class language : unsigned { de = 0, en = 1, }; char const* flag_to_string(unsigned flag, language lang) { return stringvals[static_cast<unsigned>(lang)][log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	enum class language : unsigned { de = 0, en = 1, }; char const* flag_to_string(unsigned flag, language lang) { return stringvals[static_cast<unsigned>(lang)][log2(flag)]; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	enum class language : unsigned { de = 0, en = 1, }; char const* flag_to_string(unsigned flag, language lang) { return stringvals[static_cast<unsigned>(lang)][log2(flag)]; }

Unregistrierter

Was fuer mieser C Frickelcode. :die:

314159265358979 Mitglied 14:38:30 02.02.2012 Titel:

C++ler. schrieb:

Was fuer mieser C Frickelcode. :die:

Was für ein dummer, falscher Kommentar :die:

Unregistrierter

Ein globales char* array und Makros sind also guter C++ Stil? lol

314159265358979 Mitglied 16:09:34 02.02.2012 Titel:

Ob das Array global ist oder nicht, darauf habe ich mich in meinem Code nicht festgelegt. An einem Array aus char const* ist nichts verwerflich.

Makros sind nicht grundsätzlich böse. Es ist böse, sie für Funktionen zu missbrauchen, da das zu schwer findbaren Fehlern führt. Hier machen sie den Code sogar besser, da dadurch Redundanzen und damit auch mögliche Copy & Paste-Fehler beseitigt werden. Als netter Nebeneffekt ists auch weniger Tipparbeit und der Code wird besser wartbar, da nur an einer Stelle ausgebessert werden muss.

Unregistrierter

C/C++ Code:
typedef unsigned int const flag_t; flag_t foo = 1; flag_t bar = 2; flag_t baz = 4; flag_t qux = 8;

C/C++ Code:
typedef unsigned int const flag_t; flag_t foo = 1; flag_t bar = 2; flag_t baz = 4; flag_t qux = 8;

C/C++ Code:
typedef unsigned int const flag_t; flag_t foo = 1; flag_t bar = 2; flag_t baz = 4; flag_t qux = 8;

314159265358979 Mitglied 19:18:59 02.02.2012 Titel:

Das ist aber immer noch weniger gut wartbar. Ein Flag muss keine Variable sein.

Michael E. Mitglied 23:02:48 02.02.2012 Titel:

314159265358979 schrieb:

Das ist aber immer noch weniger gut wartbar. Ein Flag muss keine Variable sein.

Bitte was?

BTW: Was spricht gegen enums?

314159265358979 Mitglied 23:40:58 02.02.2012 Titel:

Michael E. schrieb:

Bitte was?

Ach, vergiss es. Sobald ich irgendwas sage, kommt bestimmt wieder gleich ein Unreg daher und versucht, wieder was falsches rauszulesen. Kein Bock mehr, meine Grundidee, wie mans mit den Arrays macht, ist rübergekommen.

Michael E. schrieb:

BTW: Was spricht gegen enums?

Nichts.

Bashar Mitglied 00:10:37 03.02.2012 Titel:

314159265358979 schrieb:

Ach, vergiss es. Sobald ich irgendwas sage, kommt bestimmt wieder gleich ein Unreg daher und versucht, wieder was falsches rauszulesen.

Man lernt mit der Zeit, die Deppen zu ignorieren.