Container mit lazy subsets: wie Veränderung erkennen?

otze

Hallo,

Für unser Projekt bastlen wir gerade an einem Container mit besonderen Anforderungen: gespeichert werden sehr viele, zum Teil große Daten (Zum Beispiel eine Menge von Bildsequenzen). Von diesen Containern sollen subsets gebildet werden können. In unserer jetzigen Implementation verwenden wir dazu einfache indexsets, die das Subset erzeugen. Das Haupset besitzt also einen kompletten Satz indizes und alle subsets (und subsets dieser subsets) eine Untermenge. Dies soll so lange gelten, bis entweder die Eltern oder die Kinder verädnert werden. In dem Fall sollen die Daten kopiert werden, damit Veränderungen des einen Subsets nicht die Eltern oder Geschwister verändern.

Nun haben wir das Folgende Problem:

Container<Bar> parent(...);
std::generate(parent.begin(),parent.end(),foo);//Daten erzeugen a)
Container<Bar> child;
std::vector<unsigned int> indizes;
parent.createSubset(indizes,child);//lazy subset! alle Daten referenzieren direkt auf parent

//ausgeben des subsets b)
foreach(Bar& v, child)
    std::cout<<v<<std::endl;

//in place transformation c)
std::transform(child.begin(),child.end(),child.begin(),fooBar);

Die Container sollen STL conform sein, also wenn die STL algorithmen benutzt werden sollen, soll das gehen a). Hier ist das auch kein Problem, weil noch keine Kidner da sind und ich nicht darauf achten muss, sie zu ändern.
Auch b) soll gehen, und zwar ohne dass das subset kopiert wird. Es besteht ja kein Grund dafür. Aber wie kann ich b) von c) unterscheiden?

Hat jemand eine Lösung dafür? Ich tendiere momentan zu: das geht nicht. Kann man das Design irgendwie sinnvoll abändern, dass ich möglichst wenige Einschränkungen habe und trotzdem keine 1000 programmierer mir die Bude einrnenen, weil sie sich ihre Daten zerschossen haben?

Ich überlege mir, ob ich Subsets nicht doch einen anderen Datentyp gebe. Dann kann ich sagen, dass sie immer nur konstante Referenzen zurückgeben. Will der Benutzer dann eine Datentransformation machen, kann er sie einfach mit transform in einen anderen Container schieben. Allerdings würde das zusätzliche Klassen bedeuten...

Michael E.

Entweder merken die Bars, dass sie geändert werden oder die Iteratoren geben nur Proxys zurück. Bei letzteren wärst du nicht vor direkten Zugriffen auf die einzelnen Elemente des Containers geschützt.

Würde es sich lohnen, bei Änderungen an einem Objekt wirklich nur dieses eine Objekt zu duplizieren und zu ändern? Die Referenzen auf die anderen Objekte des Parents könnten bestehen bleiben.

CStoll

Ein Ansatz wäre es, wenn die Container-Iteratoren etwas zurückliefern, was sich wie eine Element-Referenz verhält, aber bei Schreibversuchen dazwischengreifen kann:

class reference
{
private:
  Container& basis;
  ...
  reference(Container& b,/*...*/);
  void check_container();//nötige Maßnahmen für die Copy-On-Write Behandlung
public:
  operator const T&() const;
  //wenn ein neuer Wert zugewiesen wird, mußt du auf jeden Fall eine Kopie anlegen:
  reference operator=(const T&)
  {
    check_container();
    ...
  }
  ...
};

class iterator
{
  ...
public:
  T operator*() const;
  reference operator*();
  ...
};

(nur grob aus dem Gedächtnis zusammengezimmert)

otze

Proxys funktioneiren leider nicht, weil die Bar keine einfachen Datentypen sind, bzw frei wählbar. Wenn ich also sowas mache wie

child.begin()->changeThis();

Dann kriege ich das wieder nicht mit. Aber Danke für deinen Ansatz.

Würde es sich lohnen, bei Änderungen an einem Objekt wirklich nur dieses eine Objekt zu duplizieren und zu ändern?

Nein, wahrscheinlich nicht. Meistens wird direkt das ganze Set verädnert. Deswegne konnten wir vorher

child.transform(fooBar);

bzw haben eine Methode, die das Set unabhängig von den anderen macht. Aber zusammen mit dem STL-Algorithmen ist das alles viel zu fehleranfällig - auch wnen ich normalerweise den Programmierer nicht vor ihm selbst retten will, da sist einfach zu unintuitiv.

CStoll

otze schrieb:

Proxys funktioneiren leider nicht, weil die Bar keine einfachen Datentypen sind, bzw frei wählbar. Wenn ich also sowas mache wie
child.begin()->changeThis();
Dann kriege ich das wieder nicht mit. Aber Danke für deinen Ansatz.

Die -> Operatoren deines Iterators kannst du auch überladen. Und im Ernstfall mußt du vermutlich ohnehin pessimistisch an die Sache herangehen - wenn du nicht feststellen kannst, ob ein Aufruf das darunterliegende Set ändert, dann gehst du lieber davon aus daß er es tut.
(da hat man lieber eine eigentlich nicht benötigte Kopie als ein Aliasing, das den gesamten Programmablauf kaputtmacht)

otze

Was wären denn alternativen im Design?

Momentan schaue ich, ob sowas funktionieren könnte:

//nur skizziert
//die Klasse erledigt die komplette Speicherverwaltung und subseterzeugung. 
//Die davon
//abgeleiteten Klassen überschreiben nur kleine Dinge
template<class T>
class ImmutableContainer{
public:
   const T* begin()const;
   const T* end()const;
   const T* begin();//immutable
   const T* end();//immutable

};
template<class T>
class ContainerView: public ImmutableContainer<T>{
    //...
};
template<class T>
class Container: public ImmutableContainer<T>{
     //erzeugt deep copy
     explizit Container(const ImmutableContainer<T>&);
     const Container& operator=(const ImmutableContainer<T>&);
     //...
     //explizite überladung, da der Container AUCH mutable ist
     T* begin();
     T* end();
};

//Nun Anwendung

template<class T>
void printContainer(const ImmutableContainer<T>&){
    foreach(Bar& v, child)
        std::cout<<v<<std::endl;
}

Container<Bar> parent(...);
std::generate(parent.begin(),parent.end(),foo);//klappt

ContainerView<Bar> child;//anderer Typ für subsets
std::vector<unsigned int> indizes;
parent.createSubset(indizes,child);

printContainer(parent);//klappt
printContainer(child);//dito

std::transform(child.begin(),child.end(),child.begin(),fooBar); //verboten
Container<Bar> copyChild(...);
std::transform(child.begin(),child.end(),copyChild.begin(),fooBar); //klappt!
copyChild = child;
std::transform(copyChild.begin(),copyChild.end(),copyChild.begin(),fooBar); //klappt!

Das einzige Problem wa sjetzt noch bleibt ist, wenn jemand nach erzeugen von child den parent verändert. Aber das wird wohl nicht passieren.

Anregungen?

//edit eventuell könnte ich ImmutableContainer weg lassen und dafür Container von ContainerView ableiten. spart eine Basisklasse. Und ist vielleicht semantisch angenehmer.