Template-Iteratoren, Dereferenzierung und Typedef in C++

Question

Ich bekomme merkwürdige Ergebnisse von einem Programm, an dem ich arbeite und kann nicht herausfinden, wo der Fehler ist oder warum ich es bekomme. Ich arbeite an einer Templated-Quadtree-Klasse, die einen Template-Iterator verwendet. Obwohl meine Funktion korrekt zu funktionieren scheint, gibt sie den gefundenen Wert nicht zurück.

Das ist mein Grund Quadtree Klasse:

template <class number_type, class label_type> 
class QuadTree { 
public: 
    // CONSTRUCTORS 
    QuadTree() : size_(0), root_(NULL) {} 

    // ACCESSORS 
    unsigned int size() const { return size_; } 

    typedef DepthIterator<number_type, label_type> iterator; 

    iterator begin() const { 
     return root_; 
    } 
    iterator end() const { return iterator(NULL); } 

    // This is the function not returning the expected value 
    iterator find(number_type x, number_type y, Node<number_type, label_type>* parent = NULL) { 
     if (parent == NULL) { 
      // start at the root, if equal return, otherwise call recursively 
      if (root_->pt.x == x && root_->pt.y == y) { return iterator(root_); } 
      else { 
       return find(x, y, root_); 
      } 
     } 
     else { 
      int quadrant; 
      // find the quadrant of the point 
      if (x < parent->pt.x && y < parent->pt.y) { 
       quadrant = 0; 
      } 
      else if (x > parent->pt.x && y < parent->pt.y) { 
       quadrant = 1; 
      } 
      else if (x < parent->pt.x && y > parent->pt.y) { 
       quadrant = 2; 
      } 
      else if (x > parent->pt.x && y > parent->pt.y) { 
       quadrant = 3; 
      } 
      // see if the quadrant is a branch or a leaf 
      if (parent->children[quadrant] == NULL) { 
       // child is a leaf and it matches the search 
       if (x == parent->pt.x && y == parent->pt.y) { return iterator(parent); } 
       // child is a leaf, but it does not match the search 
       else { return iterator(NULL); } 
      } 
      else { 
       // child is a branch, check if it's equal and return if it is, if not, continue on 
       if (x == parent->pt.x && y == parent->pt.y) { return iterator(parent); } 
       else { find(x, y, parent->children[quadrant]); } 
      } 
     } 
    } 
private: 
    unsigned int size_; 
    Node<number_type, label_type>* root_; 
}; 

Es scheint, dass meine Funktion find den richtigen Knoten auf meinem Quadtree findet, wie ich std :: cout verwenden können aus der Mutter zu drucken, bevor er es wieder für der richtige Wert Jedoch

return iterator(parent); 

gibt mir entweder einen NULL-Wert oder den Punkt (9,0), die nicht in meinem Quadtree ist.

Hier ist meine DepthIterator Klasse:

template <class number_type, class label_type> 
class DepthIterator { 
public: 
    // CONSTRUCTOR/COPY/ASSIGN/DECONSTRUCTOR 
    DepthIterator() : ptr_(NULL) {} 
    DepthIterator(Node<number_type, label_type>* n) : ptr_(n) {} 
    DepthIterator(const DepthIterator& old) : ptr_(old.ptr_) {} 
    ~DepthIterator() {} 

    // OPERATORS 
    DepthIterator& operator=(const DepthIterator& old) { ptr_ = old.ptr_; return *this; } 
    const Point<number_type>& operator*() const { return ptr_->pt; } 
    bool operator== (const DepthIterator& rgt) { return ptr_ == rgt.ptr_; } 
    bool operator!= (const DepthIterator& rgt) { return ptr_ != rgt.ptr_; } 

    // ACCESSORS 
    label_type getLabel() const { return ptr_->label; } 


private: 
    Node<number_type, label_type>* ptr_; 
}; 

Vielleicht ist meine Kopie oder dereferenzieren Bits sind das Problem? Ich lehne mich der Dereferenzierung zu, weil meine Suchfunktion funktioniert, bevor diese Operation verwendet wird, aber nicht danach.

Hier ist meine Klasse Node:

template <class number_type, class label_type> 
class Node { 
public: 
    Node() {} 
    Node(Point<number_type> p, label_type l) : pt(p), label(l) { parent = NULL; } 

    Node& operator=(const Node& old) { pt = old.pt; label = old.label; parent = *old; return *this; } 

    Point<number_type> pt; 
    label_type label; 
    Node<number_type, label_type>* children[4]; 
    Node<number_type, label_type>* parent; 
}; 

Meine Hauptfunktion so etwas wie dieses enthalten würde:

QuadTree<int, char>::iterator itr = test.find(20,10); 
// the point (20,10) does exist in the quadtree 
assert (itr != test.end()); 
assert (itr.getLabel() == 'A'); 
// both of these tests pass 

const Point<int> &pt = *itr; 
assert (pt.x == 20); 
assert (pt.y == 10); 
// both of these tests pass 

QuadTree<int,char>::iterator itr = test.find(4,7); 
// the point (4,7) does exist in the quadtree 
assert (itr != test.end()); 
// this test fails however^
assert (itr.getLabel() == 'B'); 

Der erste Test funktioniert, aber die zweite nicht. Ich bin mir nicht sicher, ob dies der Fall ist, weil der erste Test der Wurzelknoten ist und der zweite Test nicht, oder wenn es darum geht, dass ich in der Mitte dereferenziere, oder aus irgendeinem anderen Grund. Ich bin etwas neu in C++ und habe wirklich Mühe, dies zu implementieren. Kann mir jemand erklären, warum meine Suchfunktion nicht funktioniert?

Answer 1

iterator find(number_type x, number_type y, Node<number_type, label_type>* parent = NULL) { 
    if (parent == NULL) { 
     // start at the root, if equal return, otherwise call recursively 
     if (root_->pt.x == x && root_->pt.y == y) { return iterator(root_); } 
     else { 
      return find(x, y, root_); 
     } 
    } 
    else { 
     int quadrant; 
     // find the quadrant of the point 
     if (x < parent->pt.x && y < parent->pt.y) { 
      quadrant = 0; 
     } 
     else if (x > parent->pt.x && y < parent->pt.y) { 
      quadrant = 1; 
     } 
     else if (x < parent->pt.x && y > parent->pt.y) { 
      quadrant = 2; 
     } 
     else if (x > parent->pt.x && y > parent->pt.y) { 
      quadrant = 3; 
     } 
     // see if the quadrant is a branch or a leaf 
     if (parent->children[quadrant] == NULL) { 
      // child is a leaf and it matches the search 
      if (x == parent->pt.x && y == parent->pt.y) { return iterator(parent); } 
      // child is a leaf, but it does not match the search 
      else { return iterator(NULL); } 
     } 
     else { 
      // child is a branch, check if it's equal and return if it is, if not, continue on 
      if (x == parent->pt.x && y == parent->pt.y) { return iterator(parent); } 
      else { find(x, y, parent->children[quadrant]); } 
     } 
    } 
} 

Das Problem ist, das nicht definiertes Verhalten, wenn x == Eltern-> pt.x oder y == Eltern-> pt.y als Quadrant undefiniert, weil keiner der, wenn die Bedingungen true ergibt. In diesem Fall verhält sich parent->children[quadrant] == NULL wie Schrödingers Katze, es könnte wahr sein, es könnte falsch sein.

könnte ein possile fix sein:

if (x <= parent->pt.x && y <= parent->pt.y) { 
     quadrant = 0; 
    } 
    else if (x > parent->pt.x && y <= parent->pt.y) { 
     quadrant = 1; 
    } 
    else if (x <= parent->pt.x && y > parent->pt.y) { 
     quadrant = 2; 
    } 
    else if (x > parent->pt.x && y > parent->pt.y) { 
     quadrant = 3; 
    }