Nochmal: vector vs map für Mapping



  • 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. 🙂



  • 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.



  • 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?



  • 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.



  • cooky451 schrieb:

    und du das einfachere Interface möchtest.

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



  • 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.



  • 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...



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



  • 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.



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

    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)];
    }
    


  • 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 😉



  • 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.



  • 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.



  • 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:

    #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:

    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)];
    }
    


  • Was fuer mieser C Frickelcode. 👎



  • C++ler. schrieb:

    Was fuer mieser C Frickelcode. 👎

    Was für ein dummer, falscher Kommentar 👎



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



  • 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.



  • typedef unsigned int const flag_t;
    
    flag_t foo = 1;
    flag_t bar = 2;
    flag_t baz = 4;
    flag_t qux = 8;
    


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


Log in to reply