How to use Iterator Adaptors?
Hi, I'm struggling to understand how to use Iterator Adaptors, due to a lack of simple examples. This is disappointing, given that supposedly "Using iterator_adaptor, you can easily implement an iterator class" (www.boost.org/libs/utility/iterator_adaptors.htm). Can anyone help, by explaining how to implement a random access iterator for a custom collection class? e.g.: template <class T> class DumbCollection { public: DumbCollection(T data[10]) { for (int i = 0; i < 10; i++) m_data[i] = data[i]; } iterator begin(); iterator end(); private: T m_data[10]; }; Thanks, Keith
--- At Mon, 3 Jun 2002 10:38:57 +0000, keithmac66 wrote:
Hi,
I'm struggling to understand how to use Iterator Adaptors, due to a lack of simple examples. This is disappointing, given that supposedly "Using iterator_adaptor, you can easily implement an iterator class" (www.boost.org/libs/utility/iterator_adaptors.htm). Can anyone help, by explaining how to implement a random access iterator for a custom collection class? e.g.:
template <class T> class DumbCollection { public: DumbCollection(T data[10]) { for (int i = 0; i < 10; i++) m_data[i] = data[i]; } iterator begin(); iterator end(); private: T m_data[10]; };
I assume that what you are looking for is the implementation of begin() and end(). The implementation is probably too long to include here. But I can give you some direction. iterator_adaptor is exactly that it adapts one iterator to another. To come from a container to an iterator you first need an iterator. However, boosts requirements on the base iterator are much less than a full- fledged iterator. Take a look at the documentation and implementation where it talks about default_iterator_policies. This shows you the functions that have to be implemented by your base iterator class. For random access iterators, you have to implement all of them. For simpler iterators you can implement less (there is another table describing the requirements). By implementing a base iterator then you should be able to follow the other recipies/examples for how to create the typedef and construct the iterators. Its all really based on your base iterator for your container. I have done several iterators over container like structures and this recipe works pretty well. There is a fair bit of code to get it all together. Hope this helped, ...Duane -- "If tyranny and oppression come to this land, it will be in the guise of fighting a foreign enemy." - James Madison
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020603150922.32043@mail.murphyslogic.com...
--- At Mon, 3 Jun 2002 10:38:57 +0000, keithmac66 wrote:
Hi,
I'm struggling to understand how to use Iterator Adaptors, due to a lack of simple examples. This is disappointing, given that lack of simple examples. This is disappointing, given that supposedly "Using iterator_adaptor, you can easily implement an iterator class" (www.boost.org/libs/utility/iterator_adaptors.htm). Can anyone help, by explaining how to implement a random access iterator for a custom collection class? e.g.:
template <class T> class DumbCollection { public: DumbCollection(T data[10]) { for (int i = 0; i < 10; i++) m_data[i] = data[i]; } iterator begin(); iterator end(); private: T m_data[10]; };
For this one, plain T* makes a fine iterator type, assuming you intend for it to iterate through the elements of m_data. However, if you want to do it with iterator_adaptor so that you don't have pointers hanging around, the answer is trivial: typedef boost::iterator_adaptor<T*, boost::default_iterator_policies> iterator;
iterator_adaptor is exactly that it adapts one iterator to another. To come from a container to an iterator you first need an iterator. However, boosts requirements on the base iterator are much less than a full- fledged iterator.
In fact, the Base type need not be an iterator at all. For example, the counting iterator adaptor can accept int as the Base type.
Take a look at the documentation and implementation where it talks about default_iterator_policies. This shows you the functions that have to be implemented by your base iterator class.
This statement is a bit misleading. It shows the functions that your Policies class must implement. -Dave
--- At Mon, 3 Jun 2002 14:09:07 -0400, David Abrahams wrote:
Take a look at the documentation and implementation where it talks about default_iterator_policies. This shows you the functions that have to be implemented by your base iterator class.
This statement is a bit misleading. It shows the functions that your Policies class must implement.
Ah, what I was meaning was to look at the implementations of the functions in default_iterator_policies. The implementation shows what this policy calls and what default_iterator_policies expectes the base iterator to be able to do. I have found it easier to write a simple "iterator like" class and use the default_iterator_policies than to write both an iterator and a policy. ...Duane
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020603191155.29997@mail.murphyslogic.com...
--- At Mon, 3 Jun 2002 14:09:07 -0400, David Abrahams wrote:
Take a look at the documentation and implementation where it talks about default_iterator_policies. This shows you the functions that have to be implemented by your base iterator class.
This statement is a bit misleading. It shows the functions that your Policies class must implement.
Ah, what I was meaning was to look at the implementations of the functions in default_iterator_policies. The implementation shows what this policy calls and what default_iterator_policies expectes the base iterator to be able to do. I have found it easier to write a simple "iterator like" class and use the default_iterator_policies than to write both an iterator and a policy.
That's a pretty wacky idea! You're putting the behaviors in the Base object, but the library "intends" for behaviors to be specified by the Policies. In other words, the "normal" approach is to treat the Base object as raw data, and while the policies implement the operations on that data. -Dave
--- At Tue, 4 Jun 2002 00:05:46 -0400, David Abrahams wrote:
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020603191155.29997@mail.murphyslogic.com...
--- At Mon, 3 Jun 2002 14:09:07 -0400, David Abrahams wrote:
Take a look at the documentation and implementation where it talks about default_iterator_policies. This shows you the functions that have to be implemented by your base iterator class.
This statement is a bit misleading. It shows the functions that your Policies class must implement.
Ah, what I was meaning was to look at the implementations of the functions in default_iterator_policies. The implementation shows what this policy calls and what default_iterator_policies expectes the base iterator to be able to do. I have found it easier to write a simple "iterator like" class and use the default_iterator_policies than to write both an iterator and a policy.
That's a pretty wacky idea! You're putting the behaviors in the Base object, but the library "intends" for behaviors to be specified by the Policies.
In other words, the "normal" approach is to treat the Base object as raw data, and while the policies implement the operations on that data.
I really love iterators. I have worked at trying to figure out the "right" way of doing a plain iterator. That is I have a "thing" that looks like a container and has APIs for "iterating" the container but those APIs dont really look like a standard iterator. The canonical example is a file iterator; iterate over the files in a directory. The directory appears to be a container with filenames as the members of the container. What would the base and policy objects be? The way I have been doing it would be to first use the default_iterator_policies. That's because I basically want a default iterator. I dont have any iterator to assign policies to yet. Next I define the simplest iterator required by the default_iterator_policies. This is usually a forward iterator if copying is practical given the nature of the API. Basically in the example, the iterator would hold a DIR structure and use the standard DIR APIs to "increment" and dereference the structure as required. So, what is the "normal" way of creating an iterator out of thin air as it were? ...Duane -- "If tyranny and oppression come to this land, it will be in the guise of fighting a foreign enemy." - James Madison
At 10:02 PM -0700 6/3/02, Duane Murphy wrote:
I really love iterators. I have worked at trying to figure out the "right" way of doing a plain iterator. That is I have a "thing" that looks like a container and has APIs for "iterating" the container but those APIs dont really look like a standard iterator.
The canonical example is a file iterator; iterate over the files in a directory. The directory appears to be a container with filenames as the members of the container.
I have gone back to this example several times in the last few years. I have finally decided that this is a bad idea, because a file system directory is not really a container. The container can be changed outside the currently executing program, and there is no "container-like" semantics to tell the program that the iterators into that container are invalid. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> My name is Bobba Fett. You killed my father, prepare to die!
"Marshall Clow" <marshall@idio.com> wrote in message news:p0511190fb921ff8971bf@[192.168.16.220]...
At 10:02 PM -0700 6/3/02, Duane Murphy wrote:
The canonical example is a file iterator; iterate over the files in a directory. The directory appears to be a container with filenames as the members of the container.
I have gone back to this example several times in the last few years.
I have finally decided that this is a bad idea, because a file system directory is not really a container. The container can be changed outside the currently executing program, and there is no "container-like" semantics to tell the program that the iterators into that container are invalid.
?? Except in some implementations' debug mode, none of the standard containers tell the program when their iterators become invalid either.
"Marshall Clow" <marshall@idio.com> wrote in message news:p0511190fb921ff8971bf@[192.168.16.220]...
At 10:02 PM -0700 6/3/02, Duane Murphy wrote:
The canonical example is a file iterator; iterate over the files in a directory. The directory appears to be a container with filenames as the members of the container.
I have gone back to this example several times in the last few years.
I have finally decided that this is a bad idea, because a file system directory is not really a container. The container can be changed outside the currently executing program, and there is no "container-like" semantics to tell the program that the iterators into that container are invalid.
?? Except in some implementations' debug mode, none of the standard containers tell the program when their iterators become invalid either.
Yes, the container's iterators are under your control. You can ensure that the iterators stay valid by not changing the container. (or by making only 'safe' changes). [ Multi-threaded programs are more complicated, but can be solved, too ] You cannot get any such guarantees for a directory. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> My name is Bobba Fett. You killed my father, prepare to die!
At 7:19 PM +0200 6/7/02, Hendrik Schober wrote:
"Marshall Clow" <marshall@idio.com> wrote:
[...] You cannot get any such guarantees for a directory.
What's the difference to non-iterator access to a folder?
You can design the interface to the object that you are using to walk a folder so that it can notify the calling program if the underlying folder is modified. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> My name is Bobba Fett. You killed my father, prepare to die!
Hi All, Is there an interest into having a power() template calculating the N-th power of any number, when N is known at compile-time ?t uses the algorithm of the STL power function(), and runs between two or three times faster, and maybe could be of interest in the " <boost/math/common_factor.hpp> which provides run-time and compile-time evaluation of the greatest common divisor (GCD) or least common multiple (LCM) It simply works this way, for example to have PI at exponent three : double a = power_const<3>( 3.14159) As the single include file is very short, please apologize if I give it straight on, just to save your time and to have an idea how badly you judge my poor code ;) Thank for your understanding. /****************************************************************************** ** power_const.h ******************************************************************************/ template< class _Tp, int Exp, int Bool > struct power_const_t { }; template< class _Tp, int Exp > struct power_const_t< _Tp, Exp, 0 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return power_const_t<T, (Exp >> 1), ( (Exp >> 1) & 1) >::eval( the_t, the_P * the_P ); } }; template< class _Tp, int Exp > struct power_const_t< _Tp, Exp, 1 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return the_P * power_const_t<T, (Exp >> 1), ( (Exp >> 1) & 1) >::eval( the_t, the_P * the_P ); } }; template< class _Tp > struct power_const_t< _Tp, 1, 0 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return the_P ; } }; template< class _Tp > struct power_const_t< _Tp, 1, 1 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return the_P ; } }; template< class _Tp > struct power_const_t< _Tp, 0, 0 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return 1 ; } }; template< class _Tp > struct power_const_t< _Tp, 0, 1 > { inline static _Tp eval(const _Tp & the_t, const _Tp & the_P ) { return the_P * the_P ; } }; template< class _Tp, int N > inline _Tp power_const( const _Tp & the_t ) { return power_const_t<T, N, ( N & 1 ) >::eval( the_t, the_t ); }; template< class _Tp, int N > inline _Tp power_const( const _Tp & the_t ) { return power_const_t<T, N, ( N & 1 ) >::eval( the_t, the_t ); }; /****************************************************************************** ** power_const.h ******************************************************************************/ [Non-text portions of this message have been removed]
So, what is the "normal" way of creating an iterator out of thin air as it were?
That was the question in my mind, which the first sentence of the Iterator Adaptors documentation led me to hope it would answer: "The Iterator Adaptor library allows you transform an arbitrary ``base'' type into a standard-conforming iterator". If the base type is a container, how do you do it? - Keith MacDonald "Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020604050249.610@mail.murphyslogic.com...
--- At Tue, 4 Jun 2002 00:05:46 -0400, David Abrahams wrote: <snip> So, what is the "normal" way of creating an iterator out of thin air as it were?
...Duane
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020604050249.610@mail.murphyslogic.com...
--- At Tue, 4 Jun 2002 00:05:46 -0400, David Abrahams wrote:
The canonical example is a file iterator; iterate over the files in a directory. The directory appears to be a container with filenames as the members of the container.
What would the base and policy objects be?
The way I have been doing it would be to first use the default_iterator_policies. That's because I basically want a default iterator.
You have a misapprehension about the meaning of "default" here. In no sense is it intended to create "default iterators" (whatever that is). Probably default_iterator_policies is misnamed, and should be called "passthrough_iterator_policies" or something. In general, default_iterator_policies is meant to be used as a base class for other policies, because it provides useful default policy behaviors.
I dont have any iterator to assign policies to yet.
The policies are supposed to implement the core operations of the iterator using the Base object. You can, of course, stick the neccessary functionality in the Base object and use the default policies, as you are doing, but it seems a little unnatural to me.
Next I define the simplest iterator required by the default_iterator_policies.
Please, don't say that! default_iterator_policies doesn't require an iterator, and if you define the simplest Base object required, you're not defining an iterator. Witness counting_iterator_adaptor, which can accept an integer as a Base object.
This is usually a forward iterator if copying is practical given the nature of the API. Basically in the example, the iterator would hold a DIR structure and use the standard DIR APIs to "increment" and dereference the structure as required.
So, what is the "normal" way of creating an iterator out of thin air as it were?
If you have a DIR structure, I would use that as the Base object directly, then write a Policies class which implements the operations on it. -Dave
--- At Tue, 4 Jun 2002 09:45:12 -0400, David Abrahams wrote:
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020604050249.610@mail.murphyslogic.com...
--- At Tue, 4 Jun 2002 00:05:46 -0400, David Abrahams wrote: I dont have any iterator to assign policies to yet.
The policies are supposed to implement the core operations of the iterator using the Base object. You can, of course, stick the neccessary functionality in the Base object and use the default policies, as you are doing, but it seems a little unnatural to me.
This is usually a forward iterator if copying is practical given the nature of the API. Basically in the example, the iterator would hold a DIR structure and use the standard DIR APIs to "increment" and dereference the structure as required.
So, what is the "normal" way of creating an iterator out of thin air as it were?
If you have a DIR structure, I would use that as the Base object directly, then write a Policies class which implements the operations on it.
[ Giant light bulb goes on! ] Now I get it. Thank you very much for this explaination. Everytime I write an iterator there is almost always some data structure that is required in the iterator for me to use. You have simply "constructed" that part of the iterator through the base template parameter. I have been working way to hard to make this work. When I first did things this way, I went and wrapped some data structure in all kinds of methods. I see now that I was making too much work for myself. Simply specify the object that is the base and access it directly; no additional objects needed. Treating base as a member variable is acceptable. Thank you for this enlightening discussion. I will follow this pattern for my future iterators. ...Duane
--- At Tue, 4 Jun 2002 07:25:05 -0700, Duane Murphy wrote:
--- At Tue, 4 Jun 2002 09:45:12 -0400, David Abrahams wrote:
"Duane Murphy" <duanemurphy@mac.com> wrote in message news:20020604050249.610@mail.murphyslogic.com...
--- At Tue, 4 Jun 2002 00:05:46 -0400, David Abrahams wrote: I dont have any iterator to assign policies to yet.
The policies are supposed to implement the core operations of the iterator using the Base object. You can, of course, stick the neccessary functionality in the Base object and use the default policies, as you are doing, but it seems a little unnatural to me.
This is usually a forward iterator if copying is practical given the nature of the API. Basically in the example, the iterator would hold a DIR structure and use the standard DIR APIs to "increment" and dereference the structure as required.
So, what is the "normal" way of creating an iterator out of thin air as it were?
If you have a DIR structure, I would use that as the Base object directly, then write a Policies class which implements the operations on it.
[ Giant light bulb goes on! ]
Now I get it. Thank you very much for this explaination.
Everytime I write an iterator there is almost always some data structure that is required in the iterator for me to use. You have simply "constructed" that part of the iterator through the base template parameter. I have been working way to hard to make this work.
When I first did things this way, I went and wrapped some data structure in all kinds of methods. I see now that I was making too much work for myself. Simply specify the object that is the base and access it directly; no additional objects needed. Treating base as a member variable is acceptable.
Member variable isnt exactly the right terminology. Maybe, using base as a data structure rather than an object would be more correct.
Thank you for this enlightening discussion. I will follow this pattern for my future iterators.
...Duane
participants (1)
-
David Abrahams -
Duane Murphy -
Hendrik Schober -
Keith MacDonald
-
keithmac66 -
Marshall Clow -
ravioli＠softhome.net