Итераторы шаблонов, разыменование и typedef в C++

Question

Я получаю странные результаты от программы, над которой я работаю, и не могу понять, где ошибка или почему я ее получаю. Я работаю над шаблоном класса quadtree, который использует шаблонный итератор. Несмотря на то, что моя функция работает правильно, она не возвращает найденное значение.

Это мой основной класс квадрадерева:

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_; 
}; 

кажется, что моя функция находки находит правильный узел на моем квадрадереве, как я могу использовать зЬй :: COUT распечатать родитель, прежде чем он возвращает его правильное значение. Однако

return iterator(parent); 

дает мне либо значение NULL или точку (9,0), который не находится в моем квадрадереве.

Вот мой DepthIterator класс:

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_; 
}; 

Возможно, моя копия или разыменования биты проблема? Я склоняюсь к разыменованию, потому что моя функция поиска работает до того, как эта операция будет использована, но не после.

Вот мой Узла класс:

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; 
}; 

Моя основная функция будет содержать что-то вроде этого:

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'); 

Первый тест работает, но второй не делает. Я не уверен, что это потому, что первый тест - это корневой узел, а второй тест - нет, или если это потому, что я разыменован в середине или по какой-то другой причине. Я немного новичок в C++ и действительно стараюсь реализовать это. Может ли кто-нибудь объяснить, почему моя функция поиска не работает?

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]); } 
     } 
    } 
} 

Проблема заключается в неопределенное поведение, если х == родительский,> pt.x или у == родительский,> pt.y в квадранте будет неопределенным, так как ни одно из условий не если это имеет значение верно. В этом случае parent->children[quadrant] == NULL ведет себя как кошка шредингера, это может быть правдой, это может быть неверно.

possile исправление может быть:

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; 
    }