0

I need an STL-like bidirectional iterator (operator<, begin(), rbegin(), end(), rend()) as an inner class to the following (I already spent considerable time all by myself to put together a working tree from a C# article in J of Object Tech and translated it to C++):

template<typename K, typename V> class rbtree {  
public:  
  rbtree(){  
    root = NULL;  
    numberElements = 0;  
    insertedNode = NULL;  
    nodeBeingDeleted = NULL; // Set in DeleteNode  
    siblingToRight = false; // Sibling of curNode  
    parentToRight = false; // Of grand parent  
    nodeToDeleteRed = false; // Color of deleted node  
  }  
  //...  
private:  
  struct Node {  
    // Fields  
    K key; // Generic object held by each node  
    Node* left; Node* right; Node* parent; // Links to children and parent  
    bool red;// = true; // Color of node  
    // Constructor  
    Node(){  
      red = true;  
    }  
    Node(K key, Node* parent) {  
      this->key = key;  
      this->parent = parent;  
      left = NULL; right = NULL;  
      red = true;  
    }  
  };  
  // Fields  
  Node* root;  
  //...  
};
Michael Petrotta
  • 59,888
  • 27
  • 145
  • 179
  • Indent all code lines by four spaces (or more) for indentantion, syntax hilight and automatic escaping. – Tronic Mar 01 '10 at 18:39
  • select your code and press the "101010" button – f4. Mar 01 '10 at 18:40
  • This reads like a spec for a piece of contract programming, not a question... – user9876 Mar 01 '10 at 18:42
  • Indeed, where is the question? – Georg Fritzsche Mar 01 '10 at 18:42
  • I hope you did not forget to add the destructors after translating from C# – David Rodríguez - dribeas Mar 01 '10 at 19:22
  • Thanks for the comments, guys! Trying to get up to speed here. Spec for contract programming? Sort of. Spec and contractor: Professor; me student, but 57+. Question is STL-like iterator (op++, begin(), end())matching the code fragment –  Mar 01 '10 at 19:31
  • As to David Rodriguez: Thanks, guess destructor is almost a no-brainer, but STL-like iterator not. Thx –  Mar 01 '10 at 19:42
  • In all honesty: when someone mentions a far away deadline that is well within the limits of the task, that his solution is a copy of someone else's C# implementation and what he got so far is minimal I don't suspect "learning" to be the motivation. – pmr Mar 02 '10 at 09:29
  • Hey, pmr, I came here, cuz Stackoverflow has been hyped as THE forum for answers to tricky questions (by Charles Franklin, Hanselman?). It IS a tricky one for me and I shared my motives honestly. I can hardly contain my disappointment about the debating club here. –  Mar 02 '10 at 14:08

1 Answers1

2

You would be suprised to know that a std::set is implemented as an Red-Black Tree. What are your reasons for writing one yourself?

For a real answer: Writing iterators isn't trivial. You should read about the common differences between iterator requirements. This Stackoverflow question is a kind of duplicate of your question and gives useful hints.

Community
  • 1
  • 1
pmr
  • 58,701
  • 10
  • 113
  • 156
  • Reason for reinventing? Learning. (see comment above) Wouldn´t need to ask, if it was really trivial. Thx –  Mar 01 '10 at 19:35
  • @gue22: If you're learning, then going and asking for the answer doesn't exactly teach you a whole lot. Open up the source code for `std::set` and you can see a working implementation all day long. – Billy ONeal Mar 01 '10 at 23:56
  • Thanks, Billy, that´s what I´m going to try next. I simply hoped for a quick answer here, cuz I got an exam tomorrow and the deadline on Fri. –  Mar 02 '10 at 14:20