Eigene Map

Nexus

Du bist auch relativ frei, wenn du eine eigene Map gestaltest. Kriterium ist ja eigentlich nur, dass sie ständig sortiert ist und man in logarithmischer Zeit suchen kann, und das ist durch einen binären Suchbaum wunderbar gegeben. Ansonsten bei konkreten Dingen kann dir sicher auch die Implementierung der std::map deiner Standardbibliothek helfen. Eventuell auch www.cplusplus.com/reference/stl/map.

Vielleicht hat ja noch jemand anders Ratschläge.

Firefighter

Alles klar Nexus, das mit dem Binären Baum werde ich versuchen umzusetzen.

Don06

Könnte man nicht zuerst ein eigenes Set implementieren und dann Map einfach als Adapter für das Set?

Nexus

Don06 schrieb:

Könnte man nicht zuerst ein eigenes Set implementieren und dann Map einfach als Adapter für das Set?

Wie meinst du das konkret? Einfach zuerst das Set fertigstellen und dann die Map darum herum bauen? Wie würdest du dann die Elemente zuordnen?

Ich würde für die Knoten der Map einfach Zeiger auf Schlüssel-Wert-Paare einsetzen (z.B. std::pair* ).

Firefighter

Genau, an std::pair hatte ich auch für die interne Darstellung gedacht. Was mir nur im Moment etwas zu schaffen macht, die Implementations als Baum.

kimmi

Ich weiß gerade nicht, ob das in dem Artikel ebenfalls beschrieben wird: Schau auch mal nach Rot-Schwarz-Baum, um einen ausgeglichenen Baum zu garantieren.

Gruß Kimmi

Don06

Das Set wäre doch ein Template. Wenn du also ein Set mit Wertetyp std::pair anlegst und einen Komparator (?) einsetzt der nur nach dem ersten Wert im Paar sortiert, hasst du deine Map, oder liege ich falsch?

Nexus

Über den AVL-Baum haben wir zum Beispiel auch einen Artikel.

Don06, ah so hast du es gemeint. Du hast eigentlich schon Recht, allerdings wäre die Schnittstelle ein wenig anders bei einer Map. Ich weiss nicht, ob sich eine Vererbung lohnen würde...

template <typename KeyType, typename ValueType>
class Map : public Set<std::pair<KeyType, ValueType> >
{
    ...
};

Wahrscheinlich gibt es aber etwas, das dagegen spricht. Hm... Aber grundsätzlich fährt man wahrscheinlich nicht schlecht, wenn man zuerst ein Set implementiert. Falls es dann doch nicht über Vererbung gehen würde, müsste man trotzdem nicht viel Code abändern...

volkard

Nexus schrieb:

Wahrscheinlich gibt es aber etwas, das dagegen spricht.

ja. es stimmt einfach nicht, daß eime map eine set ist.

Nexus

Hehe, an das habe ich auch gedacht.

Wobei es mir vorher doch nicht so schlimm vorkam - aber eigentlich hast du Recht. Womit wir wieder mal Code duplizieren müssten...

volkard

Nexus schrieb:

Hehe, an das habe ich auch gedacht.
Wobei es mir vorher doch nicht so schlimm vorkam - aber eigentlich hast du Recht. Womit wir wieder mal Code duplizieren müssten...

nicht viel. fast alles wird ja an die Set weitergereicht.

template <typename KeyType, typename ValueType>
class Map
{
    private: 
       Set<std::pair<KeyType, ValueType> > data;
   public:
       void clear()
       {
          data.clear();
       }
};

Nexus

Okay, guter Vorschlag. Dann kann man auch Schnittstellenfunktionen wie operator[] einfach bereitstellen.

In Zukunft sollte ich wohl etwas länger philosophieren, bevor ich unüberlegte Dinge wie "Vererbung" ausspreche.

volkard

Nexus schrieb:

In Zukunft sollte ich wohl etwas länger philosophieren, bevor ich unüberlegte Dinge wie "Vererbung" ausspreche.

och, es reicht eigentlich schon, wenn du die geschichte von herrn bebel liest. http://www.c-plusplus.net/forum/viewtopic-var-t-is-75672.html

Nexus

Die habe ich bereits gelesen. Und ich muss sagen, sie hat echt Stil.