How to write an iterator for a binary search tree in c++ using nodes

Question

I am trying to write an iterator for a binary search tree that consists of nodes that are maps

Node<Key, Value>* node;

I have to iterate over a set of these and I don't really know how to return an iterator.

bool operator!=(const iterator& rhs) const{ ....idk...}

iterator& operator++(){

The second one is confusing because I'm not sure how to return a iterator&

Thanks in advance

score 1 · Answer 1 · answered Nov 17 '15 at 03:12

1

An iterator is just an object that represents a particular item in a container (your binary search tree). When you increment the iterator (with ++) you move the iterator to represent the next item in the container. So your iterator must know how to traverse to the next element in the container.

Your container must be able to provide two iterators.

begin()   // returns an iterator to the first element.
end()     // returns an iterator to the one past the last element.
          // when an iterator is incremented passed the end of the container
          // it should compare equal to the iterator returned by this call.

The operations you need to define for one of the simplest iterator (Forward Iterator) are:

Node<Key, Value>&  operator*()     // Return a reference to the node
                                   // That the current iterator represents.

iterator&          operator++()    // Advance the iterator to the next element.
                                   // Return a reference to yourself.

iterator           operator++(int) // Advance the iterator. But return the
                                   // original value.

bool operator!=(iterator const & rhs) // Check if two iterators represent
                                      // the same node (or end). return true
                                      // if they do not (its not equal).

answered Nov 17 '15 at 03:12

Martin York

257,169
86
333
562

I think I'd describe the iterator as an object that *abstracts* and *encapsulates* the implementation details of a container object, decoupling/shielding clients from the container's implementation (e.g. array, linked list, btree, etc) before being able to traverse it, rather than only as "an object that represents a particular item in a container", even though it does point to individual items during iteration. With your description, it seems even a raw pointer could pass for an "iterator". – code_dredd Nov 17 '15 at 21:12
@ray: A raw pointer **IS** an implementation of an iterator (if the container is a C-Array). – Martin York Nov 18 '15 at 00:10
But a C arrays and raw pointers are not objects (i.e. class instances), so I think you're stretching the terminology beyond what's appropriate in this context. The iterators are clearly a reference to the [iterator pattern](https://en.wikipedia.org/wiki/Iterator_pattern) – code_dredd Nov 18 '15 at 02:47
@ray: The first line in your link: `C++ implements iterators with the semantics of pointers in that language.` Pointers in C++ fulfill the contract of iterators. See the concept http://www.sgi.com/tech/stl/trivial.html and as such are iterators, – Martin York Nov 18 '15 at 04:39
@ray: You are confusing the term `object` and `instances`. – Martin York Nov 18 '15 at 04:43
It seems you're confusing the difference between actual objects (O-O sense) and primitives. Objects are instances of a class (e.g. [here](https://stackoverflow.com/questions/3323330/difference-between-object-and-instance) and [here](https://stackoverflow.com/questions/2885385/what-is-the-difference-between-an-instance-and-an-object)) whereas raw pointers are stored as integer values, which are primitives. The link you quote says that iterators use pointer *semantics* -i.e. you can use them just *like* raw pointers- not that they actually *are*, even though they do encapsulate them. Blurry line – code_dredd Nov 18 '15 at 06:05
@Ray: You need to read the standard: See [`n4527`](http://stackoverflow.com/a/4653479/14065) (the latest version of the standard). Section `1.8 The C++ object model`. `An object is a region of storage.` – Martin York Nov 18 '15 at 16:25
The fact that you think pointers are integers just is a sign you don't understand the language. – Martin York Nov 18 '15 at 16:29
Yes iterators have pointer semantics. But transitively that means pointers have iterator semantics. Look at the standard library. The algorithms section. See all those algorithms that take iterators as input. Now try and use them with pointers. Guess what they work perfectly well. Also take a look at `std::iterator_traits` class it has a section defined for pointers. If it looks like a duck and quacks like a duck its a duck. A pointer is an iterator *(when used with a container that supports it)*. – Martin York Nov 18 '15 at 16:31
I think you're relying on an equivocation fallacy to make your point. We're clearly using the term "object" differently, despite your appeal to the standard. You're using the term to mean a region of storage, so even an `int` type would be an 'object' in that sense. However, in *object-oriented programming terms* an object is an instance of a *class* (e.g. `Dog`), rather than just a primitive type (`int`, `char`, etc). By your own reasoning, you'd have to say that `C` is an OO language, which it isn't. – code_dredd Nov 19 '15 at 01:55
Your transitivity example is simply an implementation detail (i.e. pointer can be used as iterator). Sure, in certain situations. I thought my clarification that I was referring to the iterator design pattern (i.e. the *concept* of what an iterator is) seems to have gone unnoticed; you seem to be focusing on implementation details, like whether pointers can or cannot be used to achieve the goal of an iterator -which it can and was never under discussion- but you still used that to conclude I don't understand the language... You need to understand what I actually tried to communicate :) – code_dredd Nov 19 '15 at 02:02

How to write an iterator for a binary search tree in c++ using nodes

1 Answers1