Überladen von []/=

otze

Floele schrieb:

otze schrieb:

normale maps benutzen keinen proxy. normale maps geben das objekt ansich zurück.[...]Die einzige lösung wär, beim proxy den operator. zu überladen, aber das _darfst_ du nicht. Das sieht der Standard leider nicht vor.

Und wie konkret machen die maps das bzw. warum kann ich das nicht auch so machen?

die amchen das garnicht. die geben nur ne referenz auf das objekt zurück, welches gesucht wird.

Vielleicht hilft es ja wenn wir das ganze von hinten angehen, vom Ziel her. Mein Ziel ist es nämlich (hauptsächlich jedenfalls) eine unsortierte Map zu erstellen. Mit Google habe ich da nichts passendes gefunden. Gibt es nicht irgendeine Möglichkeit sowas zu erstellen?

CStoll

unsortierte Map? reicht ein vector<pair<k,v> > (oder list<pair>) für deine Zwecke schon aus?

Wenn ich wie bei einer map["a"]["b"] darauf zugreifen kann schon, aber das geht nicht, oder?

CStoll

Das müsstest du dir selber schreiben. Kannst du eventuell mal detaillierter beschreiben, was du vorhast?

Ja, ganz einfach. Ich will eine Map, die genauso funktioniert wie die richtige Map (also auch verschachtelbar, beliebige Typen als Key/Value etc.) mit dem einzigsten Unterschied dass sie unsortiert ist. Das heißt dass das was zuerst in die Map reinkommt soll auch zuerst wieder rauskommen (FIFO wird das glaube ich genannt).

CStoll

Wie wär's mit einer "list<pair<K,T> >" oder "deque<pair<K,T> >" für diesen Zweck? (verwende jeweils push_back() zum anfügen und front()/pop_front(), um das älteste Element abzufragen und rauszuschmeißen)

camper

boost::multi_index_container

CStoll schrieb:

Wie wär's mit einer "list<pair<K,T> >" oder "deque<pair<K,T> >" für diesen Zweck? (verwende jeweils push_back() zum anfügen und front()/pop_front(), um das älteste Element abzufragen und rauszuschmeißen)

Und wie kann ich dann zum Beispiel ein Element (aus der Mitte) abfragen oder ändern?

boost::multi_index_container

Ne, der Aufwand lohnt sich nicht. Wahrscheinlich würde ich es sowieso nicht schaffen Boost einzubinden.

camper

Floele schrieb:

Und wie kann ich dann zum Beispiel ein Element (aus der Mitte) abfragen oder ändern?

std::find, und dann machst du was mit dem iterator

Ist das nicht zu langsam?

finix

camper schrieb:

Floele schrieb:

Und wie kann ich dann zum Beispiel ein Element (aus der Mitte) abfragen oder ändern?

std::find, und dann machst du was mit dem iterator

Wohl eher std::find_if!?

Floele schrieb:

Ist das nicht zu langsam?

Zu langsam wofür?
Was stellst du hauptsächlich mit dem Container an?

Naja, ich speichere Daten darin, lese sie aus und ändere sie. Wieviele ist abhängig von der Größe der Ausgangsdatei. Mit "zu langsam" meine ich ob es gut ist das so zu machen, ich könnte mir vorstellen dass das mit normalen Maps dann um ein vielfaches schneller ist als immer wieder nach dem richtigen Key zu suchen.

finix

Floele schrieb:

Naja, ich speichere Daten darin, lese sie aus und ändere sie. Wieviele ist abhängig von der Größe der Ausgangsdatei. Mit "zu langsam" meine ich ob es gut ist das so zu machen, ich könnte mir vorstellen dass das mit normalen Maps dann um ein vielfaches schneller ist als immer wieder nach dem richtigen Key zu suchen.

Natürlich ist es schneller in einer map als in einer list zu suchen.

Was wäre eigentlich mit dieser Methode?

private:
	vector<k> sortv;
	map<k,t> content;

   bool has(const k key)
   {
       return (content.find(key) != content.end());
   }

   // Operators
   t& operator[](const k key)
   {
      if(!has(key))
      {
         sortv.push_back(key);
      }
      return content[key];
   }

Das heißt bei jedem Zugriff/jeder Zuweisung durch [] wird dem Sortier-Vektor (sortv) hinten der Key angefügt. Könnte es damit Probleme geben? Oder gibt es da sonst irgendwelche Tücken? Vom Zugriff her (mit Verschachtelung und so) funktioniert jedenfalls alles.

CStoll

ich würde die Parameter jeweils auf "const k**&** key" setzen und eventuell eine konstante Version von op[] definieren:

t operator[](const k& key) const
{
  if(!has(key))
    return t();
  else
    return content[key];
}

Was habe ich denn von der konstanten Version?

CStoll

Damit kannst du deinen Container als "const unsort_map<>& herumreichen, wenn du vermeiden willst, daß eine Funktion ihn verändern will.

Btw, benötigst du im späteren Verlauf noch die FIFO-Reihenfolge deiner Werte? Wenn ja, würde ich noch eine Direktverknüpfung von den sortv-Elementen in die map einbauen.

Jaja, FIFO soll es immer bleiben (bzw. die Reihenfolge die der Sortiervektor hat. Unter Umständen wird der auch umsortiert). Wie geht das mit Direktverknüpfungen denn (oder was habe ich davon)?

CStoll

Direktverknüpfungen bekommst du hin, indem du einen vector<pair<k,map<k,t>::iterator> > (der Ausdruck sieht schlimmer aus als er ist :D) verwendest und dort immer make_pair(key,content.find(key)) einträgst - auf diese Weise mußt du bei einem Zugriff über den Vektor nicht noch extra den zugehörigen Inhalt speichern.

PS: Es gibt keinen universell optimalen Container - in einem Vektor (oder List) kannst du die FIFO-Reihenfolge gut beibehalten, benötigst aber lineare Zeit für die Suche, in einem Set oder Map kannst du in logarithmischer Zeit suchen, mußt allerdings auf die Reihenfolge verzichten - und in einer Kombination Vektor+Map hast du eben den Aufwand, beides synchron zu halten.