Speicherplatzoptimierung in eigener Datenstruktur

cocacola88

Hallo ihr C++-Freunde,
ich hab mal eine Frage an euch.

Ich habe eine Datenstruktur die ähnlich einem binären Baum funktioniert. Dabei gibt es grundsätzlich 2 verschiedene Arten von Knoten.

Knoten die "Daten" enthalten. Dabei handelt es sich immer um ein Blatt des jeweiligen Baumes
Knoten die nur zur Verknüpfung dienen und keine Daten enthalten.

Aus dieser Überlegung folgt, dass die Knoten die keine Daten enthalten auch keine Variable für diese brauchen und somit nicht unnötig Speicherplatz verwenden.
Also war meine Idee grundsätzlich 2 Knotenklassen zu implementieren,
eine Klasse mit Value-Feld und eine Klasse ohne Value-Feld.

Ohne Value

template<class NodeType>
class SequenceNode
{
  [...]
public:
  virtual bool isLeaf() 
  {
    return false;
  }

  SequenceNode<NodeType>* m_Left;
  SequenceNode<NodeType>* m_Right;
  [...]
}

Mit Value

template<class NodeType>
class SequenceNodeValue
{
  [...]
public:
  virtual bool isLeaf() 
  {
    return true;
  }

  NodeType m_Value;

  [...]
}

Soweit so gut, aber jetzt kommen die Probleme. Ich hab eine Funktion die mir die Datenstruktur kopieren soll.

SequenceNode<Type>* tree_copy(const SequenceNode<Type>* root_ptr)
{
    SequenceNode<Type>* left_ptr;
    SequenceNode<Type>* right_ptr;

    if (root_ptr == 0)
        return 0;
    else
    {
        left_ptr  = tree_copy( root_ptr->getLeft() );
        right_ptr = tree_copy( root_ptr->getRight() );
        return new SequenceNode<Type> (root_ptr->getData(), left_ptr, right_ptr);
    }
}

Hier muss ich einen Pointer auf die Basisklasse übergeben. Eine Methode getData() gibt es aber nur in der abgeleiteten Klasse SequenceNodeValue, da auch nur hier Daten vorhanden sind.

Wie bekomme ich es hin, dass ich in meinen internen Knoten keinen Speicherplatz für ein Datenfeld verschwende, dass ich gar nicht brauche, da ich meine Daten nur in den Blättern speichern möchte ?

Ich hoffe ihr versteht was ich meine.

volkard

Ich bin nicht sicher, aber mir scheint, clone() kann Dein Problem lösen.
http://www.cplusplus.com/forum/articles/18757/

cocacola88

Danke schon Mal,

mit dem clone-Pattern bekomme ich das Problem mit dem Kopieren auf jeden Fall in den Griff, allerdings wird das ganze dann an einer anderen Stelle noch problematisch. Ich denke mit einem dynamic_cast würde ich das Problem an dieser Stelle auch in den Griff bekommen, allerdings vermute ich, dass ich evtl. durch ein anderes Design das ganze besser machen könnte und dabei nicht auf einen cast zurückgreifen muss.

Es gibt in der Datenstruktur eine Klasse über die ein Schreibzugriff auf die Elemente der Sequenz realisiert wird.

class SequenceTempNode
{
public:
    SequenceTempNode& operator=(const Type& crArg)
    {
        if(m_IteratorPtr->get() != 0)
        {
            if(!m_IteratorPtr->isTreeCopyNecessary())
            {
                m_IteratorPtr->get()->setData(crArg);
            }
            else
            {
                typename Sequence<Type>::Iterator tmpIterOldTree = m_SequencePtr->begin();
                SequenceNode<Type>* newTree = tree_copy(m_SequencePtr->getRoot());
                m_SequencePtr->changeRoot(newTree);

                typename Sequence<Type>::Iterator tmpIterNewTree = m_SequencePtr->begin();
                while(m_IteratorPtr->get() != tmpIterOldTree.get())
                {
                    ++tmpIterOldTree;
                    ++tmpIterNewTree;
                }

                m_IteratorPtr = &tmpIterNewTree;
                m_IteratorPtr->get()->setData(crArg);
            }
        }
        return *this;
    }

    operator Type() const
    {
        return m_IteratorPtr->get()->getData();
    }

    operator Type()
    {
        return m_IteratorPtr->get()->getData();
    }

private:
    Sequence<Type>* m_SequencePtr;
    typename Sequence<Type>::BasicIterator* m_IteratorPtr;

    SequenceNode<Type>* tree_copy(const SequenceNode<Type>* root_ptr)
    {
        [...]
    }

    void operator=(const SequenceTempNode&);
    void operator*();
    void operator,(const SequenceTempNode&);
};

Die Methode get() befindet sich im BasicIterator

SequenceNode<Type>* get()
{
    if(!m_IteratorStack.empty())
          return m_IteratorStack.back().m_FirstElement;
    else
          return 0;
}

Da sind z.B. die beiden Typkonvertierungsoperatoren. Intern kann ich auf jeden Fall annehmen, dass diese nur für Knoten aufgerufen werden die auch ein Datenfeld haben. Allerdings arbeite ich mit einem Pointer auf die Basisklasse in der diese Methoden nicht zur Verfügung stehen und damit bekomme ich einen Compilerfehler. Dynamic_Cast würde das Problem beseitigen. Ebenso im Zuweisungsoperator, wenn ich dort get()->setData() aufrufe hab ich auf jeden Fall eine Blattknoten, aber ebenso nur einen Pointer auf die Basisklasse.

Kann mir jemand sagen ob ich durch irgend ein anderes Klassendesign die Probleme umgehen kann ?
Ansonsten muss ich wohl den von mir unbeliebten cast einsetzen.

Vielen Danke schonmal