Writing a tree iterator

Discussion in 'C++' started by James Aguilar, Mar 28, 2005.

  1. Suppose I have a class Heap that represents a binary heap in an array. Then
    suppose that I have another class called Heap::iterator that moves down the
    heap to the left or the right. Here is the code from the header file
    describing these two types:

    --- CODE ---

    class Heap
    {
    std::vector<int> m_vec;
    public:
    class iterator {
    protected:
    Heap *m_heap;
    int m_position;
    public:
    enum Direction {LEFT, RIGHT};

    iterator(Heap &myHeap, int position = 0);
    iterator(const iterator &other);

    int &operator *();

    iterator left() const;
    iterator right() const;

    iterator child(const Direction &dir);
    void walk(const Direction &dir);
    };

    Heap(int depth);

    int &operator [](unsigned int index);
    const int &operator [](unsigned int index) const;

    iterator top();

    void write(std::eek:stream &o) const;
    };

    --- CODE ---

    This is not compilable code. How would you recommend that I implement a
    const_iterator while reusing code and not just copy and pasting method
    bodies?

    Thanks,

    JFA1
    James Aguilar, Mar 28, 2005
    #1
    1. Advertising

  2. On 2005-03-28, James Aguilar <> wrote:
    > Suppose I have a class Heap that represents a binary heap in an array. Then
    > suppose that I have another class called Heap::iterator that moves down the
    > heap to the left or the right. Here is the code from the header file
    > describing these two types:
    >

    [snip]
    > This is not compilable code.


    Why not ? It would make it easier to address the issue if you'd say why.

    > How would you recommend that I implement a
    > const_iterator while reusing code and not just copy and pasting method
    > bodies?


    The same way you always use when you want to write the same code for different
    types: templates.

    Make a templated version of an iterator, have one with non-const template
    parameters and one where you use const. You may need more than one template
    argument. Then make iterator and const_iterator typedefs. e.g. iterator
    could be iter<T,T*> and const_iterator could be iter<T, const T*>

    Cheers,
    --
    Donovan Rebbechi
    http://pegasus.rutgers.edu/~elflord/
    Donovan Rebbechi, Mar 28, 2005
    #2
    1. Advertising

  3. "Donovan Rebbechi" <> wrote in message
    news:...
    > Why not ? It would make it easier to address the issue if you'd say why.


    I didn't think it would be necessary.

    > The same way you always use when you want to write the same code for
    > different
    > types: templates.
    >
    > Make a templated version of an iterator, have one with non-const template
    > parameters and one where you use const. You may need more than one
    > template
    > argument. Then make iterator and const_iterator typedefs. e.g. iterator
    > could be iter<T,T*> and const_iterator could be iter<T, const T*>


    And it seems it wasn't! This is very helpful! Now, why didn't I think of
    that . . .

    - JFA1
    James Aguilar, Mar 28, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,399
  2. greg
    Replies:
    6
    Views:
    444
    Dietmar Kuehl
    Jul 17, 2003
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,091
  4. Replies:
    6
    Views:
    628
    Jim Langston
    Oct 30, 2005
  5. Steven D'Aprano

    What makes an iterator an iterator?

    Steven D'Aprano, Apr 18, 2007, in forum: Python
    Replies:
    28
    Views:
    1,132
    Steven D'Aprano
    Apr 20, 2007
Loading...

Share This Page