Überladen von []/=

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.

CStoll schrieb:

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.

Ich glaube nicht dass ich das verstanden habe
Kannst du vielleicht mal ein Praxisbeispiel geben? Die Verbindung von key und value habe ich in der Map und ich kann mir grade nicht vorstellen wie ich einen solchen Vektor sinnvoll nutzen könnte.

CStoll

Das Problem bei deiner Implementation ist, daß du beim Zugriff über den Vektor "nur" den Schlüsselwert hast und erstmal den zugehörigen Wert suchen mußt - deshalb wäre es eventuell günstiger, dort auch einen Verweis auf das zugehörige Map-Element zu speichern:

vector<pair<k,map<k,t>::iterator> > sortv;
map<k,t> content;

T& operator[](const k& key)
{
  if(!has(key))
  {
    //Schlüssel in map eintragen und Zielposition merken
    map<k,t>::iterator pos = content.insert(make_pair(key,t())).first;
    //Schlüssel und Zielposition in Vektor
    sortv.push_back(make_pair(key,pos);
  }
  return content[key];
}

T& at_pos(int pos)
{
  //      zweite Hälfte des   Zugriff auf
  //      Vektor-Elements     Map-Value
  return (sortv[pos].second)->second;
}

(ist vielleicht noch zu optimieren, aber so ungefähr könnte es aussehen)

Je nach deinen Anforderungen an die Laufzeit könntest du auch ganz auf die Map verzichten und mit std::find() direkt im Vektor suchen.

camper

tja, wenn man soweit ist und zwei container benutzt, kann man wie erwähnt auch gleich boost::multi_index_container benutzen. ist bequemer, sicherer und effizienter.

finix

CStoll schrieb:

vector<pair<k,map<k,t>::iterator> > sortv;

Hehe.. warum kompliziert wenn's auch umständlich geht, was?

template <typename KeyT, typename ValueT>
class FifoMap
{
public:
  typedef std::map<KeyT, ValueT> MapT;
  typedef std::deque<typename MapT::iterator> FifoT;

  void pop()
  {
  	content.erase(sortv.front());
  	sortv.pop_front();
  }

  ValueT& operator[]( KeyT const& k )
  {
    typename MapT::iterator mIt = map_.find(k);
    if (mIt == map_.end()) {
      mIt = content.insert(typename MapT::value_type(k, ValueT())).first;
      sortv.push_back(mIt);
    }
    return mIt->second;
  }

  ValueT& at( std::size_t index )
  {
    // range check!?
    return sortv[index]->second;
  }

  // ...

private:
  MapT  content;
  FifoT  sortv;
};

@Floele vielleicht solltest du einfach mal damit rausrücken was du eigentlich vorhast: was sind deine Anforderungen (an Funktionalität), wie wirst du den Container hauptsächlich verwenden, etc

Ansonsten kann ich mich eigentlich nur camper anschließen, schau dir einfach mal boost::multi_index_container an...