list, erase

[unskilled]

hallo...

ich habe eine liste geschrieben(für die uni, sonst hätt ich schon std::list genommen ^^) und habe jetzt ein Problem mit dem erase...
Die Signatur hat ja so auszusehen:

iterator erase(const_iterator where)

aber wie würdet ihr aus dem const_iterator dann nen iterator machen?
Mein const_iterator sieht so in etwa aus:

struct const_iterator : /*typedefs, operatoren, ...*/
{
public:
 //operatoren, copyctor, ...
private:
  const node *data;

  const_iterator(const node *_data) : data(_data) {}
//meine liste ist als friend eingetragen, weil dieser ctor ja nicht von außen aufgerufen werden sollte...
};

Iterator ist analog dazu - nur eben ohne die beiden const `s

Mein erase würde ich so in etwa schreiben:

template <typename T>
typename list<T>::iterator list<T>::erase(const_iterator to_delete)
{
  const iterator after( static_cast<node*>(to_delete.data->next) );
  _erase(to_delete.data, to_delete.data->prev, after);
  return after;
}

Der static_cast ist nötig, da ich auch 2 dummy-nodes habe (anfang und ende) und deshalb immererst von dem dummy-node zum richtigen node casten muss...

edit (hatte das prob ganz vergessen zu schildern): das problem hier ist natürlich, dass ich noch nen const_cast einbauen müsste - aber iwann wirds ja auch mal hässlich... und ich dachte, dass es vll ne bessere möglichkeit geben würde ^^

Mein const_iterator hat auch nen ctor für iteratoren - aber umgedreht find ich es ein wenig komisch.. Ich hab auch mal bissl in der MSVC-Standard-Lib gesucht - soweit ich das dort gesehen habe, hat dort der const_iterator aber kein const node -Pointer sondern einen "normalen" node-Pointer - wie eben der normale Iterator auch... Würdet ihr das auch so machen? Oder wie sähe eure Lösung aus?

bb

[Dravere]

1. Nach bisherigem Standard erwartet std::list::erase ein iterator :
http://www.cplusplus.com/reference/stl/list/erase/

2. Derzeit sieht es so aus, dass im nächsten Standard dies abgeändert und ein const_iterator erwartet wird.

3. Die Implementierung der Std-Lib des MSVC erwartet heute schon ein const_iterator .

4. In der Std-Lib zum MSVC hat man es sich einfach gemacht und den iterator von const_iterator abgeleitet. Der MSVC setzt hier also bewusst auf Slicing.

5. Ich würde bereits nach dem neuen Standard gehen und ein const_iterator erwarten und wohl auch so ähnlich lösen, wie es in der Std-Lib des MSVC gelöst ist. Obwohl die Frage durchaus ein wenig berechtigt ist, ob ein iterator wirklich auch ein const_iterator ist (is-a Beziehung).

6. Zwei alternativen wären wohl:
- Die Verbindung von den beiden Iteratoren über friend und dann in const_iterator einen Konstruktor zur Verfügung stellen, welcher einen iterator erwartet. Vom iterator wird dann der Zeiger auf den Node geholt.
- Den const_iterator so zu entwerfen, dass er nur als Wrapper um einen iterator dient. Ähnlich wie der Wrapper für reverse_iterator .

Grüssli

[unskilled]

Du würdest also insbesondere const_iterator keinen const-Pointer sondern einen normalen(mutable) Pointer halten lassen?!

Oder würdest du im CTor von iterator, der const_iterator erwartet, dann einfach nen const_cast machen? (darf man das dort dann überhaupt, ohne darüber nachdenken zu müssen? ich denk ja schon, aber sicher bin ich mir im Moment nicht ^^)

Das mit dem mutable Pointer gefällt mir nicht so recht, weil man imho bei jeder const-methode, die einen iterator wiedergibt erst das const wegcasten müsste?! (z.bsp. begin() und end() )

und dann hab ich mit diesem konzept an sich ein problem:
ich habe eine klasse, die eine liste oder was auch immer als member hat - und ich gebe dem anwender eine funktion, die ihm nen const_iterator zurückgibt - aber jz kann er diesen const_iterator eben doch in nen iterator umwandeln -.- Man kann dem User also nicht mehr eindeutig zeigen, dass er seine Griffeln von dem Container lassen soll... So denkt er sich bestimmt: const_iterator : ich darf also alles machen, was ich damit machen kann - also kann ich auch das Objekt löschen und hab außerdem dann auch gleich noch nen iterator des nächsten Elements...

Spätestens, wenn bis-jetzt-Member-Funktionen der Container als freie Funktionen implementiert werden - wie dies ja im nächsten Standard passieren sollte, oder hab ich mir da was falsch gemerkt?

bb

[Dravere]

Weder mutable noch const_cast sind mit allen drei Lösungen nötig.

1. Ein const_iterator ist nicht konstant, sondern worauf er verweist ist konstant. Du kannst allerdings einen normalen Zeiger oder sowas nehmen, also einen Zeiger auf ein nicht konstantes Objekt, und die konstante Eigenschaft einfach durch die Funktionen/Rückgabewerte hervorrufen.

2. Ich sagte ein const_iterator hat einen Konstruktor, welcher einen iterator aufnimmt. Somit würde ein Zeiger auf ein nicht konstantes Objekt and einen Zeiger auf ein konstantes Objekt übergeben werden, absolut kein Problem.

3. Nicht der Iterator sagt was im Container passiert, sondern der Container sagt es. Der Iterator hat nur die Kontrolle über das Element. Allerdings, wie ich schon im Punkt 1 gesagt habe, soll nicht die Konvertierung von einem const_iterator in einen iterator möglich sein, sondern genau der umgedrehte Fall.

4. Lies alles nochmals genau durch. Ich habe ein wenig das Gefühl, dass du ein paar Dinge durcheinander bringst. Was ist genau const, wer hat die Kontrolle, in welche Richtungen kann man konvertieren? Notfalls macht dir eine Skizze

Grüssli

[unskilled]

Dravere schrieb:

Weder mutable noch const_cast sind mit allen drei Lösungen nötig.

ich meinte mutable im Gegensatz zu const und nicht das keyword ^^

Ich glaube, wir haben ein wenig aneinander vorbeigeredet - die konvertierung von iterator in const_iterator ist mir klar und die besteht auch jetzt schon... (womit 1.+2. sich erledigt hätten ^^)
allerdings hatte ich ein prob, aus dem const_iterator, den erase bekommt nen normalen iterator zu machen - aber das löse ich wohl jz auch, indem ich kein const node pointer sondern nen non-const pointer speicher...
allerdings wird es dann ja schon wieder doof, die begin() und end() funktionen zu implementieren!?

iterator begin()
{
  return iterator( static_cast<node*> (m.anchor_begin.next) );
}

const_iterator begin() const
{
  return const_iterator( static_cast<node*> (m.anchor_begin.next) );
  //erwartet nen node*, bekommt aber nen const node*, da const-fkt...
}

die const-methode würde jetzt noch einen zusätzlichen const-cast benötigen, da const_iterator ja kein const-node pointer mehr erwartet, weil er nur noch nen non-const pointer speichert?!
Wie du um den rumkommen möchtest, ist mir noch immer unklar...

zu 3. nochmal:
aber mit erase hat man ja dann im endeffekt die umwandlung von einem const_iterator in einen (anderen) iterator ...

bb

[Dravere]

unskilled schrieb:

Ich glaube, wir haben ein wenig aneinander vorbeigeredet - die konvertierung von iterator in const_iterator ist mir klar und die besteht auch jetzt schon... (womit 1.+2. sich erledigt hätten ^^)

Nicht wirklich, dieser Satz betrifft nur Punkt 2.

unskilled schrieb:

allerdings hatte ich ein prob, aus dem const_iterator, den erase bekommt nen normalen iterator zu machen - aber das löse ich wohl jz auch, indem ich kein const node pointer sondern nen non-const pointer speicher...

Das hier dagegen betrifft Punkt 1.

unskilled schrieb:

allerdings wird es dann ja schon wieder doof, die begin() und end() funktionen zu implementieren!?

Ehm, nö.

class TestClass
{
private:
  int* m_intPtr;

  // ...

public:
  int* get_int_ptr() const
  {
    // Hier ist m_intPtr vom Typ: int* const
    // Der Zeiger ist konstant nicht das Objekt, worauf er zeigt.

    // Das folgende geht also ohne Probleme:
    return m_intPtr;
  }
}

unskilled schrieb:

zu 3. nochmal:
aber mit erase hat man ja dann im endeffekt die umwandlung von einem const_iterator in einen (anderen) iterator ...

Du meinst hier wohl über den Rückgabewert, oder?
Das spielt jedenfalls keine Rolle. Ein Iterator ist nur ein Verweis auf ein Objekt. Wenn du den Iterator an erase übergibst, ist das Objekt sowieso weg. Was du zurückbekommst, ist ein Iterator auf das nächste Objekt. Dieser Iterator ist natürlich kein konstanter Verweis, denn wenn du ein erase auf einen Container aufrufen kannst, dann hast du einen nicht-konstanten Container. Man darf also die Elemente des Containers modifizieren.

Ganz davon abgesehen, da du den nicht-konstanten Container hast, könntest du sogar den Wert, auf welcher dein const_iterator verweist, ändern gehen. Einmal std::distance , und dann einen normalen iterator holen und einmal std::advance .

Grüssli

[unskilled]

Aber folgendes geht leider nicht:

struct TestClass
{
	struct base
	{
		base *next;
		base *prev;
	};

	struct node : base
	{
		int data;
	};

	struct _m
	{
		base a;
	} m;

	node* get() const
	{
		return static_cast<node*> (&m.a);
//		return const_cast <node*> ( static_cast<const node*> (&m.a) );
	} 
};

int main()
{
	TestClass tmp;
	TestClass::node* x = tmp.get();
}

erzeugt

MSVC schrieb:

error C2440: 'static_cast' : cannot convert from 'const TestClass::base *' to 'TestClass::node *'

das meinte ich mit const_cast - oder mach ich da was falsch?!
es liegt offensichtlich daran, dass ich die member an sich in dem struct gekapselt habe... brauch ich aber, weil ich 2 dummy-knoten habe und die nach jedem ctor aufeinander zeigen sollen - also hab ich _m einfach nen standard-ctor gegeben und ruf den in jedem ctor auf (was zwar eigtl gar nicht nötig ist, aber ich habs trotzdem mal gemacht )...

bb

[Dravere]

Du könntest den Dummyknoten dynamisch erzeugen oder verpass dem Dummyknoten Objekt das Keyword mutable .

Grüssli

[unskilled]

Dravere schrieb:

Du könntest den Dummyknoten dynamisch erzeugen...

und somit wäre der standard-ctor nich mehr exception-safe...
außerdem find ich es unnötig...

Dravere schrieb:

oder verpass dem Dummyknoten Objekt das Keyword mutable .

hab ich auch schon dran gedacht, erschien mir aber irgendwie so unelegant...
du würdest wohl mutable nutzen?!

bb

edit: oder würdest du den const_cast lassen? eigtl taucht der im kompilierten programm ja so und so nicht mehr auf, oder? außerdem sollte da ja auch nichts schief gehen können, oder? ^^

[Dravere]

Ob ich den Dummyknoten dynamisch oder per mutable anlegen würde, ist schwer zu sagen. Ich tendiere allerdings zu dynamisch.

Es gibt von mir aus gesehen ein Killerargument gegen die mutable Lösung:

int main()
{
  yourlib::list<MassiveObject> list;

  return 0;
}

Wenn MassiveObject wirklich ein zu grosses Objekt ist, dann hast du hier plötzlich einen Stackoverflow. Es ist zwar ein eher theoretisches Problem, aber ich sehe zu wenig Vorteile bei der mutable Lösung, welche mich dazu bringen würden, das Risiko dieses theoretischen Problems einzugehen.

Zur Exceptionsicherheit:
Wieso sollte der Konstruktor nicht mehr exceptionsicher sein? Wenn man die Sache richtig umsetzt, dann ist das doch ohne Probleme möglich. Wo siehst du hier ein Problem?

Grüssli

[unskilled]

Dravere schrieb:

[...] Stackoverflow [...]

Die Dummy-Knoten beinhalten aber keine Daten - nur einen Zeiger auf next und prev... so könnte es auch keinen Stackoverflow geben, oder seh ich das falsch?

Dravere schrieb:

Wieso sollte der Konstruktor nicht mehr exceptionsicher sein?

weil ich dann 2 new s hätte?!

bis jetzt sieht der Standard-CTor so aus:
_m() : anchor_begin(&anchor_end, nullptr), anchor_end(nullptr, &anchor_begin) {}

danach würde er dann nicht nur nicht mehr so schön gehen sondern zusätzlich dazu könnte an 2 Stellen eine exception fliegen...

_m() : anchor_begin(nullptr), anchor_end(new base_node)
{
  anchor_begin = new base_node(anchor_end, nullptr);
  anchor_end->prev = anchor_begin;
  anchor_end->next = nullptr;
}

die nullptr sind zwar nicht notwendig und ich könnte einfach den random-wert drin stehen lassen, aber darin sehe ich keinen vorteil...
und der ctor ist so noch nicht mal exception-safe...

wenn ich so drüber nachdenke, denke ich fast, dass ich die lösung mit dem const_cast lasse - da er (imho) genau 0takte kostet und niemals konstante daten geändert werden. Somit sollte es auch nicht undefiniertes verhalten liefern können - selbst, wenn der compiler konstante daten in irgend nen read-only speicher schreiben sollte... Richtig?

bb

[Dravere]

unskilled schrieb:

Die Dummy-Knoten beinhalten aber keine Daten - nur einen Zeiger auf next und prev... so könnte es auch keinen Stackoverflow geben, oder seh ich das falsch?

Ah, sorry, da habe ich nicht genug weit mitgedacht. Habe selber noch nie eine Liste mit Dummyknoten implementiert
Die paar zusätzlichen ifs, welche dann nötig sind, waren mir bisher immer egal.

Dann sieht aber mutable durchaus lecker aus

unskilled schrieb:

weil ich dann 2 new s hätte?!

Ja und? Man könnte zum Beispiel einen scoped_ptr nehmen, wäre sowieso nicht so verkehrt. Nur weil man zwei news hat, heisst das doch nicht, dass man den Konstruktor nicht Exception sicher machen kann.

unskilled schrieb:

bis jetzt sieht der Standard-CTor so aus:
_m() : anchor_begin(&anchor_end, nullptr), anchor_end(nullptr, &anchor_begin) {}

Geht sowas überhaupt laut Standard? Da bin ich mir jetzt gar nicht so sicher. Es sollte doch eine Reihenfolge zu beachten sein. Zumindest dürfte es hier eine Warnung geben, ähnlich wie wenn man this in der Intialisierungsliste verwendet.

unskilled schrieb:

wenn ich so drüber nachdenke, denke ich fast, dass ich die lösung mit dem const_cast lasse - da er (imho) genau 0takte kostet und niemals konstante daten geändert werden. Somit sollte es auch nicht undefiniertes verhalten liefern können - selbst, wenn der compiler konstante daten in irgend nen read-only speicher schreiben sollte... Richtig?

Sofern du dir da ganz sicher bist, dass niemand anderes oder auch du "ausversehen" das Objekt doch verändert, weil du oder der andere sich nicht daran erinnert, dass der Zeiger auf ein nicht konstantes Objekt eigentlich ein Zeiger auf ein konstantes Objekt ist.

Ich mag const_cast nicht, da würde ich eher mutable nehmen, da es das Design sicherer macht.

Grüssli

[unskilled]

Dravere schrieb:

unskilled schrieb:

bis jetzt sieht der Standard-CTor so aus:
_m() : anchor_begin(&anchor_end, nullptr), anchor_end(nullptr, &anchor_begin) {}

Geht sowas überhaupt laut Standard? Da bin ich mir jetzt gar nicht so sicher. Es sollte doch eine Reihenfolge zu beachten sein. Zumindest dürfte es hier eine Warnung geben, ähnlich wie wenn man this in der Intialisierungsliste verwendet.

Nö - die Adresse steht ja schon fest - und was anderes verwende ich ja nicht... kommt auch keine Warnung...

Dravere schrieb:

unskilled schrieb:

wenn ich so drüber nachdenke, denke ich fast, dass ich die lösung mit dem const_cast lasse - da er (imho) genau 0takte kostet und niemals konstante daten geändert werden. Somit sollte es auch nicht undefiniertes verhalten liefern können - selbst, wenn der compiler konstante daten in irgend nen read-only speicher schreiben sollte... Richtig?

Sofern du dir da ganz sicher bist, dass niemand anderes oder auch du "ausversehen" das Objekt doch verändert, weil du oder der andere sich nicht daran erinnert, dass der Zeiger auf ein nicht konstantes Objekt eigentlich ein Zeiger auf ein konstantes Objekt ist.

Ja, ich bin mir sicher, dass niemand was verändert... wenn das Objekt an sich const ist, dann wird bei begin() und end() ein const_iterator erzeugt und man kann nur über advance oder so nen iterator draus machen - aber das ist ja immer so ^^ ansonsten hat man keine möglichkeiten, das objekt zu ändern...

Dravere schrieb:

Ich mag const_cast nicht, da würde ich eher mutable nehmen, da es das Design sicherer macht.

Hmm... mutable sieht immer so hässlich aus : D
Da nehm ich lieber irgendwo nen const_cast, den so und so niemand sieht

bb

Danke für deine Hilfe und Geduld

[Dravere]

unskilled schrieb:

Nö - die Adresse steht ja schon fest - und was anderes verwende ich ja nicht... kommt auch keine Warnung...

Problem wäre aber sowas:

class Inner
{
  int x;

public:
  Inner(Inner* other)
    : x(0)
  {
    other->x = 4;
  }
}

class Outer
{
  Inner a, b;

public:
  Outer()
    : a(&b) // Hier würde dem x in b 4 zugewiesen werden,
            // Obwohl das Objekt gar noch nicht konstruiert ist.
    , b(&a)
  {
  }
}

Klar, bei dir ist das nicht der Fall, weil du nur den Zeiger abspeicherst, aber deswegen dachte ich, dass zumindest eine Warnung kommen würde, denn der Kompiler wird sicher nicht genau nachprüfen, was mit dem Zeiger passiert. Er könnte es zum Teil sogar gar nicht.

unskilled schrieb:

Hmm... mutable sieht immer so hässlich aus : D
Da nehm ich lieber irgendwo nen const_cast, den so und so niemand sieht

Naja, ist deine Entscheidung ...

Grüssli

[unskilled]

jopp - aber auch bei deinem bsp bekomm ich mit dem msvc auf w4 keine warning...
warnt gcc bei sowas?

bb