Überladen von []/=

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

Boost is' nicht, weil ich das sowieso nicht installiert bekomme und mein Programm dann nachher vermutlich doppelt so groß ist ohne dass es nötig wäre. Ich gucke mir eure Vorschläge erstmal in Ruhe an und dann melde ich mich nochmal. Was ich vorhabe habe ich schon gesagt: Eine Map die unsortiert ist. Was konkret darin abgespeichert wird ist CSS-Code.
http://sourceforge.net/projects/csstidy/
Wer Spaß an der Freude hat kann sich den Code ja mal angucken und wird dann spätestens bei print_css() merken wie blöd es ist wenn man keinen passenden Container hat (oder was passiert wenn man Code von PHP nach C++ konvertiert).

otze

rofl?!? du willst wirklich eine map dazu benutzen, um unsortiert einträge abzuspeichern? hackts?

Wieso das denn? Ich sage doch schon die ganze Zeit dass ich eine unsortiere Map bauen will. Ich habe nie gesagt dass ich die Map zum unsortierten Abspeichern benutzen möchte.

@finix
Ich habe mich jetzt mal für deine Lösung entschieden, soweit funktioniert es auch. Für die Funktion erase() habe ich folgendes gebaut:

void erase(const k key)
{
	for(typename FifoT::iterator i = sortv.begin(); i != sortv.end(); ++i)
	{
		if( (*i)->first == key)
		{
			sortv.erase(i);
			content.erase( (*i)->first);
			return;
		}
	}
}

Wäre das so gut oder kann man da noch was effizienteres schreiben?

finix

Sag mal, geht's noch?

ETA: Falls das doch alles ernst gemeint ist:
How To Ask Questions The Smart Way (de)
Google: c++ tutorial (alternativ dem weißen Hasen oben rechts folgen)
Google: algorithmen datenstrukturen tutorial