Überladen von []/=

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

finix schrieb:

Sag mal, geht's noch?

Was ist denn jetzt los? Habe ich zu viele Fragen gestellt oder wie?

otze

Floele schrieb:

finix schrieb:

Sag mal, geht's noch?

Was ist denn jetzt los? Habe ich zu viele Fragen gestellt oder wie?

Du stellst sie nicht richtig!

Bis jetzt habt ihr euch doch auch nicht beschwert, warum so plötzlich? Ich wüsste schon ganz gerne was ich in meinem letzten Beitrag falsch gemacht habe dass man so reagieren muss. Wenn euch die Frage über erase() also nun aus irgendwelchen Gründen nicht gefallen hat können wir das auch vergessen (da es immerhin funktioniert) und ich stelle einfach meine vorerst letzte Frage in er Hofffnung dass sie besser ankommt.

camper

[quote="Floele"]

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;
		}
	}
}

sortv.erase(i) invalidiert i, und key hast du sowieso schon als argument. im übrigen würde ich hier find_if benutzen.

finix

ok ok... erstmal erase:

// * Cpp-tags sehen im C++-Forum deutlich huebscher aus

void erase( const KeyT& key ) 
// * Per Referenz macht sich deutlich besser
// * Wenn dir KeyT nicht zusagt waehle einen anderen Bezeichner, aber
//   einfach nur 'k' sieht zu sehr nach Variable aus
{
  for (typename FifoT::iterator i = sortv.begin(), e = sortv.end(); i != e; ++i)
  // * Stil- & _Geschmacks_sache, aber for, if, etc sind Keywords, sind
  //   keine Funktionen, daher ein Space zwischen Keyword und Klammer
  {
    if ((*i)->first == key)
    {
      //sortv.erase(i);
      // * Sehr schoen. Mit der letzten Zeile hast du i 'kaputt' gemacht
      //content.erase((*i)->first);
      // * Wenn du Pech (!) hast kompiliert diese Zeile nicht nur
      //   sondern laeuft sogar. Koenntest den Parameter key nehmen, aber:
      // * Warum laesst du in der map nochmals suchen wenn es dir so um
      //   Performance geht? Du hast die Position in der map gerade gefunden...

      content.erase(*i);
      sortv.erase(i);
      return;
    }
  }
  // * Die Schleife an sich ist auch nicht wirklich zu huebsch - wenn du
  //   noch weitere Faelle hast wo du nach key oder value (in sortv) suchen
  //   musst draengt es sich foermlich auf dir ein Praedikat zu bauen und
  //   mit std::find_if zu arbeiten
}

Zu deiner "eigentlichen" Frage: Ich ziehe vielleicht voreilige Schlüsse, aber warum hast selbst nach 5 1/2 Seiten und mehrfacher Nachfrage immer noch nicht erwähnt dass du scheinbar ein PHP-"Array" nachbauen willst?

Und du solltest echt mal nach Lektüre Algorithmen & Datenstrukturen Ausschau halten, dann müsstest du nicht darüber nachgrübeln ob das Suchen nach einem Schlüssel in einer map nicht schneller geht als einer pair<key,val>-list, würdest bemerken dass dein Vorhaben nicht mehr allzu viel mit FIFO zu tun hat, dass du deine Probleme evtl auch ohne php_style_array lösen kannst, dann noch ein paar allgemeine C++-Tutorials und du würdest weniger solche Schnitzer wie oben in deinen Code basteln noch müsstest du nicht so wahnsinnige Komplexitätsängste vor boost haben.... </rant>

// * Per Referenz macht sich deutlich besser
// * Wenn dir KeyT nicht zusagt waehle einen anderen Bezeichner, aber
// einfach nur 'k' sieht zu sehr nach Variable aus
// * Stil- & _Geschmacks_sache, aber for, if, etc sind Keywords, sind
// keine Funktionen, daher ein Space zwischen Keyword und Klammer
// * Sehr schoen. Mit der letzten Zeile hast du i 'kaputt' gemacht

Soweit komme ich mit

finix schrieb:

// * Wenn du Pech (!) hast kompiliert diese Zeile nicht nur
// sondern laeuft sogar.

Da hatte ich wohl Pech.

// * Warum laesst du in der map nochmals suchen wenn es dir so um
/ Performance geht? Du hast die Position in der map gerade gefunden...

Eigentlich wollte ich auch genau das vermeiden...habe das Ziel leider knapp verfehlt.

// * Die Schleife an sich ist auch nicht wirklich zu huebsch - wenn du
// noch weitere Faelle hast wo du nach key oder value (in sortv) suchen
// musst draengt es sich foermlich auf dir ein Praedikat zu bauen und
// mit std::find_if zu arbeiten

Ja, aber müsste ich dann nicht noch eine extra-Funktion/Klasse bauen? Ich kann mir nicht vorstellen dass das so viel bringt (?)
Außer bei erase() brauche ich solche Suchschleifen im Moment nicht.

Zu deiner "eigentlichen" Frage: Ich ziehe vielleicht voreilige Schlüsse, aber warum hast selbst nach 5 1/2 Seiten und mehrfacher Nachfrage immer noch nicht erwähnt dass du scheinbar ein PHP-"Array" nachbauen willst?

Nein, ganz so ist es nicht. Ich hätte natürlich gerne ein voll funktionsfähiges PHP Array für C++ (sowie einiges anderes), allerdings ist das vermutlich unmöglich, oder? Jedenfalls reicht mir - wie gesagt - eine unsortierte Map.

Und du solltest echt mal nach Lektüre Algorithmen & Datenstrukturen Ausschau halten, dann müsstest du nicht darüber nachgrübeln ob das Suchen nach einem Schlüssel in einer map nicht schneller geht als einer pair<key,val>-list, würdest bemerken dass dein Vorhaben nicht mehr allzu viel mit FIFO zu tun hat, dass du deine Probleme evtl auch ohne php_style_array lösen kannst, dann noch ein paar allgemeine C++-Tutorials und du würdest weniger solche Schnitzer wie oben in deinen Code basteln noch müsstest du nicht so wahnsinnige Komplexitätsängste vor boost haben....

Jaah, immer langsam.
Ich habe leider nicht die Zeit so viele C++ Tutorials zu lesen wie ich gerne möchte (Literatur habe ich schon genug angehäuft). Ich gebe gerne zu dass ich mit C++ vielleicht über meine Kenntnisse hinaus programmiere (bin bei sowas immer etwas ungeduldig), aber irendwann muss man ja mal anfangen - immer nur irgendwelche Tutorials lesen ist langweilig. Wenn ich diese Klasse hier erstmal fertig habe dann gibt es für mich danach nur noch einfacheres zu tun. Werde dann auch wieder das ein oder andere neue Tutorial lesen bevor ich wieder mit etwas komplexem anfange.

Jetzt gäbe es jedenfalls nur noch eine Kleinigkeit die ich gerne für meine Map hätte - und zwar ein Iterator. Ich bin grade dabei den zu machen, wenn ich damit ein Problem kriege (ich befürchte mal das wird der Fall sein, zum Erstellen eigener Iteratoren habe ich bis jetzt nämlich noch nicht viel gefunden) frage ich falls es nichts ausmacht.