2

I realize I'm stupid so please go easy on me. Yes this is an assignment, but I want to understand what I'm doing wrong, not just the answer.

I'm trying to write an operator== and an operator!= function for an iterator on a binary search tree in the BSTIterator class template.

Given (all in the same class template):

private: 

BSTNode<Data>* curr;

...

bool operator==(BSTIterator<Data> const & other) const {
  (here's where I do my magic)
}

Same setup for operator!=.

I write for == ...

  return (&curr == other);

I don't think I need the parentheses but anyway ... here's what I have for !=

  return !(&curr == other);

My compiler has a problem with != but not apparently ==.

It spit out a lot of gobbledy gook but, as far as I can tell, the relevant part is:

No match for 'operator!=' in '&((const BSTIterator*)this)->BSTIterator::curr != other'

and it references the line that says return !(&curr == other);

I think at first the compiler didn't like my operator== function either but I see no reference to it now. Why would it like one and not the other when they are basically the same except for the ! ?

Please let me know if I need to include more information.

0

2 Answers 2

4

As I understand from your code curr indicate the position that your iterator point to it. Do when you compare an instance of your iterator with another you should check if they both point to the same location. am I right? if the answer is true shouldn't you code like this:

bool operator==( BSTIterator<Data> const & other) const {
    return this->curr == other.curr;
}
bool operator!=( BSTIterator<Data> const & other) const {
    return this->curr != other.curr;
}

And about your error: your compiler say &cur is of a type( BSTNode<Data>** ) that I don't know how to compare it with an instance of your iterator( BSTIterator<Data> ) and that's obvious since you are defining == and != for your class and you never defined and operator for such operation, do you?

6
  • Ah, thank you! I get so confused with this stuff. I entered what you wrote, and didn't get any errors from Mr Compiler. I had tried every variation of ->'s, &'s and .'s but this one, lol.
    – punstress
    Oct 9, 2012 at 19:16
  • 1
    @punstress You should make a good effort to understand what the ->, & and . operators do, it'll make things a lot easier to understand. Remember to think of the types you're applying them to, and what it does to each type.
    – Collin
    Oct 9, 2012 at 19:31
  • You're right; I'm still confused why this->curr needs an arrow and other.curr needs a dot. I understand -> accesses a member but why wouldn't it also be other->curr?
    – punstress
    Oct 9, 2012 at 19:59
  • Languages like basic, delphi and even java is designed with idea that programmer don't know every thing, so language should abstract what ever possible, but C++ designed by idea that programmer know every thing and language should just provide the tools. When you have an object other its memory is allocated (may be in stack) so your access with . can't fail, but when you access a pointer(this) with -> you must know that you access may fail because pointer may be NULL or invalid (already deleted) so the reason is obvious, this and other do not have the same type
    – BigBoss
    Oct 9, 2012 at 20:05
  • 1
    Note that this-> is not required here and you can say curr == other.curr, main note is you must compare curr of this with curr of another!
    – BigBoss
    Oct 9, 2012 at 20:06
2

The first thing is to determine what the semantics of the operation are. For a class with reference semantics (an iterator represents a reference into an element in a container) the common definition of equality is refers to the exact same object. Conceptually, it1 == it2 iff &*it1 == &*it2 (both iterators are the same if the address of the object accessed through operator* is the same *).

After that you just need to perform the test. In your case if you have a pointer to the node in the tree, then the two iterators are the same if the pointers stored inside the iterators refer to the same node. That is, if the stored pointers are the same.

Note that in this case you want to compare the pointers by value: two pointers are the same if the value stored in them is the same, so you will not use the address-of operator (1):

return (&curr == other);
        ^        ^
        1        2

Also note (2) that in that line of code you are comparing a pointer curr with an iterator other which probably does not make sense. You want to compare both stored pointers.

4
  • Uh oh. I was pretty sure we're comparing addresses not values. Here is a place in the test.cpp file that uses the == to compare iterators, one called vit initialized at begin() and one called ven at end(). for(; vit != ven; ++vit) and it goes through a vector of ints and inserts each one into the BST.
    – punstress
    Oct 9, 2012 at 19:22
  • @punstress: A pointer has a value, that is the address of an object, and an address that is the memory location where the value is stored. &curr obtains the address of the pointer, which is different from the value stored in the pointer (the latter being the address of some other object, the node) Oct 9, 2012 at 19:29
  • Coincidentally someone just asked about this on our class forum, and the response was "you should compare if curr of the current BSTiterator is equal to curr of "other". This is checking if they(the two curr) are the same, not the values contained in them."
    – punstress
    Oct 9, 2012 at 19:49
  • 1
    @punstress: No. You are mixing equality with identity. Two separate distinct pointers can be equal if the stored pointer refers to the same memory. int a; int *p1=&a, *p2=&1; bool identity = &p1 == &p2; bool equality = p1 == p2;. There are two pointers, with different addresses, although both refer to the same object a, so they are equal. Comparing the address of two objects is a test for identity and it will tell you that they are the same object, testing the values is a test for equality and will tell you that in this particular point in time they share the same value. Oct 9, 2012 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.