Template Übung: Eigenen vector pogrammieren

PuppetMaster2k

Hallo zusammen!

Ich beschäftige mich erst seit kurzem mit Templates und habe mir gedacht, als Übung könnte ich mal einen eigenen vector programmieren. Allerdings stoße ich da schon auf ein Problem bei push_back(). Zu Testzwecken habe ich natürlich auch ein Programm geschrieben, das meinen vector füllen soll und natürlich die Daten auch wieder ausgibt. Und bei der Ausgabe kam dann folgender Fehler:

Groesse <-- myvec(5) wird instanziiert
5
Ausgabe
0
1
2
3
4

push_back <-- hier füge ich 5,6,7,8,9 hinzu
Groesse
10
Ausgabe
4425472 <-- hier sollte eigentlich 0 stehen
4425472 <-- und hier 1
2
3
4
5
6
7
8
9

Ich habe gefunden wann/wo der Fehler auftritt und zwar

(Hier mein Template in Kurzfassung)

template<typename T> class myvec
{
    private:
    T *m_data;
    size_t m_size;

    public:
    //Std-Ctor
    myvec(void)
        : m_size(0)
    { }

    //Ctor 1
    myvec(int size)
        : m_size(size)
    {
	    m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = 0;
        }
    }

    //Destruktor
   ~myvec()     { delete [] m_data; }

    //Index-Operator
    T& operator[] (size_t i) const	{ return m_data[i]; }

    //Element anhängen
    void push_back(const T& data)
    {
        ++m_size;
	    T* tmp = new T[m_size]; 
        for(int i = 0; i<m_size-1; ++i)
        {
            tmp[i] = m_data[i]; //<-- hier kann ich das erste mal sehen das 0 und 1 nicht mehr vorhanden sind
        }

        tmp[m_size-1] = data;
        m_data = tmp;

	    delete [] tmp;
    }
};

Dieser Fehler tritt auf, nachdem ich das 6. Element (in dem Fall also den Wert 5) hinzufüge.

Meine Frage nun, woran liegt es? Fehlerhafte Speicher-Alloziierung? Oder was anderes?

MFK

Dein Programm verwendet nicht zufällig den (automatisch generierten) Copy-CTor deines Vectors? Der ist nämlich falsch.

PuppetMaster2k

Ich habe für meinen Vector den Copy-Ctor sowie den op= überladen.

//Copy-Ctor
    myvec(const myvec &vec)
    {
    	m_size = vec.m_size;
        m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = vec.m_data[i];
        }
    }

    //Operator=
    T& operator= (const myvec& vec) const
    {
        m_size = vec.m_size;
        m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = vec.m_data[i]
        }

        return (*this);
    }

Aber wie stelle ich fest ob er jetzt den automatisch generierten oder meinen nimmt?

PuppetMaster2k schrieb:

...
void push_back(const T& data)
    {
	...
        m_data = tmp;
	delete [] tmp;
    }
...

An dieser Stelle löscht du dein neu alloziertes Array und nicht das alte. Also eher so machen:

delete [] m_data;
m_data = tmp;

Im großen und ganzen zeigt dieser Code, wie man einen vector nicht implementieren sollte. Da du jedoch nur Templates lernen wolltest, ist es nicht so schlimm.

PuppetMaster2k

Ponto schrieb:

An dieser Stelle löscht du dein neu alloziertes Array und nicht das alte. Also eher so machen:
delete [] m_data;
m_data = tmp;

Danke, das war's. Ich hab gar nicht dran gedacht, das ich so ja das flasche array lösche.

Ponto schrieb:

Im großen und ganzen zeigt dieser Code, wie man einen vector nicht implementieren sollte.

Aber wie könnte man es denn besser (richtig) machen? Ich habe mir zwar schon die Sourcen von vector angesehen, werde aber nocht nicht so ganz schlau aus allem.

Für ein Beispiel oder einen Hinweis wäre ich dankbar

Shade Of Mine

template<typename T> class myvec
{
    private:
    T *m_data;
    size_t m_size;

    public:
    //Std-Ctor
    myvec(void)
        : m_size(0)
    { }

    //Ctor 1
    myvec(int size)
        : m_size(size)
    {
	    m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = 0; //wieso 0 ? das verkraftet zB myvec<std::string> nicht.
        }
    }

    //Destruktor
   ~myvec()     { delete [] m_data; }
   //macht PENG bei myvec<int>(); weil data irgendwohin zeigt

    //Index-Operator
    T& operator[] (size_t i) const	{ return m_data[i]; }

    //Element anhängen
    void push_back(const T& data)
    {
        ++m_size;
	    T* tmp = new T[m_size]; 
        for(int i = 0; i<m_size-1; ++i)
        {
            tmp[i] = m_data[i]; //<-- hier kann ich das erste mal sehen das 0 und 1 nicht mehr vorhanden sind
        }

        tmp[m_size-1] = data;
        delete [] m_data;
        m_data = tmp;
    }
    //std::copy statt der schleife verwenden

//Copy-Ctor
    myvec(const myvec &vec)
    {
        m_size = vec.m_size;
        m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = vec.m_data[i];
        }
//std::copy statt der schleife
    }

    //Operator=
    T& operator= (const myvec& vec) const
    {
        m_size = vec.m_size;
        m_data = new T[m_size];
        for(int i = 0; i<m_size; ++i)
        {
            m_data[i] = vec.m_data[i]
        }

        return (*this);
    }
    //wieso ist der const? das geht doch garnicht... und der returntype passt auch nicht
    //abgesehen davon, implementiert man den op= mit dem copyctor
    /*
myvec const& operator=(myvec other)
{
  swap(other);
  return *this;
}

void swap(myvec& vec)
{
  std::swap(m_data, vec.m_data);
  std::swap(m_size, vec.m_size);
}
*/

};

Weiters solltest du die initialisierungsliste nützen.

aber alles-in-allem nicht so schlecht.

eine konkurrenz zu std::vector oder STL konform ist er zwar nicht, aber als Übung ganz OK.

interpreter

Mal ne generelle Frage:
In den ganzen selbstimplementierten TemplateContainern sehe ich immer sowas:
T* value;

Aber ist das nicht ungeschickt? Wenn ich jetzt z.b. nen Container mit n Elementen eines Objekttyps erstelle (myContainer<Objekttyp> mc(n)), dann werden doch automatisch n Konstruktoren aufgerufen, obwohl ich ja nur SPEICHER für n Objekte brauche. Ich würde es so machen:
T** value; und dann im Konstruktor Speicher für n Pointer allokieren.

Ist das nicht besser?

PuppetMaster2k

@Shade
Danke für die Infos/Änderung

Das nächste was bei mir ins Haus kommt wird ein Buch über Templates und STL sein, da ich leider noch keins habe und Templates in meinen C++ Buch nur stiefmütterlich behandelt werden.

interpreter schrieb:

Mal ne generelle Frage:
In den ganzen selbstimplementierten TemplateContainern sehe ich immer sowas:
T* value;

Aber ist das nicht ungeschickt? Wenn ich jetzt z.b. nen Container mit n Elementen eines Objekttyps erstelle (myContainer<Objekttyp> mc(n)), dann werden doch automatisch n Konstruktoren aufgerufen, obwohl ich ja nur SPEICHER für n Objekte brauche. Ich würde es so machen:
T** value; und dann im Konstruktor Speicher für n Pointer allokieren.

Ist das nicht besser?

Wenn du einen Container mit n Elementen haben willst, dann solltest du auch für diese n Elemente einen Konstruktor aufrufen. Wenn du jedoch nur einen Container haben willst der anfangs Kapazität für n Elemente bereitstellt aber keine enthält so allozierst du am Anfang nur Speicher für n Elemente. Den uninitialisierten Speicher erhälst du zum Beispiel durch operator new, malloc oder den Allokator deiner Wahl. Später werden dann die Objekte in diesen Speicher hineinkonstruiert. Dies geht mit placement new oder std::uninitialized_fill().

Das alles geht wunderbar mit einem T *, auch wenn es besser ist den rohen Speicher vom Container zu kapseln.

Jester

Kann es sein, daß Dein op= ein Speicherloch enthält? Der alte Speicher wird nicht freigegeben. Von Selbstzuweisung wollen wir mal nicht sprechen.
Shade's Lösung mit dem Copy-Ctor umgeht alle diese Probleme und ist zusätzlich noch exception-sicher.

MfG Jester

PuppetMaster2k

Ich habe mittlerweile alles schon angepasst. Ob da ein Speicherloch entsteht habe ich so noch gar nicht getestet, da ich erst das Problem mit push_back lösen wollte.
Da ich aber weder in der Schule noch in meinem Buch etwas darüber gelesen habe, das man den op= normalerweise über den Copy-Ctor implementiert, habe ich halt die noch hier beschriebene Vorgehensweise verwendet, sie aber nich getestet.

Auch das Problem mit der Selbstzuweisung habe ich schon gelöst (was mir erst beim testen aufgefallen ist)

myvec const& operator= (myvec other)
{
    if(this != other)
    {
        myvec<T> temp(other);
        swap(temp);
    }
    return (*this);
}