Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

GeekPlusPlus

Creating a proper iterator.

This topic is 5221 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I'm currently working on writing an iterator class for my AvLTree (Binary tree). Now my problem is, once I do this: AvLTree::CIterator it; How do I setup my iterator class so that I can do. (*it) and get the object my iterator points to? Like other data structure iterators. right now I have
	// Interator class

	class CIterator
	{
	public:
		CIterator() {};
		~CIterator() {};

	private:
		CAvLNode<Type>* m_pPosition;
	};
As my iterator class. Anyone have an idea? - Newb Programmer: Geek++ [edited by - GeekPlusPlus on June 5, 2004 7:56:51 PM]

Share this post


Link to post
Share on other sites
Advertisement
Overload unary operator *. Probably something like

template <typename Type>
class CIterator {
public:
CIterator() {};
~CIterator() {};

Type operator*() { return m_pPosition->value; }
private:
CAvLNode<Type>* m_pPosition;
};

Share this post


Link to post
Share on other sites
Well, I''m not sure what your implementation looks like, but I would imagine that it''d be best to make your iterator class a template so you can use one Iterator class for any data structure. In any event, I know that you are going to have to:

1. Overload the dereference operator. I''ve never done this but I imagine it would look something like:

CAvLNode& CIterator::operator*()
{
return *m_pPosition;
}

I didn''t put a parameter into the function because you should really make it part of your class. If you made it a template, you would replace CAvLNode& with TypeNode& assuming the template type had the name "TypeNode."

2. You should definitely make the CIterator class a friend of whatever lists you need.

3. If you made the iterator a template, you could have a function like this in your CAvLNode class:


// getRootIt() returns an iterator that points to the root of the AvLTree.
CIterator CAvLTree::getRootIt()
{
return CIterator(m_pRoot);
}


and in your CIterator class, a constructor like this:


template
CIterator::CIterator(TypeNode* pTNode):
m_pPosition(pTNode)
{
}


there might be bugs in that code but you get the idea.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by clearsnake
Well, I''m not sure what your implementation looks like, but I would imagine that it''d be best to make your iterator class a template so you can use one Iterator class for any data structure. In any event, I know that you are going to have to:

1. Overload the dereference operator. I''ve never done this but I imagine it would look something like:

CAvLNode& CIterator::operator*()
{
return *m_pPosition;
}

I didn''t put a parameter into the function because you should really make it part of your class. If you made it a template, you would replace CAvLNode& with TypeNode& assuming the template type had the name "TypeNode."

2. You should definitely make the CIterator class a friend of whatever lists you need.

3. If you made the iterator a template, you could have a function like this in your CAvLNode class:


// getRootIt() returns an iterator that points to the root of the AvLTree.
CIterator<CAvLNode> CAvLTree::getRootIt()
{
return CIterator<CAvLNode>(m_pRoot);
}


and in your CIterator class, a constructor like this:


template <typename TypeNode>
CIterator::CIterator(TypeNode* pTNode):
m_pPosition(pTNode)
{
}


there might be bugs in that code but you get the idea.


Sorry about that #3. I guess brackets don''t show up in code snippets. Here''s what I meant to write:


// getRootIt() returns an iterator that points to the root of the AvLTree.

CIterator<CAvLNode> CAvLTree::getRootIt()
{
return CIterator<CAvLNode>(m_pRoot);
}


and


template <typename TypeNode>
CIterator::CIterator(TypeNode* pTNode):
m_pPosition(pTNode)
{
}


Also, in response to SiCrane''s suggestion, you would not want to return m_pPosition->value because that wouldn''t give you a reference to the thing m_pPosition points to (which is what you actually want).

Share this post


Link to post
Share on other sites
Also noting that your overloaded * should be a const member function which the previous examples left out. Just because an iterator is constant doesn''t mean it can''t be dereferenced, just like you can dereference both const and non-const pointers (with the const-ness of the data being pointed to not being affected by the const-ness of the iterator).

Share this post


Link to post
Share on other sites
quote:
Original post by Polymorphic OOP
Also noting that your overloaded * should be a const member function which the previous examples left out. Just because an iterator is constant doesn''t mean it can''t be dereferenced, just like you can dereference both const and non-const pointers (with the const-ness of the data being pointed to not being affected by the const-ness of the iterator).


I don''t agree. The dereference operator should not be const. Or perhaps, you could overload it to be both const and non-const (sounds like it would work, but I haven''t tried it) because it makes perfectly good sense to do something like this:

*it = getNewValue();

or

int myVariable = *it;

but if you''re going to have a non-const version then there''s really no sense in making a const one.

Share this post


Link to post
Share on other sites
quote:
Original post by clearsnake
I don't agree. The dereference operator should not be const. Or perhaps, you could overload it to be both const and non-const (sounds like it would work, but I haven't tried it) because it makes perfectly good sense to do something like this:

*it = getNewValue();

or

int myVariable = *it;


You can still do that with a const member function! You should read up on const as you seem confused as to what a const member function implies. Your two examples aren't really showing anything that represents somethign you can't do with a const member function. I think you are interpreting "const member-function" as a member function that returns a reference to a const, which is not what a const member function is. Also, if that is what you meant then your second example would work anyways, so either way I don't see at all what you are trying to say.

Making a member function const means that it is capable of being called on a const object. Internally, the this pointer is a poitner to const.

You declare one like

class a
{
void some_function() const ;
};


(note the const at the end of the function declaration)

Member functions that are const will be called called if the object isn't const unless there is also a non-const version of the member function overloaded as well. Making a const member function just means that the this pointer being passed is a pointer to a const. If you don't understand the logic behind it, its the same reason that you can pass a pointer to a non-const object to a function that takes a pointer to a const. With the logic as my function example, the member function is still useable with a non-const object.

The reason why in this case you shouldn't also overload a non-const in addition to the const version is because the non-const version would do exactly the same thing as the const version, therefore you would just be needlessly duplicating code.

[edited by - Polymorphic OOP on June 5, 2004 11:10:53 PM]

Share this post


Link to post
Share on other sites
Imagine what we could accomplish if we didn''t argue over the const keyword. The only place it actually is needed is in this case:

class MyInt
{
public:
MyInt& operator =(const MyInt &x)
{
m_x = x;
}
private:
int m_x;
};
//in code...

MyInt myIntObj;
myIntObj = 3; //Compiler complains if parameter is not ''const''


I discovered that when I tried going without const and the compiler bitched. In VC++ [the one that comes with .net 2003] atleast, you can''t input a literal like int 3 above, unless it''s treated as const, b/c it''s obvious that you can''t modify 3, b/c it''s not a variable. And there are probably other stupid idiosyncrasies that only const can appease. For everything else, eg thinks like:

Vector3 operator +(const Vector3&) const;

adding those stupid const''s in is more time-consuming than safe and helpful. All IMHO, anyway. Kthx.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Polymorphic OOP
You declare one like

class a
{
void some_function() const ;
};


(note the const at the end of the function declaration)

its the same reason that you can pass a pointer to a non-const object to a function that takes a pointer to a const. With the logic as my function example, the member function is still useable with a non-const object.


I thought const functions can''t modify the member objects for the class that they''re declared in, so what''s the advantage to declaring that above function that takes 0 arguments and returns nothing as const?

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!