4

I'm implementing a map for an exercise and I'm at the point where I would have to iterate over it (done and working) but the problem is that I don't know how to implement a last element (presumably an empty link). I was thinking that I would attach some special kind of link (descendant of base link) which would then be attached to the last element and in this way I would be able to detect if I'm at the real last element or not. I wonder what will be your opinion about this idea and probably hear from you about some more traditional and regularly used techniques for doing this.

interesting
  • 149
  • 1
  • 10
smallB
  • 16,662
  • 33
  • 107
  • 151

3 Answers3

3

There are two ways to implement end: a dummy node and a singular iterator (i.e. NULL).

The problem with NULL is that you need to be able to get back to the structure if you decrement --end().

What GCC does is create a truncated dummy node in the map object itself. It has links but no data payload. It is maintained as the root of the tree, with a circular parent link that invokes special behavior. Semantically it might be a little messy, but C++-compliant semantics should be worth the hassle.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
  • @Potatoswatter I don't quite understand what do you mean by singular iterator. Could you please explain that? Thank you. – smallB Aug 15 '10 at 11:09
  • @smallB: in cases where `--` does not apply, such as stream iterators, you can just put the value `0` inside the iterator. In that case, the natural `end` of any structure is equal to the default value of the iterator. – Potatoswatter Aug 15 '10 at 11:17
  • @Potatoswatter so it is basically what I've had in mind talking about "special kind" of link isn't that so? – smallB Aug 15 '10 at 11:33
  • 1
    @smallB I guess so. The really special link is the parent link of the root. For details, see `bits/stl_tree.h` and `tree.cc` (static librayr source, not a header; unofficial mirror at http://archpub20.cs.ccu.edu.tw/cgi-bin/dwww?type=file&location=/usr/share/doc/libstdc%2B%2B6-doc/libstdc%2B%2B/html_user/tree_8cc-source.html, see http://gcc.gnu.org/svn.html for an official copy) – Potatoswatter Aug 15 '10 at 11:48
3

If your iterator isn't bidirectional then you don't really need end to point to anything (just use NULL in that case). end() only needs to have a real value in the case of a bidirectional iterator, because in that case you'll need to be able to move backwards from end() towards the beginning of the list.

The GNU C++ Library (what you get if you use std::map with GCC/G++) implements end() as a pointer to the root node of the tree. This way, if used in a bidirectional iterator you can access the root node to find the right most node in the tree (which is the node directly before end()).

Edit to explain an empty tree

The map itself always contains a node for the root of the tree (it's not a pointer, its a normal member node). When the tree is empty, both leaves of this node point to the node itself (as does end()). So in an empty tree begin() would return the same thing as end().

So we have something like this:

template<class T> struct node_t {
    T data;
    node_t *left;
    node_t *right;
};


template<class T> class map {
    private:
        node_t root;
    public:
        // ...
        iterator begin() { return iterator(root.left); }
        iterator end() { return iterator(&root); }
}
SoapBox
  • 20,457
  • 3
  • 51
  • 87
  • So what if we have one node? begin == end? Could you explain more? Do you mean to use dummy node as the root? – adf88 Aug 15 '10 at 11:13
  • The root node always exists, when the tree is empty the root node's left and right leaves are both NULL. So in an empty tree, begin() would point to the left leaf (which is NULL), and end would still point to the root node. – SoapBox Aug 15 '10 at 11:18
  • @SoapBox thanks for your example. But what will happen if you will try to dereference begin? Won't you get runtime error? Begin is a null. – smallB Aug 15 '10 at 11:28
  • I believe at initialization, the leaves should both point to the root, but +1 anyway. – Potatoswatter Aug 15 '10 at 11:34
  • In an empty tree, yes. But you shouldn't dereference being in an empty tree, because it's empty. – SoapBox Aug 15 '10 at 11:34
  • @SoapBox but isn't this method somewhat incompatibile with std approach where end points to "one past last"? – smallB Aug 15 '10 at 11:39
  • This is the std approach, as used by GCC 4.4.1. It doesn't physically point to one past last, but the code checks for this condition and treats it the same way as a one-past-last would. The problem with having a literal one-past-last is you have to take care that someone doesn't delete that node or move it or try to insert something after it, etc. – SoapBox Aug 15 '10 at 11:45
  • @smallB: One past the rigthmost node will ascend up to the root. Then you need to detect the circular link to prevent infinite recursion. (Some kind of root parent detection is necessary no matter what.) – Potatoswatter Aug 15 '10 at 11:51
  • @SoapBox and Potatoswatter another question arises when I think about root being as a "one past last" node (I like this idea BTW). Special care has to be taken when inserting and deleting, isn't that so? – smallB Aug 15 '10 at 12:03
  • Yes, but you'd have to take special care when inserting and deleting anyway, to make sure that your one-past-last node is still working correctly. – SoapBox Aug 15 '10 at 12:08
-1

Use dummy node for that.

adf88
  • 4,277
  • 1
  • 23
  • 21