Static map template



  • Hallo,

    was haltet ihr von der Idee eine template Klasse StaticMap zu implementieren?

    Ich meine damit eine Klasse, die die Typen für key und value und ihre Größe als template parameter erhält.
    Der Vorteil wäre, dass man nicht mit new arbeiten müsste wie std::map.



  • Du kannst auch bei normalen STL-Maps direkt die Objekte halten.

    (Das Problem an der Stelle ist, dass man auf diese Weise keine Objekte von abgeleiteten Klassen in die Map einfügen kann. Also kommst du nicht drumrum bei deiner Map intern ebenfalls Pointer zu halten... daher braucht man an der der Stelle eine kleine Fabrik, die wiederum benötigt eine einheitliche Schnittstelle, ...
    Man sieht das artet recht schnell aus)



  • Ich glaube er meinte mit Statisch eher die größe der Map, also sowas in der Art:

    template< typename TK, typename TV, int size=64 >
    class StaticMap
    {
      // ...
    }
    
    // ...
    StaticMap< std::string, int, 1024 > container; // Map mit 1024 möglichen Einträgen
    

    grüße



  • Stimmt 😃

    Das macht die Sache allerdings nicht besser. Das Problem mit den abgeleiteten Klassen hat man immer noch und man verbrät zusätzlich noch Speicher den man mit hoher Wahrscheinlichkeit nicht immer benutzt.



  • @Mathias: Ehrlich gesagt weiß ich nicht ganz, was du meinst. std::map hat doch als value_type einfach ein Key,Value-Paar, wieso sollte der dahingehend mit Zeigern arbeiten?!

    Was wäre z.B. gegen sowas einzuwenden:

    template <size_t N, typename Key, typename Value>
    class static_map
    {
    public:
        // std::map Interface
    
    private:
        struct Node
        {
            size_t left, right;
            value_type data;
        };
    
        Node[N] _nodes;
    };
    

    Wenn man sich dafür entscheidet, die Größe der Map festzulegen, wird man schon seine Gründe dafür haben. Man verbrät also im Normalfall keinen oder kaum Speicher damit (im Vergleich zur std::map).



  • Danke für die Antworten.

    Aufgrund der Antworten habe ich mich entschieden eine StaticMap zu implementieren.
    Es handelt sich ja um ein Embedded system. Die Größe der map steht ohnehin im vorraus fest, also wird kein Speicher unnütz verbraten.



  • Was gegen die Implementierung mit einem statischen Array von Pair-Objekte spricht?

    Das Arbeiten mit Schüsseln.
    Das Array muss sortiert sein damit man effektiv mit Hilfe des Schlüssels suchen, hinzufügen und löschen kann. Das sollte im Normalfall eine nette Kopiererei von Pair-Objekten geben, wenn sie nicht vorsortiert sind.
    Ist das ganze wirklich statisch kann ich mir die Map generell sparen und mit
    dem Index als Schlüssel arbeiten.



  • Man kann auch Bäume effizient innerhalb eines linearen Speichers aufbauen (s.o.)., dann gibts kein rumkopieren. In Informatik nicht aufgepasst? 😉
    Das mit dem Index als Schlüssel kann ich nicht nachvollziehen. Wie willst du dann z.B. strings als Schlüssel verwenden?


  • Mod

    wieso nicht einfach einen entsprechenden allocator schreiben?


Anmelden zum Antworten