Есть ли способ эффективно добавлять позиции к узлам в двоичном дереве?

Question

В следующем фрагменте кода C ++ вызовет ли Position::left() многократно создание нескольких объектов для Node, на который указывает v->left, каждый раз, когда вызывается эта функция? Эта память эффективна или есть лучший способ сделать это?

struct Node {                   // a node of the tree
          Elem    element;              // element value
          Node*   par;                  // parent
          Node*   left;                 // left child
          Node*   right;                // right child
          Node() : elt(), par(NULL), left(NULL), right(NULL) { } // constructor
        };    

    class Position {
        private:
            Node *v;
        public:
            Position(Node *_v = NULL) : v(_v) {}

            Elem &operator*() { return v->element; }
            Position left() const { return Position(v->left); }
        }

Answer 1

Position::left, поскольку он использует v->left без проверки на ноль, будет продолжаться до тех пор, пока он вызывается. Таким образом, производительность менее важна, чем безопасность.

Тем не менее, ваш class Position делает очень мало поверх struct Node. Это кажется ненужным (и в действительности скрывает поля типа par).

Чего вы пытаетесь достичь sh здесь?