Writing a tree iterator

[James Aguilar]

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: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

 

[Donovan Rebbechi]

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,

 

[James Aguilar]

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