Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Dec 22nd, 2008, 7:44 PM   #1
titaniumdecoy
Programming Guru

 
titaniumdecoy's Avatar
 
Join Date: Nov 2005
Location: California
Posts: 1,535
Rep Power: 11 titaniumdecoy will become famous soon enoughtitaniumdecoy will become famous soon enough
Send a message via AIM to titaniumdecoy
Custom iterator

I know how to use iterators for existing types such as std::list. I am writing my own data type (a skip list) which I am modeling on STL containers. How can I write an iterator for my own data type? I cannot seem to find a basic iterator class to derive from.
titaniumdecoy is offline   Reply With Quote
Old Dec 23rd, 2008, 8:13 AM   #2
Poindexter
Programmer
 
Join Date: Dec 2008
Posts: 72
Rep Power: 6 Poindexter is on a distinguished road
Re: Custom iterator

Iterators are sets of rules based on the behaviour of pointers. Just follow the rules in your iterator class and that's all you need. This is a class with a forward iterator.
c++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <iterator>
  3.  
  4. using namespace std;
  5.  
  6. class ForwardList
  7. {
  8. private:
  9. struct node
  10. {
  11. int _value;
  12. node *_next;
  13.  
  14. node(int value, node *next):
  15. _value(value), _next(next) {}
  16. };
  17.  
  18. class list_iterator
  19. {
  20. private:
  21. node *_value;
  22. public:
  23. list_iterator(node *value):
  24. _value(value) {}
  25.  
  26. list_iterator& operator++();
  27. list_iterator operator++(int);
  28. int& operator*();
  29. bool operator!=(const list_iterator& rhs) const;
  30. };
  31.  
  32. node *_head;
  33. size_t _size;
  34. public:
  35. typedef list_iterator iterator;
  36. typedef const list_iterator const_iterator;
  37. typedef size_t size_type;
  38.  
  39. ForwardList():
  40. _head(0), _size(0) {}
  41. ~ForwardList();
  42.  
  43. iterator begin() { return iterator(_head); }
  44. const_iterator begin() const { return iterator(_head); }
  45. iterator end() { return iterator(0); }
  46. const_iterator end() const { return iterator(0); }
  47. size_type size() const { return _size; }
  48.  
  49. void prepend(int value);
  50. };
  51.  
  52. ForwardList::list_iterator& ForwardList::list_iterator::operator++()
  53. {
  54. _value = _value->_next;
  55. return *this;
  56. }
  57.  
  58. ForwardList::list_iterator ForwardList::list_iterator::operator++(int)
  59. {
  60. ForwardList::list_iterator temp = *this;
  61. _value = _value->_next;
  62. return temp;
  63. }
  64.  
  65. int& ForwardList::list_iterator::operator*()
  66. {
  67. return _value->_value;
  68. }
  69.  
  70. bool ForwardList::list_iterator::operator!=(const list_iterator& rhs) const
  71. {
  72. return _value != rhs._value;
  73. }
  74.  
  75. ForwardList::~ForwardList()
  76. {
  77. while (_head != 0)
  78. {
  79. ForwardList::node *temp = _head->_next;
  80. delete _head;
  81. _head = temp;
  82. }
  83. }
  84.  
  85. void ForwardList::prepend(int value)
  86. {
  87. _head = new node(value, _head);
  88. ++_size;
  89. }
  90.  
  91. void main()
  92. {
  93. ForwardList list;
  94.  
  95. cout << "list size: " << list.size() << '\n';
  96.  
  97. for (int i = 0; i < 10; ++i)
  98. list.prepend(i);
  99.  
  100. cout << "list size: " << list.size() << '\n';
  101.  
  102. ForwardList::iterator iter = list.begin();
  103.  
  104. while (iter != list.end())
  105. cout << *iter++ << ' ';
  106. cout << endl;
  107.  
  108. iter = list.begin();
  109.  
  110. while (iter != list.end())
  111. {
  112. cout << *iter << ' ';
  113. ++iter;
  114. }
  115. cout << endl;
  116. }
Forward iterators support copying, assignment, dereferencing, prefix and postfix increment, and comparison. I left out the stuff that isn't used. Strictly speaking, it also needs an operator-> and operator==.
Poindexter is offline   Reply With Quote
Old Dec 23rd, 2008, 10:41 AM   #3
Cache
Hobbyist
 
Join Date: Sep 2005
Posts: 331
Rep Power: 9 Cache is on a distinguished road
Re: Custom iterator

STL algorithms use trait types (usually obtained through std::iterator_traits) to get category and type information about iterators. If your iterator doesn't define the correct traits it either won't work with generic algorithms or a suboptimal implementation (for your iterator category) of the algorithm might be selected.

The following snippet will fail to compile using iterators as defined in the above post:
cpp Syntax (Toggle Plain Text)
  1. transform(
  2. begin
  3. , end
  4. , begin
  5. , bind1st(multiplies<int>(), 10)
  6. );

error C2039: 'iterator_category' : is not a member of ForwardList::list_iterator

The fix is to derive from std::iterator which will provide typedefs for the correct traits.
cpp Syntax (Toggle Plain Text)
  1. class list_iterator
  2. : public std::iterator<std::forward_iterator_tag, int>

Some interesting links:
http://www.angelikalanger.com/Articl...sInStdlib.html
http://www.cs.helsinki.fi/u/tpkarkka...iterators.html
http://www.boost.org/community/gener...ag_dispatching

"The C++ Standard Library: A Tutorial and Reference" (highly recommended for all things STL)
http://www.amazon.com/C-Standard-Lib.../dp/0201379260
Cache is offline   Reply With Quote
Old Dec 23rd, 2008, 10:48 AM   #4
Poindexter
Programmer
 
Join Date: Dec 2008
Posts: 72
Rep Power: 6 Poindexter is on a distinguished road
Re: Custom iterator

Thanks Cache, I totally forgot about traits because I don't write iterators much.
Poindexter is offline   Reply With Quote
Old Dec 23rd, 2008, 2:09 PM   #5
titaniumdecoy
Programming Guru

 
titaniumdecoy's Avatar
 
Join Date: Nov 2005
Location: California
Posts: 1,535
Rep Power: 11 titaniumdecoy will become famous soon enoughtitaniumdecoy will become famous soon enough
Send a message via AIM to titaniumdecoy
Re: Custom iterator

Thanks for the info. Since I am storing the data as a linked list of SkipNodes, would it be a good idea to make the SkipNode class itself an iterator class? Then I could just return a pointer to the first SkipNode in the list...
titaniumdecoy is offline   Reply With Quote
Old Dec 23rd, 2008, 6:04 PM   #6
Poindexter
Programmer
 
Join Date: Dec 2008
Posts: 72
Rep Power: 6 Poindexter is on a distinguished road
Re: Custom iterator

Yeah, you can do that.
Poindexter is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
custom iterator rwm C++ 16 May 18th, 2007 2:51 AM
Remove with iterator? titaniumdecoy C++ 6 Jun 12th, 2006 8:42 AM
How to create office xp like menus and other custom controls some1 C++ 5 Nov 8th, 2005 2:28 PM
Using Iterator on a HashMap Hockeyman Java 3 Jun 15th, 2005 4:31 AM
Custom Tiles/Sprites Aourhgad C++ 4 Jan 14th, 2005 1:49 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 3:15 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC