Árbol iterativo rojo-negro (pila dinámica) -- ++ campo con tree campo con memory-management camp codereview Relacionados El problema

Iterative Red-Black Tree (dynamic stack)


4
vote

problema

Español

He reelaborado completamente el código anterior, publicado aquí , de modo que sea un poco más correcto con respecto a la gestión de la memoria dinámica, y también un poco más fieles al paradigma orientado a objetos.

  /** A program for Red-Black Tree manipulation: insertion and value retrieval.   * All position relations (first, last, previous, next) are in-order.   */  class RBTree {     struct Node {         enum class Colour : bool { RED, BLACK };         int value;         Node *left, *right, *parent;         Colour colour;     public:         Node* getGrandparent() const;         Node* getUncle() const;         void setLeft(Node*);         void setRight(Node*);     };     class Iterator {         class Stack {             Node **buffer;             int size, top;         private:             void resize();         public: // Member 'buffer' is initialized like this because the program doesn't catch/handle exceptions.             Stack() : size(16), buffer(new Node*[size]), top(0) {}             void push(Node*);             Node* pop();             Node* peek();             void clear();             bool isEmpty() const;             ~Stack() { delete[] buffer; } // ?         public:             Stack(const Stack&);             Stack(Stack&&);             Stack& operator = (const Stack&);             Stack& operator = (Stack&&);         };         Stack stack;         const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified.         Node* pointer;     public:         Iterator(const RBTree*);         void first();         void next();         void last();         void reset();         void to(Node*);         Node* getNode() const;         bool operator != (const Iterator&) const;     };     Node *root;     Iterator iterator; private:     void attachValue(int);     void resolve();     void rotateLeft(Node*);     void rotateRight(Node*);     void setRoot(Node*);     void deleteTree(); public:     RBTree() : root(nullptr), iterator(this) {}     bool insertValue(int);     Node* findValue(int);     bool printTree() const;     ~RBTree() { deleteTree(); } public: // This section ensures that tree can neither be copied nor initialized with another tree, only built with insertion.     RBTree(const RBTree&) = delete;     RBTree(RBTree&&) = delete;     RBTree& operator = (const RBTree&) = delete;     RBTree& operator = (RBTree&&) = delete; };  // TREE // public: //  // Retruns {false} if value already exists. bool RBTree::insertValue(int p_value) { if (findValue(p_value) == nullptr) {         attachValue(p_value);         resolve();         return true;     }     else         return false; }  // Returns {nullptr} if value doesn't exist. RBTree::Node* RBTree::findValue(int p_value) {     Node *node = root, *parent = nullptr;     while (node != nullptr) {         if (p_value < node->value) {             parent = node;             node = node->left;         }         else if (p_value > node->value) {             parent = node;             node = node->right;         }         else             return node;     }     if (parent != nullptr)         iterator.to(parent);     return nullptr; }  bool RBTree::printTree() const {     if (root != nullptr) {         // print using in-order iteration         return true;     }     else         return false;  }  // TREE // private: //  // Attaches the given value under the current node (referenced by member 'iterator'). void RBTree::attachValue(int p_value) {     Node *node = new Node;     (*node) = { p_value, nullptr, nullptr, nullptr, Node::Colour::RED };     if (root == nullptr) {         root = node;         return;     }     Node *parent = iterator.getNode();     iterator.reset();     if (p_value < parent->value)         parent->setLeft(node);     else         parent->setRight(node);     iterator.to(node); }  // Resolves the invalid states. void RBTree::resolve() {     int case_number = 1;     Node *node = iterator.getNode();     iterator.reset();     if (node == nullptr)         node = root;     do {         switch (case_number) {             case 1: {                 if (node->parent == nullptr) {                     node->colour = Node::Colour::BLACK;                     return;                 }             }             case 2: {                 if (node->parent->colour == Node::Colour::BLACK)                     return;             }             case 3: {                 Node *uncle = node->getUncle();                 if (uncle != nullptr && uncle->colour == Node::Colour::RED) {                     Node *grandparent = node->getGrandparent();                     node->parent->colour = Node::Colour::BLACK;                     uncle->colour = Node::Colour::BLACK;                     grandparent->colour = Node::Colour::RED;                     node = grandparent;                     break;                 }             }             case 4: {                 Node *grandparent = node->getGrandparent(), *parent = node->parent;                 if (node == parent->right && parent == grandparent->left) {                     rotateLeft(parent);                     node = node->left;                 }                 else if (node == parent->left && parent == grandparent->right) {                     rotateRight(parent);                     node = node->right;                 }             }             case 5: {                 Node *grandparent = node->getGrandparent(), *parent = node->parent;                 parent->colour = Node::Colour::BLACK;                 grandparent->colour = Node::Colour::RED;                 if (node == parent->left)                     rotateRight(grandparent);                 else                     rotateLeft(grandparent);                 node = parent;                 break;             }         }     } while (case_number); }  RBTree::Node* RBTree::Node::getGrandparent() const {     if (parent != nullptr)         return parent->parent;     else         return nullptr; }  RBTree::Node* RBTree::Node::getUncle() const {     Node *grandparent = getGrandparent();     if (this == grandparent->left)         return grandparent->right;     else         return grandparent->left; }  void RBTree::rotateLeft(Node *p_node) {     Node *node = p_node;     Node *right_left = p_node->right->left;     if (p_node == root) // If root is the pivot, update the root info.         setRoot(p_node->right);     p_node = p_node->right;     if (node->parent != nullptr)         node->parent->setRight(node->right);     node->right->setLeft(node);     node->setRight(right_left);  }  void RBTree::rotateRight(Node *p_node) {     Node *node = p_node;     Node *left_right = p_node->left->right;     if (p_node == root) // If root is the pivot, update the root info.         setRoot(p_node->right);     p_node = p_node->left;     if (node->parent != nullptr)         node->parent->setLeft(node->left);     node->left->setRight(node);     node->setLeft(left_right); }  void RBTree::setRoot(Node *p_root) {     root = p_root;     root->parent = nullptr; }  void RBTree::deleteTree() {     Node *node;     for (Iterator i(this); (node = i.getNode()) != root; i.next())         delete node;     delete root; }  // NODE: Ensures the proper connection. //  void RBTree::Node::setLeft(Node *p_left) {     left = p_left;     if (p_left != nullptr)         p_left->parent = this; }  void RBTree::Node::setRight(Node *p_right) {     right = p_right;     if (p_right != nullptr)         p_right->parent = this; }  // ITERATOR //  RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {}  // Traverses to the first node (leftmost). void RBTree::Iterator::first() {     if (pointer != nullptr) {         while (true) {             if (pointer != nullptr) {                 stack.push(pointer);                 pointer = pointer->left;             }             else {                 pointer = stack.peek();                 break;             }         }     } }  // Traverses to next node in-order. void RBTree::Iterator::next() {     if (pointer != nullptr) {         if (!stack.isEmpty()) {             pointer = stack.pop();             if (pointer->right != nullptr) {                 pointer = pointer->right;                 first();             }         }     } }  // Traverses to the last node (rightmost). void RBTree::Iterator::last() {     pointer = tree->root;     if (pointer != nullptr)         while (pointer->right != nullptr)             pointer = pointer->right;     stack.clear(); }  // Returns to the first node. void RBTree::Iterator::reset() {     pointer = tree->root;     stack.clear();     first(); }  // Traverses to the given node. Stores {nullptr} if the node cannot be found. // ?? void RBTree::Iterator::to(Node *p_node) {     if (p_node == tree->root) {         pointer = p_node;         return;     }     reset();     while (pointer != p_node)         next(); }  RBTree::Node* RBTree::Iterator::getNode() const {     return pointer; }  bool RBTree::Iterator::operator != (const Iterator& p_iterator) const {     return pointer != p_iterator.pointer ? true : false; }  // STACK //  // Doubles the stack size. void RBTree::Iterator::Stack::resize() {     Node **temporary = new Node*[size <<= 1];     for (int i = 0; i < top; i++)         temporary[i] = buffer[i];     delete[] buffer;     buffer = temporary; }  // Copy constructor. RBTree::Iterator::Stack::Stack(const Stack& p_stack) : size(p_stack.size), top(p_stack.top), buffer(new Node*[p_stack.size]) {     for (int i = 0; i < top; i++)         buffer[i] = p_stack.buffer[i]; }  // Move constructor. RBTree::Iterator::Stack::Stack(Stack&& p_stack) : size(p_stack.size), top(p_stack.top), buffer(p_stack.buffer) {     p_stack.buffer = nullptr; }  // Copy assignment operator. RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (const Stack& p_stack) {     if (p_stack.buffer == this->buffer)         return *this;     size = p_stack.size;     top = p_stack.top;     Node** temporary = new Node*[size];     for (int i = 0; i < top; i++)         temporary[i] = p_stack.buffer[i];     delete[] buffer;     buffer = temporary;     return *this; }  // Move assignment operator. RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (Stack&& p_stack) {     if (p_stack.buffer == this->buffer)         return *this;     delete[] buffer;     buffer = p_stack.buffer;     p_stack.buffer = nullptr;     return *this; }  void RBTree::Iterator::Stack::push(Node *p_node) {     if (top == size)         resize();     buffer[top++] = p_node; }  RBTree::Node* RBTree::Iterator::Stack::pop() {     return isEmpty() ? nullptr : buffer[--top]; }  RBTree::Node* RBTree::Iterator::Stack::peek() {     return isEmpty() ? nullptr : buffer[top - 1]; }  void RBTree::Iterator::Stack::clear() {     top = 0; }  bool RBTree::Iterator::Stack::isEmpty() const {     return top == 0 ? true : false; }  #include <iostream>  using std::cout; using std::cin;  int main() {     RBTree tree;     int choice = 0;     cout << " Options:    1 Insert value.  2 Find value.   0 Exit.  Choice: ";     cin >> choice;     while (choice != 0) {         switch (choice) {             case 1: {                 cout << " Value = ";                 cin >> choice;                 if (tree.insertValue(choice))                     cout << "  > Insertion successful. ";                 else                     cout << "  > Insertion failed. ";                 break;             }             case 2: {                 cout << " Value = ";                 cin >> choice;                 if (tree.findValue(choice) != nullptr)                     cout << "  > Value found. ";                 else                     cout << "  > Value not found. ";                 break;             }             case 3: {                 if (tree.printTree())                     cout << "  > Print unsuccessful. ";                 else                     cout << "  > Print failed. ";                 break;             }             case 0: {                 return 0;             }             default: {                 cout << "  > Invalid option. ";             }         }         cout << " Options:    1 Insert node.  2 Find node.   0 Exit.  Choice: ";         cin >> choice;     } }   

El printTree() es un talón, todavía estoy buscando un algoritmo apropiado que utilice el recorrido en orden. Eso no es parte de esta revisión, ya que se discute aquí , en detalle. < / p>

Estoy buscando una confirmación de que el código ha mejorado lo suficiente desde la versión anterior, guiada por las respuestas que recibí en ese cargo con respecto a la encapsulación, la administración de la memoria, etc. También me agradecería si pudieras señalar He hecho algo malo al aplicar esas críticas.

Original en ingles

I've completely reworked the previous code, posted here, so that it is a bit more correct regarding dynamic memory management, and also a bit more true to the object-oriented paradigm.

/** A program for Red-Black Tree manipulation: insertion and value retrieval.   * All position relations (first, last, previous, next) are in-order.   */  class RBTree {     struct Node {         enum class Colour : bool { RED, BLACK };         int value;         Node *left, *right, *parent;         Colour colour;     public:         Node* getGrandparent() const;         Node* getUncle() const;         void setLeft(Node*);         void setRight(Node*);     };     class Iterator {         class Stack {             Node **buffer;             int size, top;         private:             void resize();         public: // Member 'buffer' is initialized like this because the program doesn't catch/handle exceptions.             Stack() : size(16), buffer(new Node*[size]), top(0) {}             void push(Node*);             Node* pop();             Node* peek();             void clear();             bool isEmpty() const;             ~Stack() { delete[] buffer; } // ?         public:             Stack(const Stack&);             Stack(Stack&&);             Stack& operator = (const Stack&);             Stack& operator = (Stack&&);         };         Stack stack;         const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified.         Node* pointer;     public:         Iterator(const RBTree*);         void first();         void next();         void last();         void reset();         void to(Node*);         Node* getNode() const;         bool operator != (const Iterator&) const;     };     Node *root;     Iterator iterator; private:     void attachValue(int);     void resolve();     void rotateLeft(Node*);     void rotateRight(Node*);     void setRoot(Node*);     void deleteTree(); public:     RBTree() : root(nullptr), iterator(this) {}     bool insertValue(int);     Node* findValue(int);     bool printTree() const;     ~RBTree() { deleteTree(); } public: // This section ensures that tree can neither be copied nor initialized with another tree, only built with insertion.     RBTree(const RBTree&) = delete;     RBTree(RBTree&&) = delete;     RBTree& operator = (const RBTree&) = delete;     RBTree& operator = (RBTree&&) = delete; };  // TREE // public: //  // Retruns {false} if value already exists. bool RBTree::insertValue(int p_value) { if (findValue(p_value) == nullptr) {         attachValue(p_value);         resolve();         return true;     }     else         return false; }  // Returns {nullptr} if value doesn't exist. RBTree::Node* RBTree::findValue(int p_value) {     Node *node = root, *parent = nullptr;     while (node != nullptr) {         if (p_value < node->value) {             parent = node;             node = node->left;         }         else if (p_value > node->value) {             parent = node;             node = node->right;         }         else             return node;     }     if (parent != nullptr)         iterator.to(parent);     return nullptr; }  bool RBTree::printTree() const {     if (root != nullptr) {         // print using in-order iteration         return true;     }     else         return false;  }  // TREE // private: //  // Attaches the given value under the current node (referenced by member 'iterator'). void RBTree::attachValue(int p_value) {     Node *node = new Node;     (*node) = { p_value, nullptr, nullptr, nullptr, Node::Colour::RED };     if (root == nullptr) {         root = node;         return;     }     Node *parent = iterator.getNode();     iterator.reset();     if (p_value < parent->value)         parent->setLeft(node);     else         parent->setRight(node);     iterator.to(node); }  // Resolves the invalid states. void RBTree::resolve() {     int case_number = 1;     Node *node = iterator.getNode();     iterator.reset();     if (node == nullptr)         node = root;     do {         switch (case_number) {             case 1: {                 if (node->parent == nullptr) {                     node->colour = Node::Colour::BLACK;                     return;                 }             }             case 2: {                 if (node->parent->colour == Node::Colour::BLACK)                     return;             }             case 3: {                 Node *uncle = node->getUncle();                 if (uncle != nullptr && uncle->colour == Node::Colour::RED) {                     Node *grandparent = node->getGrandparent();                     node->parent->colour = Node::Colour::BLACK;                     uncle->colour = Node::Colour::BLACK;                     grandparent->colour = Node::Colour::RED;                     node = grandparent;                     break;                 }             }             case 4: {                 Node *grandparent = node->getGrandparent(), *parent = node->parent;                 if (node == parent->right && parent == grandparent->left) {                     rotateLeft(parent);                     node = node->left;                 }                 else if (node == parent->left && parent == grandparent->right) {                     rotateRight(parent);                     node = node->right;                 }             }             case 5: {                 Node *grandparent = node->getGrandparent(), *parent = node->parent;                 parent->colour = Node::Colour::BLACK;                 grandparent->colour = Node::Colour::RED;                 if (node == parent->left)                     rotateRight(grandparent);                 else                     rotateLeft(grandparent);                 node = parent;                 break;             }         }     } while (case_number); }  RBTree::Node* RBTree::Node::getGrandparent() const {     if (parent != nullptr)         return parent->parent;     else         return nullptr; }  RBTree::Node* RBTree::Node::getUncle() const {     Node *grandparent = getGrandparent();     if (this == grandparent->left)         return grandparent->right;     else         return grandparent->left; }  void RBTree::rotateLeft(Node *p_node) {     Node *node = p_node;     Node *right_left = p_node->right->left;     if (p_node == root) // If root is the pivot, update the root info.         setRoot(p_node->right);     p_node = p_node->right;     if (node->parent != nullptr)         node->parent->setRight(node->right);     node->right->setLeft(node);     node->setRight(right_left);  }  void RBTree::rotateRight(Node *p_node) {     Node *node = p_node;     Node *left_right = p_node->left->right;     if (p_node == root) // If root is the pivot, update the root info.         setRoot(p_node->right);     p_node = p_node->left;     if (node->parent != nullptr)         node->parent->setLeft(node->left);     node->left->setRight(node);     node->setLeft(left_right); }  void RBTree::setRoot(Node *p_root) {     root = p_root;     root->parent = nullptr; }  void RBTree::deleteTree() {     Node *node;     for (Iterator i(this); (node = i.getNode()) != root; i.next())         delete node;     delete root; }  // NODE: Ensures the proper connection. //  void RBTree::Node::setLeft(Node *p_left) {     left = p_left;     if (p_left != nullptr)         p_left->parent = this; }  void RBTree::Node::setRight(Node *p_right) {     right = p_right;     if (p_right != nullptr)         p_right->parent = this; }  // ITERATOR //  RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {}  // Traverses to the first node (leftmost). void RBTree::Iterator::first() {     if (pointer != nullptr) {         while (true) {             if (pointer != nullptr) {                 stack.push(pointer);                 pointer = pointer->left;             }             else {                 pointer = stack.peek();                 break;             }         }     } }  // Traverses to next node in-order. void RBTree::Iterator::next() {     if (pointer != nullptr) {         if (!stack.isEmpty()) {             pointer = stack.pop();             if (pointer->right != nullptr) {                 pointer = pointer->right;                 first();             }         }     } }  // Traverses to the last node (rightmost). void RBTree::Iterator::last() {     pointer = tree->root;     if (pointer != nullptr)         while (pointer->right != nullptr)             pointer = pointer->right;     stack.clear(); }  // Returns to the first node. void RBTree::Iterator::reset() {     pointer = tree->root;     stack.clear();     first(); }  // Traverses to the given node. Stores {nullptr} if the node cannot be found. // ?? void RBTree::Iterator::to(Node *p_node) {     if (p_node == tree->root) {         pointer = p_node;         return;     }     reset();     while (pointer != p_node)         next(); }  RBTree::Node* RBTree::Iterator::getNode() const {     return pointer; }  bool RBTree::Iterator::operator != (const Iterator& p_iterator) const {     return pointer != p_iterator.pointer ? true : false; }  // STACK //  // Doubles the stack size. void RBTree::Iterator::Stack::resize() {     Node **temporary = new Node*[size <<= 1];     for (int i = 0; i < top; i++)         temporary[i] = buffer[i];     delete[] buffer;     buffer = temporary; }  // Copy constructor. RBTree::Iterator::Stack::Stack(const Stack& p_stack) : size(p_stack.size), top(p_stack.top), buffer(new Node*[p_stack.size]) {     for (int i = 0; i < top; i++)         buffer[i] = p_stack.buffer[i]; }  // Move constructor. RBTree::Iterator::Stack::Stack(Stack&& p_stack) : size(p_stack.size), top(p_stack.top), buffer(p_stack.buffer) {     p_stack.buffer = nullptr; }  // Copy assignment operator. RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (const Stack& p_stack) {     if (p_stack.buffer == this->buffer)         return *this;     size = p_stack.size;     top = p_stack.top;     Node** temporary = new Node*[size];     for (int i = 0; i < top; i++)         temporary[i] = p_stack.buffer[i];     delete[] buffer;     buffer = temporary;     return *this; }  // Move assignment operator. RBTree::Iterator::Stack& RBTree::Iterator::Stack::operator = (Stack&& p_stack) {     if (p_stack.buffer == this->buffer)         return *this;     delete[] buffer;     buffer = p_stack.buffer;     p_stack.buffer = nullptr;     return *this; }  void RBTree::Iterator::Stack::push(Node *p_node) {     if (top == size)         resize();     buffer[top++] = p_node; }  RBTree::Node* RBTree::Iterator::Stack::pop() {     return isEmpty() ? nullptr : buffer[--top]; }  RBTree::Node* RBTree::Iterator::Stack::peek() {     return isEmpty() ? nullptr : buffer[top - 1]; }  void RBTree::Iterator::Stack::clear() {     top = 0; }  bool RBTree::Iterator::Stack::isEmpty() const {     return top == 0 ? true : false; }  #include <iostream>  using std::cout; using std::cin;  int main() {     RBTree tree;     int choice = 0;     cout << "\nOptions: \n\n 1 Insert value.\n 2 Find value.\n\n 0 Exit.\n\nChoice: ";     cin >> choice;     while (choice != 0) {         switch (choice) {             case 1: {                 cout << "\nValue = ";                 cin >> choice;                 if (tree.insertValue(choice))                     cout << "\n > Insertion successful.\n";                 else                     cout << "\n > Insertion failed.\n";                 break;             }             case 2: {                 cout << "\nValue = ";                 cin >> choice;                 if (tree.findValue(choice) != nullptr)                     cout << "\n > Value found.\n";                 else                     cout << "\n > Value not found.\n";                 break;             }             case 3: {                 if (tree.printTree())                     cout << "\n > Print unsuccessful.\n";                 else                     cout << "\n > Print failed.\n";                 break;             }             case 0: {                 return 0;             }             default: {                 cout << "\n > Invalid option.\n";             }         }         cout << "\nOptions: \n\n 1 Insert node.\n 2 Find node.\n\n 0 Exit.\n\nChoice: ";         cin >> choice;     } } 

The printTree() function is a stub, I'm still looking for an appropriate algorithm that utilizes the in-order traversal. That's not a part of this review, for it is discussed here, in detail.

I am looking for a confirmation that the code has sufficiently improved since the previous version, guided by the answers I was given in that post regarding encapsulation, memory management, etc... Also I would appreciate if you could point out if I've done anything wrong while applying those critiques.

        

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

¿Qué es un iterador?

Un iterador es un concepto muy poderoso en el mundo de C ++. En su núcleo, el iterador es solo un conjunto de operaciones requeridas, pero cuando cada objeto similar al iterador se adhiere a esos conceptos, puede abrir el maravilloso mundo de la programación genérica.

Escribiendo un contenedor que tiene iteradores que se adhieren a la norma significa que puedo ser completamente agnóstico a lo que sea que esté haciendo debajo del capó. Si quiero iterarlo sobre todo en su mapa, solo hago eso:

  for (auto const& item : map) { ... }   

Traigo esto porque RBTree::Iterator1 Crea casi ninguno de los conceptos de incluso el nivel más bajo de Iterator, InputIterator . Esas operaciones son: i != j3 , *i4 , 9988776655544335 , 9988777665544336 , 99887776655443377 , < Código> *i++ . Aunque un árbol rojo debería apoyar realmente a una i != j9 .

En este caso, RBTree::Iterator0 (que debe ser deletreado RBTree::Iterator1 ) debe ser realmente una envoltura delgada para RBTree::Iterator2 . No hay RBTree::Iterator3 necesario (de hecho, no estoy seguro de lo que es para).

  RBTree::Iterator5  

Igualdad, desigualdad y deferencias son operaciones triviales. Dado que tiene el RBTree::Iterator6 , y por lo tanto, conozca a los padres, a la izquierda y los niños del nodo, que es suficiente para averiguar cuáles son los nodos siguientes y anteriores para este, que debe ser deletreado:

  RBTree::Iterator7  

Para comenzar, el caso fácil para "Siguiente" es si nuestro nodo actual tiene un niño derecho:

  RBTree::Iterator8  

Es muy importante escribir sus iteradores para trabajar la forma en que los usuarios esperan que los ingresos trabajen. No puedo enfatizar esto lo suficiente.

Por último, debe no tener un iterador . Eso no tiene sentido. Un iterador es para la iteración. El árbol debe tener un solo miembro: el RBTree::Iterator9 .

consistencia

Una vez que tenemos un iterador de trabajo, mantengamos la interfaz consistente con otros contenedores. Para empezar, necesitamos el esqueleto de contenedor típico:

  InputIterator0  

Luego, 99887766555443321 debe devolver un InputIterator2

  InputIterator3  

que debe compararse con InputIterator4 para ver si hemos encontrado algo. Y InputIterator5 debería ser realmente:

  InputIterator6  

Dado que InputIterator7 es natural, y fácilmente le permite escribir su árbol a otros tipos de arroyos.

¿Por qué no es redactable?

¿Por qué es su clase ni copia ni movible? Como mínimo, escribir las operaciones de movimiento debe ser trivial:

  InputIterator8  

No hay razón para no apoyarlo. La copia implicará una copia profunda, pero eso es menos complicado que cualquier otra operación para el árbol. ¡No necesitas averiguar colorear! Solo copiar

Principio de lo menos sorpresa

Creo que la mayoría de la gente se sorprendería de que InputIterator9 muta su i != j0 ! Cuando dije en su publicación anterior para factorizar a la lógica común, por lo que llamen una función común, me refiero a que, ¡no para crear un nuevo miembro para almacenar los datos intermedios!

Esto no es solo una solución cuestionable porque es sorprendente. Esto también significa que no puede escribir i != j1 como una función de miembro, lo que significa que un 99887776655443333 es inútil.

Además, tenemos i != j4 , que solo se llama aquí:

  i != j5  

Debe estar en el trabajo de i != j6655443336 para mantener el mapa en un estado consistente. De lo contrario, simplemente podría olvidarse de llamar i != j7 y ahora su árbol está roto.

 

What is an Iterator?

An iterator is a very powerful concept in the world of C++. At its core, iterator is just a set of required operations, but when every iterator-like object adheres to those concepts, you can open up the wonderful world of generic programming.

Writing a container that has iterators that adhere to the standard means that I can be completely agnostic to whatever it is you're doing under the hood. If I want to iterate over everything in your map, I just do that:

for (auto const& item : map) { ... } 

I bring this up because RBTree::Iterator meets almost none of the concepts of even the lowest level of iterator, InputIterator. Those operations are: i != j, *i, i->member, ++i, (void)i++, *i++. Although a RedBlack Tree should really support a BidirectionalIterator.

In this case, Iterator (which should be spelled iterator) should really just be a thin wrapper for Node*. There is no Stack necessary (indeed, I am unsure what Iterator::Stack is for).

class iterator {     Node* cur;  public:     ... }; 

Equality, inequality, and dereference are trivial operations. Since you have the Node*, and thus know the node's parent, left, and right children, that is enough to figure out what the next and previous nodes are to this one, which should be spelled:

iterator& operator++() { /* next */; return *this; } iterator& operator--() { /* prev */; return *this; } 

To get you started, the easy case for "next" is if our current node has a right child:

iterator& operator++() {     if (cur->right) {         cur = cur->right;         while (cur->left) {             cur = cur->left;         }         return *this;     }     else {         ...     } } 

It is very important to write your iterators to work the way that users expect iterators to work. I cannot stress this enough.

Lastly, you should not have a member iterator. That doesn't make sense. An iterator is for iterating. The tree should have a single member: the root.

Consistency

Once we have a working iterator, let's keep the interface consistent with other containers. To start with, we need the typical container skeleton:

iterator begin(); iterator end(); 

Then, find() should return an iterator

iterator find(int); 

which should be compared to end() to see if we've found anything. And printTree() should really look like:

friend std::ostream& operator<<(std::ostream&, const RBTree& ); 

Since std::cout << tree; is natural, and easily allows you to write your tree to other kinds of streams.

Why not copyable?

Why is your class neither copyable nor moveable? At the very least, writing the move operations should be trivial:

RBTree(RBTree&& rhs) : root(rhs.root) {     rhs.root = nullptr; } 

No reason not to support it. Copying will involve a deep copy, but that's less complicated than any other operation for the tree. You don't need to figure out colouring! Just copy.

Principle of Least Surprise

I think most people would be surprised that findValue() mutates your RBTree! When I said in your previous post to factor out the common logic so they call a common function, I meant just that - not to create a new member to store the intermediate data!

This isn't just a questionable solution because it's surprising. This also means you can't write find() as a const member function, which means that a const RBTree is useless.

Furthermore, we have resolve(), which is only called here:

bool RBTree::insertValue(int p_value) {     if (findValue(p_value) == nullptr) {         attachValue(p_value);         resolve();  // <===         return true;     }     else         return false; } 

It should be up to attachValue()'s job to keep the map in a consistent state. Otherwise, you could simply forget to call resolve() and now your tree is broken.

 
 
 
 

Relacionados problema

8  Encontrar una contraseña con fuerza bruta  ( Finding a password with brute force ) 
El propósito de este Código es encontrar una contraseña con el agrietamiento de fuerza bruta, donde, ya que intente todas las combinaciones posibles hasta que...

4  Asignación de matrices para la modificación en el lugar  ( Allocating matrices for in place modification ) 
Este código parece estar funcionando. Estoy asignando matrices en la pila y los pasa a funciones para modificar en su lugar. ¿Es esta una práctica estándar, o...

5  ¿Podría mejorarse este sistema de profundidad para un juego?  ( Could this depth system for a game be improved ) 
Todavía soy nuevo en C ++ y no tengo una gran idea de mi codificación, así que estaría muy agradecido a cualquiera y todos los que le otorgan consejos. Ade...

2  ¿Estoy usando mi matriz de origen de datos correctamente?  ( Am i using my data source array correctly ) 
Cuando quiero hacer algunas pruebas rápidas para mis uitablesviewControllers, generalmente creo un NSARRAY que tiene algunos datos ficticios. Me gustaría sabe...

8  Convertir un segurreque en una matriz de bytes  ( Converting a securestring to a byte array ) 
¿Asigna algo que no ha liberado? ¿Algo que permanece en la memoria? Excepto la matriz de bytes de resultado, OFC. checkOnline.sh1 ...

12  C ++ Lista doblemente vinculada Implementación  ( C doubly linked list implementation ) 
¿Alguien tiene sugerencias sobre cómo mejorar esto? específicamente: ¡Estoy pasando y devolviendo las referencias correctamente para prevenir la copia in...

5  Destructor para una lista vinculada  ( Destructor for a linked list ) 
El código completo se encuentra aquí: https://gist.github.com/4521540 < / p> Es un maniquí List en C ++. Mi preocupación es para liberar la memoria. No s...

2  Pregunta de memoria  ( Memory question ) 
Puede verificar esta parte de una subclase del controlador de visualización para verificar las fugas de la memoria. No soy tan bueno para encontrar fugas. Nec...

3  Integración de SFML y BAX2D LIB, y una fábrica de forma de producción en masa [cerrada]  ( Integrating sfml and box2d lib and a mass production shape factory ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

4  Algoritmo de monedas mínimo en rubí  ( Minimum coins algorithm in ruby ) 
Estoy trabajando en un rompecabezas para encontrar el número mínimo de monedas necesarias para comprar un producto. Estoy dado tres monedas: 1 3 5 ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos