-1

I've build an iterator class aiming at inspecting a binary tree. This iterator is defined bellow:

template <class Key> class intervalST_const_iterator
{
//friend class IntervalST<Key>;

private:
    const Interval<Key> *interval;// equivalent to Interval<Key> const *interval; meaning: interval is apointer to the const object: Interval<Key>
                                  //meaning that the object cannot be changed via interval
                                  //interval can change here

public:
    intervalST_const_iterator(const Interval<Key> *p): interval(p){}
    //~intervalST_const_iterator() {delete interval;}
    //the const at the end of this operator means that the operator will not change *this
    bool operator != (const intervalST_const_iterator & other) const
    {
        return this->interval != other.interval;
    }
    bool operator == (const intervalST_const_iterator & other) const
    {
        return this->interval == other.interval;
    }
    //the const at the beginning means that the it's not allowed to change the object
    const Interval<Key> operator *() const
    {
        return *(this->interval);
    }
    intervalST_const_iterator<Key> & left()
    {
        interval = interval->left;
        return *this;

    }
    intervalST_const_iterator<Key> & right()
    {
        interval = interval->right;
        return *this;
    }
};

In this class I've also defined a destructor ~intervalST_const_iterator() {delete interval;} I've put it in comment.

I'm using this iterator in order to iterate on a tree class that looks like that:

template <class Key> class intervalST_const_iterator;

template <class Key> class IntervalST
{
private:
    Interval<Key> *root;

    //friend class intervalST_const_iterator<Key>;//allow the iterator class to access the private section of intervalST

    bool isRed(Interval<Key> *interval);
    Interval<Key> *rotateLeft(Interval<Key> *h);
    Interval<Key> *rotateRight(Interval<Key> *h);
    Interval<Key> *put(Interval<Key> *h,Key lo, Key hi, Key val);
    Interval<Key> *moveRedLeft(Interval<Key> *h);
    Interval<Key> *moveRedRight(Interval<Key> *h);
    Interval<Key> *deleteMin(Interval<Key> *h, Key hi);
    Interval<Key> *balance(Interval<Key> *h);
    Interval<Key> *remove(Interval<Key> *h, Key lo, Key hi);
    Interval<Key> *min(Interval<Key> *h);
    Interval<Key> *addDuplicate(Interval<Key> *h, Key hi);
    Interval<Key> *removeDuplicate(Interval<Key> *h, Key low, Key hi);
    Interval<Key> *getPointerToKey(Key low);

    void flipColors(Interval<Key> *h);
    void destroy(Interval<Key> *h);
    void printTree(Interval<Key> *h, int indent);
    Key maxVal(Interval<Key> *h);
    int size(Interval<Key> *h);
    bool isBST(Interval<Key> *x, Key min, Key max);
    inline bool isBST(){return isBST(root,0,0);}
    bool isSizeConsistent(Interval<Key> *x);
    inline bool isSizeConsistent(){return isSizeConsistent(root);}
    bool is23(Interval<Key> *x);
    inline bool is23(){return is23(root);}
    bool isBalanced();
    bool isBalanced(Interval<Key> *x,int black);
    int getKeySize(Key low);
    int compare(Key a, Key b);

public:

    //don't forget to build the constructor
    //and overload the =equal operator
    typedef intervalST_const_iterator<Key> const_iterator;//const iterator on a tree


    const_iterator begin() const;
    const_iterator end() const;

    IntervalST():root(NULL){};
    ~IntervalST();
    void remove(Key lo, Key hi);
    void put(Key lo, Key hi);
    inline int size(){return size(root);}
    inline bool isEmpty(){return root == NULL;}
    void print(int indent = 0);
    void check();


};

with corresponding begin() and end() method for the iterator

template <typename Key> typename IntervalST<Key>::const_iterator IntervalST<Key>::begin() const
{
return const_iterator(root);
}

template <typename Key> typename IntervalST<Key>::const_iterator IntervalST<Key>::end() const
{
//return const_iterator(NULL,this);
return const_iterator(NULL);
}

Then I'm using a function - see bellow - which works well when the destructor of the iterator class is not defined and gives strange results when the destructor is defined.

Why is this happening? Do I need to define a destructor for the iterator class in order to prevent leaks? How to handle this problem? thanks for your help.

template <typename Key> std::vector<Segment<Key> > findIntersections(const IntervalST<Key> &tree ,Segment<Key> segment)
{
//initialize a const iterator on the tree
intervalST_const_iterator<Key> iterator = tree.begin();
vector<Segment<Key> > intersections;

Key k = (*iterator).max;
//walk the tree
while(iterator != tree.end())
{
    //if(*(iterator).intersects(segment.gety1(),segment.gety2())) intersections.push_back(segment);
    if(intersects((*iterator).low,(*iterator).back,segment.gety1(),segment.gety2()))
    {
        intersections.push_back(segment);
        return intersections;
    }
    else if (iterator.left() == tree.end())                                          iterator = iterator.right();
    else if (segment.gety1() > (*iterator.left()).max)                               iterator = iterator.right();
    else                                                                             iterator = iterator.left();
}
return intersections;
}
PhonoDots
  • 149
  • 1
  • 12
  • You might want to read about [the rule of three](https://en.wikipedia.org/wiki/Rule_of_three_%28C%2B%2B_programming%29). – Some programmer dude Dec 19 '13 at 08:54
  • @Joachim Pileborg I think the problem **is not linked** to the fact I haven't defined a copy ctor and that I've not overloaded the equal (=) operator. – PhonoDots Dec 19 '13 at 08:59
  • @PhonoDots: Indeed; it's because you're deleting something you didn't `new`. Don't do that. (But if it did need a destructor, then the Rule of Three would be very important). – Mike Seymour Dec 19 '13 at 09:00

1 Answers1

3

The iterator does not own the Interval, it just has a pointer to one that's owned by the IntervalST it's iterating over. Therefore, it shouldn't delete it.

The iterator does not need a destructor, nor any of the other special functions it would also need if it did.

Community
  • 1
  • 1
Mike Seymour
  • 249,747
  • 28
  • 448
  • 644