STL Set - Werte ändern per Iterator?



  • Hallo,

    kann in einem std::set durch einen Iterator ein Wert (oder Schlüssel) verändert werden?

    std::set<int> s;
    s.insert(1);
    s.insert(2);
    
    (*s.find(1)) = 3;
    


  • Was soll daran nicht gehen?



  • Naja, VC motzt...

    Gleich wird wieder gefragt - Hier bitte:

    #include <set>
    #include <iostream>
    using namespace std;
    
    int main() {
        std::set<int> s;
        s.insert(1);
        s.insert(2);
    
        (*s.find(1)) = 3;	
    
        system("pause");
    }
    

    Fehler (Zeile 10):

    error C3892: 'std::_Tree<_Traits>::find' : you cannot assign to a variable that is const
    


  • Nein, den Schlüssel darfst du nicht ändern, weil das Sortierprädikat davon abhängt. Durch Ändern der Werte könntest du das Set intern durcheinanderbringen, sodass die Klasseninvarianten (stets sortiert) nicht mehr aufrecht erhalten werden.

    Falls du das wirklich machen musst, kommst du wohl um ein Herausnehmen und Neu Einfügen nicht herum.



  • Nexus schrieb:

    Nein, den Schlüssel darfst du nicht ändern, weil das Sortierprädikat davon abhängt. Durch Ändern der Werte könntest du das Set intern durcheinanderbringen, sodass die Klasseninvarianten (stets sortiert) nicht mehr aufrecht erhalten werden.

    Falls du das wirklich machen musst, kommst du wohl um ein Herausnehmen und Neu Einfügen nicht herum.

    Da stimmt schon, aber ich habs bei mir auch getestet VC 2008 Prof. und da gehts. Finde ich auch intuitiver, weil das entfernen/neu einfügen irgendwie logisch ist bei einer Menge also kann er das auch gleich selbst tun. Bin mir allerdings nicht sicher, was der Standard dazu sagt (nicht nachgeschaut).
    Ist ja eigentlich nicht dein Problem, was jetz die Datenstruktur genau macht, wenn du etwas ändern möchtest. Man bekommt ja auch keinen const_iterator zurück, also gehe ich davon aus, dass der Standard das durchaus auch erlaubt.



  • Habe gerade den entsprechenden Passus der Referenz nicht zur Hand, aber Nicolai Josuttis erklärt in seinem Buch "The C++ Standard Library: A Tutorial and Reference" p182 Folgendes zu Iteratoren von sets und multisets:

    Nicolai Josuttis schrieb:

    ...
    More important is the constraint that, from an iterator´s point of view, all elements are considered constant. This is necessary to ensure that you can´t
    compromise the order of the elements by changing their values. However, as a result you can´t call any modifying algorithm on the elements of a set or
    multiset.
    ...

    Nexus hat also völlig recht.



  • drakon schrieb:

    Da stimmt schon, aber ich habs bei mir auch getestet VC 2008 Prof. und da gehts.

    Nein, tuts nicht. Wenn du den Schlüssel veränderst, dann macht es die Sortierung kaputt. Und es gibt kein Sprachmittel in C++, sodass das Set davon Wind kriegen könnte(zumindest keins, dass im Interface von set erlaubt wäre).

    teste es doch mal: füge die ersten 100 Zahlen ins set ein. Dann ändere die 50 oder so auf den Wert 105. Und dann schau mal, ob du sie mit find noch finden kannst. Gib dann mal das Set mit einem Iterator aus.



  • otze schrieb:

    drakon schrieb:

    Da stimmt schon, aber ich habs bei mir auch getestet VC 2008 Prof. und da gehts.

    Nein, tuts nicht. Wenn du den Schlüssel veränderst, dann macht es die Sortierung kaputt. Und es gibt kein Sprachmittel in C++, sodass das Set davon Wind kriegen könnte(zumindest keins, dass im Interface von set erlaubt wäre).

    teste es doch mal: füge die ersten 100 Zahlen ins set ein. Dann ändere die 50 oder so auf den Wert 105. Und dann schau mal, ob du sie mit find noch finden kannst. Gib dann mal das Set mit einem Iterator aus.

    Ok. Kann sein. Ich habe es nicht so gründlich getestet und nur mit dem Debugger geschaut, ob das Element korrekt drin war und es war dann geändert drin.
    Warum gibt find denn da kein const_iterator zurück?

    Wenn dein Verfahren so funktioniert, dann halte ich das für sehr unsauber. Man kann die Invariante des Objektes zerstören und man kommt es nicht mitüber?! Sehr fahrlässig meiner Meinung nach.



  • drakon schrieb:

    Warum gibt find denn da kein const_iterator zurück?

    Weil du bei nem const_iterator auch nicht das zugehörige Datum ändern könntest...
    Imho gabs auch mal ne Diskussion, wie man mit nem const_iterator trotzdem löschen kann - bin ich mir allerdings nicht mehr sicher...

    bb



  • unskilled schrieb:

    drakon schrieb:

    Warum gibt find denn da kein const_iterator zurück?

    Weil du bei nem const_iterator auch nicht das zugehörige Datum ändern könntest...

    Was für ein Datum bei einem set? Der Schlüssel ist das Datum..



  • drakon schrieb:

    unskilled schrieb:

    drakon schrieb:

    Warum gibt find denn da kein const_iterator zurück?

    Weil du bei nem const_iterator auch nicht das zugehörige Datum ändern könntest...

    Was für ein Datum bei einem set? Der Schlüssel ist das Datum..

    oh - war von map ausgegangen - mein fehler^^



  • Herr Kreft & Fr.Langer haben mit 'Are Set Iterators Mutable or Immutable' einen recht umfangreichen Artikel zum Thema verfasst.

    Gruß
    Werner



  • Werner Salomon schrieb:

    Herr Kreft & Fr.Langer haben mit 'Are Set Iterators Mutable or Immutable' einen recht umfangreichen Artikel zum Thema verfasst.

    Gruß
    Werner

    Habs gerade aus dem anderen Thread gelesen. 😉 Danke für den Link!
    (btw: du weisst das vlt. gerade: das ist üblicherweise ein AVL Baum, oder?)

    Sehr interessant, auch wenn ich es wirklich ein wenig ungeschickt finde. Allerdings ist es wohl kaum besser zu beheben.

    unskilled hatte zu einem Teil schon (unabsichtlich) Recht. 😉 - Ich habe da irgendwie die Menge zu mathematisch als einfache Objekte angesehen, aber es können natürlich auch Objekte sein, wo man dann etwas ändern kann, was nichts zur Ordnung beiträgt, darum muss es auch eine nicht konstante Version geben.



  • drakon schrieb:

    Ok. Kann sein. Ich habe es nicht so gründlich getestet und nur mit dem Debugger geschaut, ob das Element korrekt drin war und es war dann geändert drin.
    Warum gibt find denn da kein const_iterator zurück?

    Wenn dein Verfahren so funktioniert, dann halte ich das für sehr unsauber. Man kann die Invariante des Objektes zerstören und man kommt es nicht mitüber?! Sehr fahrlässig meiner Meinung nach.

    Sag mir, wie du es lösen würdest.

    Nur const_iteratoren zu erlauben, scheint im ersten Augenblick zwar eine naheliegende Lösung zu sein, stellt jedoch nicht wirklich eine Option dar. Damit werden nämlich sämtliche Modifikationen am Objekt verunmöglicht, darunter auch jene, die im Bezug auf das Sortierkriterium irrelevant sind. Damit würde der std::set -Container einiges an Flexibilität einbüssen. Hingegen wäre eine Wrapper-Klasse, die lediglich const -Zugriff erlaubt, leicht zu implementieren.

    Das Problem ist, dass du keine Implementierung für std::set und std::multiset schreiben kannst, welche intelligent genug ist, um zwischen akzeptablen und gefährlichem Zugriff auf die Elemente zu unterscheiden. Also muss diese Aufgabe dem Benutzer überlassen werden.

    Edit: Hab deinen Beitrag erst jetzt gesehen...



  • Mir wurde das Problem bewusst, während ich den Beitrag gelesen habe. Habe vorher eben nie nachgedacht wie jetzt das set aufgebaut ist (was man als User ja nicht unbedingt müssen sollte), aber als mir klar wurde, dass es ja ein Baum mit beliebigen Objekten ist, war es eigentlich klar, dass es nicht so einfach geht.

    Eine Lösung liesse sich wahrscheinlich schon finden, welche dann aber mit grosser Wahrscheinlichkeit nicht wirklich konsistent mit den anderen Container Klassen wäre.



  • Selbst wenn man eine halbwegs generische Lösung fände, müsste man dem Container manuell mitteilen, welche Operationen erlaubt sind und welche nicht. Für den entsprechenden Aufwand kann man sich geradeso gut nach konventionellen Möglichkeiten umsehen oder wie die meisten Programmierer einfach gar nichts tun (d.h. bei modifizierendem Zugriff achtsam sein).



  • Nexus schrieb:

    Selbst wenn man eine halbwegs generische Lösung fände, müsste man dem Container manuell mitteilen, welche Operationen erlaubt sind und welche nicht.

    Partial const objects. Alle Datenobjekte, welche in einer bestimmten Funktion (hier z.B '<') benutzt werden, müssen const sein. Bei einem Objekt, was in einem set gespeichert werden soll macht das sogar richtig viel Sinn.
    Das wäre doch mal was. 🙂

    Das könnte man vielleicht sogar irgendwie bereits hinbringen. Vielleicht ist die Idee gar nicht so verrückt, wie ich im ersten Moment gedacht habe..



  • drakon schrieb:

    Partial const objects. Alle Datenobjekte, welche in einer bestimmten Funktion (hier z.B '<') benutzt werden, müssen const sein.

    Also würde iterator keinen Schreibzugriff auf diese erlauben? Und du müsstest auch einen neuen Qualifizierer für Zeiger und Referenzen anbieten, damit man den Iterator dereferenzieren kann. Allerings wäre es unklug, in der Klasse einzelne Methoden damit kennzuzeichnen, da man möglicherweise verschiedene Sortierkriterien zu einem Typ haben möchte. Was schlussendlich wieder darauf hinausläuft, dass man sortierkriteriums-spezifisch qualifizieren muss.

    Wahrscheinlich wäre es doch etwas verrückt... 😉



  • Nexus schrieb:

    drakon schrieb:

    Partial const objects. Alle Datenobjekte, welche in einer bestimmten Funktion (hier z.B '<') benutzt werden, müssen const sein.

    Also würde iterator keinen Schreibzugriff auf diese erlauben?

    Es würde am Iterator Konzept nichts ändern. Das nichts falsches geschieht kommt automatisch damit, dass die Variablen konstant sind und man sie folglich mit keiner Funktion ändern kann. Ein Iterator kann genau das gleiche tun, wie sonst auch.

    Und du müsstest auch einen neuen Qualifizierer für Zeiger und Referenzen anbieten, damit man den Iterator dereferenzieren kann. Allerings wäre es unklug, in der Klasse einzelne Methoden damit kennzuzeichnen, da man möglicherweise verschiedene Sortierkriterien zu einem Typ haben möchte. Was schlussendlich wieder darauf hinausläuft, dass man sortierkriteriums-spezifisch qualifizieren muss.

    Ich denke an so etwas hier:

    class element [is partial const with '<']
    {
     public:
      element (int key ): key_ ( key ), foo( 0 ) {}
      bool operator < (const element& other)
      {
        // return foo_ < other.foo_; // compiler Fehler
        return key_ < other.key_;
      }
     private:
     const int key_;
     int foo_;
    };
    

    Und ein set nimmt dann nur Typen an, welche partial const auf '<' sind.
    Das ganze sollte für ein Compiler nicht allzu schwer zu implementieren sein. Einfach die in den genannten Funktionen benutzten Typen anschauen, ob sie const sind oder nicht und eine entsprechende Meldung ausgeben.

    Gäbe so natürlich noch Probleme damit Objekte, welche keine Instanzen von Klassen sind zu handhaben, aber das könnte man bestimmt auch irgendwie zufriedenstellend lösen.

    In wiefern sich so etwas lohnen würde ist eine andere Frage. Ist ja nur ein Gedankenexperiment, wie man es lösen könnte. 😉


Log in to reply