Frage zu STL und Iterator

Hallo!

(Bevor jetzt jemand auf die Verwendung von vector verweist - ich mach das ganze um die STL genauer kennenzulernen)

Ich versuche gerade eine Klasse zu programmieren, welche STL mäßig aufgebaut ist, also Container sowie Iterator. Und darauf möchte ich dann die Algorithmen der STL anwenden.

Nun hab ich ganz einen einfachen Container gestrickt welcher Objekte vom Typ T in einem dynamischen Array aufnehmen kann.
Innerhalb des Containers habe ich weiters eine Iterator Klasse definiert.

template<class T>
class myArray
{
 ...
 public:
 class iterator
 {
  ...
  T* current;
  ...
 }
 ...
};

Nun zur Frage: Wie schaffe ich es, den Iterator insowfern intelligent zu machen, dass er nicht über den Array Bereich hinausläuft?
Also z.B. im Falle:

iterator& operator++()
{
    current++;
    return *this;
}

Wäre die dahinterliegende Datenstruktur eine einfach verkettete Liste, so wäre die Abfrage ja einfach: zuerst prüfen ob man bereits am Listenende angekommen ist, und wenn ja, dann wird der Iterator nicht mehr erhöht, er bleibt also bei end() stehen.
Weiters wäre eine gewisse Intelligenz wünschenswert beim Dereferenzieren, also beim operator*(). Ich möchte in dem Fall vermeiden, dass auf end() zugegriffen werden kann - da hier außerhalb des reservierten Speicherbereichs zugegriffen wird.

Hat jemand eine Idee, wie ich es schaffe, dass der Iterator mehr Informationen über das Objekt erhält, über das er gerade iteriert, sodass ich die erwähnten Schutzmechanismen einbauen kann?

volkard

template<class T>
class myArray
{
 ...
 public:
 class iterator
 {
  ...
  T* current;
  ...
#ifdef DEBUG
   myArray& theArray;
#endif
 }
 ...
};

Dann kannste testen, was Du magst.

Nagut, dann stellt sich aber noch die Frage:
Wie bekomme ich die Referenz auf die "umgebende" Klasse.
Container und Iteratorklasse sind ja verschachtelt.
Und somit kann die innere Klasse ja nur auf statische Vars der äußeren Klasse zugreifen!?

in main siehts ungefähr so aus:

//Container
myArray<int> array(10);

//und dazu iterator holen
myArray<int>::iterator iter=array.begin();

/*iter zeigt mir nun auf ein element, aber um den iterator mit intelligenz auszustatten müsste der iterator ja etwas mehr wissen über die umgebende klasse.
also sowas in der art:
*/
myArray<int>::iterator iter(array);

/*irgendwie schaffen es die STL Container und Iteratoren ja auch, z.B. vector.
und das ohne diese komische initialisierung wie in der oberen codezeile mit iter(array)*/

Steh grad aufm Schlauch...

cooky451

Hä? Du übergibst *this in my_array.begin(), ist doch klar?

cooky451 schrieb:

Hä? Du übergibst *this in my_array.begin(), ist doch klar?

War ja klar dass das so einfach ist
Danke!

krümelkacker

...wobei das Objekt mit einer Referenz als Element nicht vernünftig zuweisbar wird. Das ist natürlich für einen Iterator kein Zustand.

Ich habe festgestellt, dass man für Zeiger-artige Objekte eher Zeiger-Elemente verwenden sollte und für Referenz-artige Objekte (Proxies & co) eher Referenzen als Elemente. Bedenke dabei den vom Compiler eventuell generierten Zuweisungsoperator.

Der std::reference_wrapper ist dabei eher ein komischer Mischmasch. Manchmal verhält sich das Ding wie ein Zeiger, manchmal wie eine Referenz. Wenn ich einem reference_wrapper<int> einen anderen reference_wrapper<int> zuweise, dann verhalten sie sich Zeiger-artig. Wenn ich einem reference_wrapper<int> einen int zuweise, dann verhält sich das Ding Referenz-artig. Damit beides funktioniert, muss ein reference_wrapper aber einen Zeiger speichern.

volkard

krümelkacker schrieb:

...wobei das Objekt mit einer Referenz als Element nicht vernünftig zuweisbar wird. Das ist natürlich für einen Iterator kein Zustand.

Da habe ich ausnahmsweise mal & benutzt, um anzuzeigen, daß der pointee grundsätzlich am Leben sein muss, und ich kriege gleich Haue.

krümelkacker schrieb:

Ich habe festgestellt, dass man für Zeiger-artige Objekte eher Zeiger-Elemente verwenden sollte und für Referenz-artige Objekte (Proxies & co) eher Referenzen als Elemente.

Boah, wie soll ich ein Gefühl dafür entwickeln, was "referenz-artig" ist? Ich vermute fast, ich sollte generell Zeiger bevorzugen und Referenzen meiden.

krümelkacker

Zeiger-artig: Ein Iterator
(ist selbst ein Objekt, kann man dazu bringen auf andere Objekte zu zeigen, indem man Iteratoren tauscht, einander zuweist, operator++ benutzt, etc etc etc)

Referenz-artig: Z.B. vector<bool>::reference
Das Objekt soll eine Referenz emulieren. Zuweisungsn beziehen sich immer auf das referenzierte Objekt. Dementsprechend ist eine Referenz als Element praktisch, um Zeiger-Semantik zu umgehen; denn wenn ich

myboolvec[3] = myboolvec[4];

schreibe, will ich, dass sich der Vektor ändert und nicht das temporäre "Referenzobjekt". Eine Referenz lässt sich ja normalerweise nicht mehr umbiegen. Mit einer Referenz als Element fällt auch gleich der vom Compiler generierte Zuweisungsoperator weg, den wir hier ja eh nicht brauchen.

Hallo!

Hab die Klasse mit Container+Iterator jetzt fertig.
Derzeit nur bidirectional Iterator, werd ich aber noch erweitern auf random access. Funktioniert auch soweit ich das jetzt getestet habe.

Könnt ihr mal kurz über den Code drüber schauen und sagen, was nicht passt und was ihr anders machen würdet?
Bin wie schon gesagt beim C++ lernen und freue mich daher über jedes Feedback!

template<class T>
class safeArray
{
    public:
        typedef T value_type;
        typedef T* pointer;
        typedef T& reference;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;

        safeArray(const size_t count)
        :m_count(count)
        {
            m_array=new T[m_count];
        }

        virtual ~safeArray()
        {
            delete[] m_array;
        }

        safeArray(const safeArray& original)
        :m_count(original.m_count)
        {
            m_array=new T[m_count];

            for(size_t i=0;i<m_count;i++)
                m_array[i]=original.m_array[i];
        }

        safeArray& operator=(const safeArray& rhs)
        {
                safeArray temp(rhs);

                std::swap(m_array,temp.m_array);
                std::swap(m_count,temp.m_count);
                return *this;
        }

        void print() const
        {
            for(size_t i=0;i<m_count;i++)
                std::cout<<m_array[i]<<std::endl;
        }

    private:
        T* m_array;
        size_t m_count;

    public:
        class iterator
        {
            public:
                typedef std::bidirectional_iterator_tag iterator_category;
                typedef T value_type;
                typedef T* pointer;
                typedef T& reference;
                typedef size_t size_type;
                typedef ptrdiff_t difference_type;

                iterator(const safeArray* refSafeArray, const size_t index)
                :m_refToSafeArray(refSafeArray)
                {
                    if(index>=0 && index<=m_refToSafeArray->m_count)
                        m_current=index;
                    else
                        m_current=m_refToSafeArray->m_count;
                }

                T& operator*()
                {
                    return m_refToSafeArray->m_array[m_current];
                }

                const T& operator*() const
                {
                    return m_refToSafeArray->m_array[m_current];
                }

                iterator& operator++()
                {
                    if(m_current<m_refToSafeArray->m_count)
                        m_current++;
                    return *this;
                }

                iterator operator++(int)
                {
                    iterator temp(*this);
                    ++(*this);

                    return temp;
                }

                iterator& operator--()
                {
                    if(m_current>0)
                        m_current--;
                    return *this;
                }

                iterator operator--(int)
                {
                    iterator temp(*this);
                    --(*this);

                    return temp;
                }

                const bool operator==(const iterator& iterSecond) const
                {
                    return m_current==iterSecond.m_current;
                }

                const bool operator!=(const iterator& iterSecond) const
                {
                    return m_current!=iterSecond.m_current;
                }

            private:
                size_t m_current;
                const safeArray* m_refToSafeArray;
        };

        iterator begin() const
        {
            return iterator(this,0);
        }

        iterator end() const
        {
            return iterator(this,m_count);
        }
};

volkard

Default-Konstruktor sollte her, damit man so Dinger selber wieder in Arrays stopfen kann.

Destruktor nicht virtual. Von sowas soll man nicht erben.

Was passiert, wenn in der Elementzuweisung im Kopierkonstruktor eine Exception fliegt?

print sollte '\n' statt std::endl benutzen.

sollte if(index>=0 && index<=m_refToSafeArray->m_count) nicht if(index>=0 && index<m_refToSafeArray->m_count) heißen?

Ebenso return iterator(this,m_count); wohl return iterator(this,m_count-1);

Aber was DU da fabrizierst, ist höchst bedenklich. Du verschleierst damit nur Programmierfehler bei der Array-Bedienung! Prüfen ist gut. Aber dann hart herausgehen. Am besten mit sowas wie assert.

LordJaxom

volkard schrieb:

sollte if(index>=0 && index<=m_refToSafeArray->m_count) nicht if(index>=0 && index<m_refToSafeArray->m_count) heißen?

Ebenso return iterator(this,m_count); wohl return iterator(this,m_count-1);

Sollten Ende-Iteratoren nicht eins hinter das letzte Element zeigen?

volkard

LordJaxom schrieb:

Sollten Ende-Iteratoren nicht eins hinter das letzte Element zeigen?

Ups, ja. Dann sind die beiden korrekt.
Aber dann kann ich ins Nirvana schreiben.

hi,

wie kann ich den iterator bis zum letzten element laufen lassen?
tree::treeiterator it = t.begin(); it != t.end(); it = it.next()

class tree
{
private:
	class node *root;

public:
	class treeiterator
	{
	private:
		std::stack<class node*> stack;
		class node *now;
		class node *end;
		class tree *ptree;
		bool left;
		bool right;

	public:
		treeiterator(class tree *tree_): now(NULL), left(false), right(false)
		{
			ptree = tree_;
		}

		void start_at_beginning()
		{
			now = ptree->get_root_node();
			stack.push(now);
		}

		void start_at_end()
		{
			now = ptree->get_root_node();
			std::stack<class node*> stack_tmp;

			while(true)
			{
				if(now->left) 
				{
					stack_tmp.push(now->right); 
				}
				if(now->right)
				{
					stack_tmp.push(now->left); 
				}

				if (!stack_tmp.empty()) 
				{ 
					now = stack_tmp.top(); 
					stack_tmp.pop(); 
				} 
				else
				{
					break;
				}
			}
		}

		class node *get_node()
		{
			return now;
		}

		treeiterator &next() // next iterator for Depth first Search
		{
			if (now->left) 
			{
				stack.push(now->right); 
			}
			if (now->right) 
			{
				stack.push(now->left); 
			}
			if (!stack.empty()) 
			{ 
				now = stack.top(); 
				stack.pop(); 
			}
			else
			{
				now = NULL;
			}

			return *this;
		}

		bool operator== (treeiterator &it)
		{
			return this->get_node() == it.get_node();
		}

		bool operator!= (treeiterator &it)
		{
			return this->get_node() != it.get_node();
		}

		node operator*()
		{
			return *get_node();
		}
	};

public:
	tree(): root(NULL) {}

	class node *get_root_node()
	{
		return root;
	}

	class treeiterator begin()
	{
		class treeiterator it(this); 
		it.start_at_beginning(); 
		return it;
	}

	class treeiterator end()
	{
		class treeiterator it(this); 
		it.start_at_end(); 
		return it;
	}
};

for(tree::treeiterator it = t.begin(); it != t.end(); it = it.next())
	{
		cout << it.get_node()->value;
	}

Default-Konstruktor sollte her, damit man so Dinger selber wieder in Arrays stopfen kann.

Ok. Könnte ich ja ganz einfach einbauen mit einem Default-Argument im Ctor.

Destruktor nicht virtual. Von sowas soll man nicht erben.

Ok. Was ist das Problem wenn man unnötigerweise virtual verwendet? Nur unnötiger Overhead durch die vtables oder wie die heißen oder auch sonst noch Probleme?

Was passiert, wenn in der Elementzuweisung im Kopierkonstruktor eine Exception fliegt?
Tja, gute Frage.
Wenn ich ein try catch mache, welches mir im catch Block dann den neuen Speicher wieder freigibt, und ich dann normal weitermache, so bekomm ich beim dtor ein Problem weil mir delete[] Speicher freigeben will denn es nicht mehr gibt!?
Was wäre die Lösung? Vielleicht Speicher=0 setzen nach delete[] und dies im Dtor nochmals prüfen bevor ich mit delete[] drüberfahre?

safeArray(const safeArray& original)
        :m_count(original.m_count)
        {
            m_array=new T[m_count];

            for(size_t i=0;i<m_count;i++)
                m_array[i]=original.m_array[i];
        }

print sollte '\n' statt std::endl benutzen.

OK.

**
sollte if(index>=0 && index<=m_refToSafeArray->m_count) nicht if(index>=0 && index<m_refToSafeArray->m_count) heißen?

Ebenso return iterator(this,m_count); wohl return iterator(this,m_count-1);**

s.o. wegen end() = eins hinter letztem Element.
Naja, iter=end; iter=value; sollte ich ja verhindern, stimmt schon ("ins Nirvana schreiben").
Also wenn ich beim operator() merke, dass an einer Stelle dereferenziert wird, die nicht im gültigen Bereich liegt, raus mit Exception/assert?

Aber was DU da fabrizierst, ist höchst bedenklich. Du verschleierst damit nur Programmierfehler bei der Array-Bedienung! Prüfen ist gut. Aber dann hart herausgehen. Am besten mit sowas wie assert.

Wie meinst du das genau?
Sobald also ein in irgendeiner Weise falscher Zugriff aufs safeArray erfolgt sofort Exception werfen? Viel "radikaler" mit falschen Zugriffen umgehen?

volkard

stl mal wieder schrieb:

Wie meinst du das genau?
Sobald also ein in irgendeiner Weise falscher Zugriff aufs safeArray erfolgt sofort Exception werfen? Viel "radikaler" mit falschen Zugriffen umgehen?

Sogar assert statt exceptions. ~(Wobei ich ein heimlicher Freund von AssertExceptions bin.)~

safeArray(const size_t count)
        :m_count(count)
        {
            m_array=new T[m_count];
        }

const unsinnig
size_t schlecht, verbirgt minuszahlenfehler

safeArray(int count)
        :m_count(count)
        {
            assert(count>=0);
            m_array=new T[m_count];
        }

Auch beim

if(index>=0 && index<=m_refToSafeArray->m_count)

kann sollte evtl aus diesem Gund index wohl ein int sein.
Ok, absolut unüblich für Arrays. Aber man sieht noch schneller, ob's eine Unter- oder Überschreitung war.

Ja, das virtual macht nur ein Bißchen lahmer, schadet aber ansonsten gar nicht.

volkard

stl mal wieder schrieb:

Was wäre die Lösung? Vielleicht Speicher=0 setzen nach delete[] und dies im Dtor nochmals prüfen bevor ich mit delete[] drüberfahre?

Nee! Mach sowas nicht. Das ist am Ende auch nicht sicherer.
Überhaupt setze ich nie nach dem delete irgend einen Zeiger auf 0.

Du könntest mit try/catch schauen, ob eine Exception geflogen ist, gegebenenfalls löschen und sie weiterwerfen.
Oder Du faßt den Speicher dort mit einem Smart-Pointer an, der im Exceptionfall löscht.

TyRoXx

volkard schrieb:

size_t schlecht, verbirgt minuszahlenfehler
safeArray(int count)
        :m_count(count)
        {
            assert(count>=0);
            m_array=new T[m_count];
        }
Auch beim
if(index>=0 && index<=m_refToSafeArray->m_count)
kann sollte evtl aus diesem Gund index wohl ein int sein.
Ok, absolut unüblich für Arrays. Aber man sieht noch schneller, ob's eine Unter- oder Überschreitung war.

Nicht dein Ernst?

RHBaum

Ok. Was ist das Problem wenn man unnötigerweise virtual verwendet? Nur unnötiger Overhead durch die vtables oder wie die heißen oder auch sonst noch Probleme?

1. Technik:
ja, du erzeugst ne vtable, wo keine sein muss, und nimmst dem compiler damit evtl. auch Optimierungsmöglichkeiten.

2. Philosophie:
(alle wissen es !? aber keiner weiss wo es steht ! ^^ also quasi ungeschriebenes Gesetz!) Du gibst anderen Nutzern mit einem virtuellen Dtor zu verstehen, das deine Klasse hervorragend zum Ableiten geeignet ist ... oder so ähnlich ^^ und genau das ist eigentlich nicht der Fall ... Das klasseninterface an sich ist ok, aber es ist alles andere als "gut zum Ableiten" geeignet
Deine Klasse ist als Implementation, also zum (wieder)verwenden designt, da ist Aggregation / Komposition Mittel der Wahl.
Polymorphie, sollte der Hauptanwendungsfall von Vererbung sein, also das austauschen von typen zur laufzeit (zur compilezeit sind Templates meist die bessere Wahl), und das willst du mit deiner klasse glaub ich nicht erreichen ^^

Ciao ...

volkard

Naja, schwupps, habe ich eine Klasse PersistentesArray von safeArray abgeleitet, die als zuätzliches Attribut einen Dateinamen als String hat und im Konstruktor die Datei liest und im Destruktor die Datei schreibt.
Zu Aggregation habe ich keine Lust, weil ich das ganze Zugriff-Geraffele per Hand weiterleiten müßte.
Erbe ich normalerweise nicht von Containern, weil sie normalerweise keinen virtuellen Destruktor haben oder ist es umgegehrt?

@RHBaum: Vor allem Punkt 2 ist ein gutes Argument, danke für die Ausführungen.

@volkard: Nochwas zu den assert's:

iterator(const safeArray* refSafeArray, int index)
                :m_refToSafeArray(refSafeArray)
                {
                    assert(index>=0 && index<=m_refToSafeArray->m_count);
                    m_current=index;
                }

Jetzt habe ich da einen Vergleich zwischen signed und unsigned.
Und: Woher weiß ich, dass size_t int und nicht long oder long long ist?
Oder ist size_t definitionsgemäß unsigned int?