10 Replies - 35946 Views - Last Post: 29 July 2008 - 02:31 PM Rate Topic: -----

#1 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

making your own iterators

Posted 23 July 2008 - 07:36 PM

iterator tutorial

so i've read that source as to how to make your own iterator. just two questions: is it well-written and accurate, ala, is it worth following? and how does one go about making a const_iterator?

what i'm using it for is my own generic data container which i'm making emulate the STL containers. so that requires that i have an iterator for it, so i can use 'DataStructure::iterator.'

at the core of the data structure is a STL list. at a high-level, the data structure is essentially a list that can hold multiple values for each element and has special sorting functions. but basically, as far as the client is concerned, it functions just like a STL list. as such, i was planning on simply making each datastructure::iterator function call the equivalent list::iterator function(with proper adjustments to make this work though).


also, wth is std::iterator and how do i use it(explained in simple terms please :) )?

This post has been edited by The Architect 2.0: 23 July 2008 - 07:39 PM


Is This A Good Question/Topic? 0
  • +

Replies To: making your own iterators

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4332
  • View blog
  • Posts: 12,127
  • Joined: 18-April 07

Re: making your own iterators

Posted 23 July 2008 - 09:24 PM

1. Yes the site you reference and O'Reilly in general make great tutorial pages. Sometimes a little high level, but if you can understand them just fine they will work great for you.

2. O'Reilly Network -- What is an Iterator This link will tell you more about iterators and this is page 4 which shows you about const_iterators. Const_iterators are essentially the same as the other iterators but that, as you probably guessed, you are saying you will not modify the contents of the container list. Thus you can only do things like print or display data, not manipulate the content the iterator points to.

3. That sounds like a good first approach to directly map your external iterator functionality to the internal list iterator as long as you account for all the boundaries which it sounds like you are aware of.

4. std::iterator is the base class of iterators. You can inherit from it to make your own iterators. You can get a clue of this in the following article...

C++ and STL: Take Advantage of STL Algorithms by Implementing a Custom Iterator

Hope I got everything with this. :)
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: making your own iterators

Posted 23 July 2008 - 10:42 PM

we are not iterator counting ninjas (or some other kind of ninjas) here are DIC?
Was This Post Helpful? 0
  • +
  • -

#4 no2pencil  Icon User is online

  • Toubabo Koomi
  • member icon

Reputation: 5246
  • View blog
  • Posts: 27,062
  • Joined: 10-May 07

Re: making your own iterators

Posted 23 July 2008 - 10:51 PM

LOL! Here at D.I.C. we be shtick reminding ninjas :snap:
Was This Post Helpful? 0
  • +
  • -

#5 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

Re: making your own iterators

Posted 24 July 2008 - 12:51 AM

um...is it me or is some of the text wrong?

it says using the dereference operator on STL containers' iterators returns a COPY of an element(according to the standard). wouldn't that mean that any operation i performed WOULD NOT change the element value in the container? cause my test shows that i CAN change the value of the element, meaning that a REFERENCE is returned.

basically, the text is wrong and the code is right. so, did i miss something or is the previous statement correct?
Was This Post Helpful? 0
  • +
  • -

#6 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: making your own iterators

Posted 24 July 2008 - 06:52 AM

I can not find the text you are referring to.

While the STL containers often do deal with copies of an object rather than the object itself the standard iterator should reference the object stored in the container. However, there are specialized iterators which return a "pass-by-value" copy of the element -- for example the iterator talked about in the microsoft article there refers to a custom iterator with a requirement to "pass-by-value" and so it does. But this is a custom iterator -- the standard ones pass by reference (in fact the simplest iterator is a pointer into an array).
Was This Post Helpful? 0
  • +
  • -

#7 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: making your own iterators

Posted 24 July 2008 - 07:06 PM

View PostThe Architect 2.0, on 24 Jul, 2008 - 12:51 AM, said:

um...is it me or is some of the text wrong?

it says using the dereference operator on STL containers' iterators returns a COPY of an element(according to the standard). wouldn't that mean that any operation i performed WOULD NOT change the element value in the container? cause my test shows that i CAN change the value of the element, meaning that a REFERENCE is returned.

basically, the text is wrong and the code is right. so, did i miss something or is the previous statement correct?


The definition of operator* should be approximately:

T& operator*();

What you're seeing above might be true for an input iterator, but is definitely not true for a forward iterator. Though std::istream_iterator uses a reference type as a return value for operator*.


Here's an example of an iterator and a simple container:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template <typename T>
class fixed_array
{
    public:

        typedef int size_type;

        class iterator 
        {
            public:
                typedef iterator self_type;
                typedef T value_type;
                typedef T& reference;
                typedef T* pointer;
                typedef std::forward_iterator_tag iterator_category;
                typedef int difference_type;
                iterator(pointer ptr) : ptr_(ptr) { }
                self_type operator++() { self_type i = *this; ptr_++; return i; }
                self_type operator++(int junk) { ptr_++; return *this; }
                reference operator*() { return *ptr_; }
                pointer operator->() { return ptr_; }
                bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
                bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
            private:
                pointer ptr_;
        };

        class const_iterator 
        {
            public:
                typedef const_iterator self_type;
                typedef T value_type;
                typedef T& reference;
                typedef T* pointer;
                typedef int difference_type;
                typedef std::forward_iterator_tag iterator_category;
                const_iterator(pointer ptr) : ptr_(ptr) { }
                self_type operator++() { self_type i = *this; ptr_++; return i; }
                self_type operator++(int junk) { ptr_++; return *this; }
                const reference operator*() { return *ptr_; }
                const pointer operator->() { return ptr_; }
                bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
                bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
            private:
                pointer ptr_;
        };
     

        fixed_array(size_type size) : size_(size) {
            data_ = new T[size_];
        }

        size_type size() const { return size_; }
        
        T& operator[](size_type index) 
        { 
            assert(index < size_);
            return data_[index]; 
        }

        const T& operator[](size_type index) const
        {
            assert(index < size_);
            return data_[index];
        }

        iterator begin()
        {
            return iterator(data_);
        }

        iterator end()
        {
            return iterator(data_ + size_);
        }

        const_iterator begin() const
        {
            return const_iterator(data_);
        }

        const_iterator end() const
        {
            return const_iterator(data_ + size_);
        }

    private:
        T* data_;
        size_type size_;
};


int main()
{
    fixed_array<double> point3d(3);
    point3d[0] = 2.3;
    point3d[1] = 3.2;
    point3d[2] = 4.2;

    for(fixed_array<double>::iterator i = point3d.begin(); i != point3d.end(); i++)
    {
        std::cout << *i << " ";
    }

    std::cout << std::endl;

    std::vector<double> vec;
    std::copy(point3d.begin(), point3d.end(), std::back_inserter(vec));

    for(std::vector<double>::iterator i = vec.begin(); i != vec.end(); i++)
    {
        std::cout << *i << " ";
    }

    std::cout << std::endl;
    return 0;
}



Really, the iterators defined could have been random access iterators, but I suppose I didn't feel like implementing that (requires more operator overloads). As you can see, I didn't actually inherit from std::iterator, but it does make it a bit easier (as you don't have to have the typedefs in the class definition.)

This post has been edited by perfectly.insane: 24 July 2008 - 07:08 PM

Was This Post Helpful? 0
  • +
  • -

#8 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

Re: making your own iterators

Posted 27 July 2008 - 08:39 PM

what do i put in for the second parameter(value_type(?)) of std::iterator?

where normal iterators hold a reference/pointer to the container element, my custom iterator is going to be holding an instance of of a list iterator.

so, do i put in a list iterator as the value_type, or something else?
Was This Post Helpful? 0
  • +
  • -

#9 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: making your own iterators

Posted 28 July 2008 - 03:10 AM

value_type should be the type that the container is holding. For example, if one has a std::list<int>, then the value_type in std::list<int>::iterator will be int. Likewise, pointer will be int*, and reference will be int&.
Was This Post Helpful? 0
  • +
  • -

#10 The Architect 2.0  Icon User is offline

  • D.I.C Regular

Reputation: 37
  • View blog
  • Posts: 351
  • Joined: 22-May 08

Re: making your own iterators

Posted 28 July 2008 - 06:25 PM

but this iterator holds a list<String>::iterator.

what do i put in in this case?
Was This Post Helpful? 0
  • +
  • -

#11 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: making your own iterators

Posted 29 July 2008 - 02:31 PM

Then value_type would be a String.

The example I gave shows this:

template <typename T>  
class fixed_array  
{  
    public:  
  
        typedef int size_type;  
  
        class iterator   
        {  
            public:  
                typedef iterator self_type;  

                // value_type will be the same type as the template
                // parameter.
                typedef T value_type;  
                typedef T& reference;  
                typedef T* pointer;  



Basically, inheriting an iterator class from std::iterator<Category, T> does this for you (gives you the required typedefs). So, the _Tp template parameter in this case would be T. The category parameter depends on what type of iterator you want (input, output, forward, bidirectional, and random access), but will need to be something like std::random_access_iterator_tag (in the case of a random access iterator).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1