Non-template functions that take iterators
Andre Majorel
unknown STL containers of a known value type, without making the
function a template ?
Ideally, I would like to be able to write :
myfunc.h :
typedef ... mytype;
myfunc (iterator<mytype> begin, iterator<mytype> end);
use.cc :
std::vector<mytype> v;
std::list<mytype> l;
myfunc (v.begin (), v.end ());
myfunc (l.begin (), l.end ());
I'm aware it can be done by making myfunc() a template but I'd
rather avoid the code and header bloat if possible.
Since (I understand) STL iterators are pure templates, (their
methods are not virtual), I'm afraid this might be a lost cause
but I ask anyway in case I'm missing something...
Thanks in advance.
--
André Majorel <amaj...@teezer.fr> (it's really "teaser")
http://www.teaser.fr/~amajorel/
A properly functioning grocery clerk is a linear system -- Erik Spjut
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
cjoy
"Andre Majorel" <a...@vulcain.knox.com> wrote in message
news:slrn9i9d...@vulcain.knox.com...
> Is it possible to define a function that take iterators on
> unknown STL containers of a known value type, without making the
> function a template ?
>
> Ideally, I would like to be able to write :
>
> myfunc.h :
> typedef ... mytype;
> myfunc (iterator<mytype> begin, iterator<mytype> end);
>
> use.cc :
> std::vector<mytype> v;
> std::list<mytype> l;
> myfunc (v.begin (), v.end ());
> myfunc (l.begin (), l.end ());
>
Yes, it's possible. One solution is given in the paper shown below which
gives an adaptor to do this.
See the threads last week on "Paper: Variant Objects for Generic Algorithms"
and "virtual iterators" for more discussion.
Variant Objects for Generic Algorithm Design:
http://www.geocities.com/corwinjoy/vo/VariantObject.htm
Frans Meijer
Andre Majorel <a...@vulcain.knox.com> schreef in berichtnieuws
slrn9i9d...@vulcain.knox.com...
> Is it possible to define a function that take iterators on
> unknown STL containers of a known value type, without making the
> function a template ?
>
> Ideally, I would like to be able to write :
>
> myfunc.h :
> typedef ... mytype;
> myfunc (iterator<mytype> begin, iterator<mytype> end);
>
> use.cc :
> std::vector<mytype> v;
> std::list<mytype> l;
> myfunc (v.begin (), v.end ());
> myfunc (l.begin (), l.end ());
>
> I'm aware it can be done by making myfunc() a template but I'd
> rather avoid the code and header bloat if possible.
>
To what purpose?
If your custom function is only used with one type of iterator
(eg, std::vector<mytype>::iterator) you could write it non-templatized.
But you'd have to rewrite it if you decide to use std::map.
You'd have to write both versions if you want to use both std::vector and
std::map
The templatized version would be specialized for std::vector if you use
std::vector, or std::map if you use std::map, or both if you use both.
There is /no/ code bloat for the templatized version. Templates are only
specialized for the types you use.
Michiel Salters
>
>Is it possible to define a function that take iterators on
>unknown STL containers of a known value type, without making the
>function a template ?
Yes and no. The iterator type of list<int> differs from the
iterator type of vector<int>. You can have 2 overloads of a function;
one for list<int>::iterator and one for vector<int>::iterator.
However, this violates the spirit of the STL. My container is just
as good as the STL containers, and the STL algorithms don't
discriminate. You should also accept my iterators, even though
you can't name them. The only way to do so is by using a template.
>Ideally, I would like to be able to write :
>
> myfunc.h :
> typedef ... mytype;
> myfunc (iterator<mytype> begin, iterator<mytype> end);
>
> use.cc :
> std::vector<mytype> v;
> std::list<mytype> l;
> myfunc (v.begin (), v.end ());
> myfunc (l.begin (), l.end ());
>
>I'm aware it can be done by making myfunc() a template but I'd
>rather avoid the code and header bloat if possible.
Where did you get the idea that templates cause code bloat? Return that
idea & get a refund :).
Seriously, templates will seem to cause code bloat because it allows you
to get a large of executable from a little source. If you write all N
overloads of a function yourself, you'll get the same size executable.
But because of the work you've done you'll probably accept it. If the
compiler writes these N overloads for you ( using your template ), the
resulting executable will be almost the same size. (Not counting debug
information).
Regards,
Michiel Salters
--
Michiel Salters
Consultant Technical Software Engineering
CMG Trade, Transport & Industry
Michiel...@cmg.nl
Andre Majorel
>In article <slrn9i9d...@vulcain.knox.com>, Andre Majorel says...
>>
>>Is it possible to define a function that take iterators on
>>unknown STL containers of a known value type, without making the
>>function a template ?
>
>Yes and no. The iterator type of list<int> differs from the
>iterator type of vector<int>. You can have 2 overloads of a function;
>one for list<int>::iterator and one for vector<int>::iterator.
>However, this violates the spirit of the STL. My container is just
>as good as the STL containers, and the STL algorithms don't
>discriminate. You should also accept my iterators, even though
>you can't name them. The only way to do so is by using a template.
That's what I feared.
>Seriously, templates will seem to cause code bloat because it allows you
>to get a large of executable from a little source. If you write all N
>overloads of a function yourself, you'll get the same size executable.
>But because of the work you've done you'll probably accept it. If the
>compiler writes these N overloads for you ( using your template ), the
>resulting executable will be almost the same size. (Not counting debug
>information).
The code is bloated compared to what it would be if using
iterators only involved, say, calling virtual functions.
It's unfortunate because this contradicts somewhat one of the
goals of the STL that is, I understand, to let programmers
freely pick the best container for the job. If your function is
big enough you will think twice before using it again with a
different container.
Disclaimer: I'm *not* implying that implementing the STL using
polymorphism instead of templates is possible or even desirable.
You have probably all learned to live with this nasty aspect of
the STL, but I'm new to this. I was under the impression that
there was something magical about the STL and I've just been
told Santa doesn't exist.
The lesson for me is that, if you have a function that goes :
template<typename Iterator>
myfunc (Iterator begin, Iterator end)
{
for (Iterator i = begin; i != end; i++)
{
// 200 lines of code
}
}
you'd better write it :
template<typename Iterator>
myfunc (Iterator begin, Iterator end)
{
for (Iterator i = begin; i != end; i++)
foo (*i);
}
void foo (mytype)
{
// 200 lines of code
}
--
André Majorel <amaj...@teezer.fr> (it's really "teaser")
http://www.teaser.fr/~amajorel/
A properly functioning grocery clerk is a linear system -- Erik Spjut
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
stonerCT
> >you can't name them. The only way to do so is by using a template.
>
> That's what I feared.
Feared?
You seem to be concerned that templated code will unnecessarily increase
your executable size. Actually you should be aware that template
instantiation is typically only performed on-demand. If you only reference
one type throughout your whole program to interact with this algorithm,
there would literally be no difference in the resulting code-size than if
you wrote it non-templated. If you use twenty distinct types with the
algorithm, there would be no code-size difference between using a simple
templated function or doing it the long way and writing out (or worse,
copy/pasting) separate functions for each different type you reference in
your program... hey if that floats your boat..
> template<typename Iterator>
> myfunc (Iterator begin, Iterator end)
> {
> for (Iterator i = begin; i != end; i++)
> foo (*i);
> }
>
> void foo (mytype)
> {
> // 200 lines of code
> }
I will assume you are worried here about large inlined template functions
(though the myfunc<>() function above does not actually appear to be
inlined, unless it is really inside a class {} block) causing code bloat. In
that case, it is likely a good idea not to inline the entire function. Yet,
templated code does not have to only be inlined though; it is perfectly
valid to write templated functions that can have standard linkage. On many
platforms, the compiler will automatically instantiate the function as
necessary and you won't even have to think about it further. On other
environments, you may be required to explicitly instantiate the functions of
various types that you use, but it is only one simple line of code per
instantiation, and does not affect the resulting code size. If the function
is written with regular linkage, having the declaration in a shared header
file is all that is required (just as with any other function).
> template<typename Iterator>
> myfunc (Iterator begin, Iterator end)
> {
> for (Iterator i = begin; i != end; i++)
> {
> // 200 lines of code
> }
> }
Given that neither function is inlined, this is fully equivalent to the code
in the other example. There is no detriment to your program due to using
templates under these circumstances. If you still believe otherwise, you are
mistaken.
hys
Dave Harris
> > template<typename Iterator>
> > myfunc (Iterator begin, Iterator end)
> > {
> > for (Iterator i = begin; i != end; i++)
> > foo (*i);
> > }
> >
> > void foo (mytype)
> > {
> > // 200 lines of code
> > }
>
> I will assume you are worried here about large inlined template
> functions (though the myfunc<>() function above does not actually
> appear to be inlined, unless it is really inside a class {}
> block) causing code bloat.
He's worried about instantiating myfunc with a dozen different iterator
types, where they all have the same value_type (namely mytype). The idea
is that objects of type mytype are being stored in a variety of
containers.
He expects the above form to replicate the 2 lines of myfunc 12 times, and
the 200 lines of foo only once. Whereas the other form, with foo manually
inlined, replicates the 200 lines of foo 12 times as well. Thus the above
form is less bloated by a factor of about 100. This is about inlining foo
into myfunc, not inlining myfunc into its callers.
I think he's right; his understanding is pretty good.
If iterators had dynamic polymorphism, he could write it as:
template <typename T>
class Pit { // Polymorphic iterator.
// ...
};
void myfunc( Pit<mytype> begin, Pit<mytype> end ) {
for (Pit<mytype> i = begin; i != end; ++i) {
// 200 lines of code using *i.
}
}
This uses dynamic polymorphism instead of compile-time polymorphism.
Myfunc is not a template, so there will (probably) be less bloat.
Against that we have the overhead of the indirection and virtual function
calls, plus the difficulty of designing and implementing Pit<T>. I imagine
we need a letter-and-envelope idiom, which in turn means heap allocation,
and possible exceptions due to heap-exhaustion when copying iterators.
Also we need a virtual operator!=(), which is often a problem area. It's
all doable, but it's not trivial or especially efficient. (See the earlier
"virtual iterators" thread for more details.)
Another approach would be to use a single sequence object instead of a
pair of iterators, and pass by reference to avoid copying and slicing
problems (which tend to destroy polymorphism). Eg:
// Abstract polymorphic base class for sequences.
template <typename T>
class Seq {
public:
virtual bool empty() const = 0;
virtual T &operator*() = 0;
virtual void operator++() = 0;
};
// Concrete implementation based on iterators.
template <typename iterator>
class IteratorSeq : public Seq<
iterator_traits<iterator>::value_type> {
iterator first;
iterator last;
typedef iterator_traits<iterator>::value_type T;
public:
IteratorSeq( iterator begin, iterator end ) :
first(begin), last(end) {}
virtual bool empty() const { return first == last; }
virtual T &operator*() { return *first; }
virtual void operator++() { ++first; }
};
// Factory function for containers.
template <typename container>
inline IteratorSeq<container::iterator> seq( container &c ) {
return IteratorSeq( c.begin(), c.end() );
}
// Example of use - not a template.
void myfunc( Seq<mytype> &s ) {
for ( ; !s.empty(); ++s) {
// 200 lines of code using *s.
}
}
// Example of caller.
void demo( std::vector<mytype> &v ) {
myfunc( seq( v ) );
}
This is incomplete code, but I think it shows how a different approach to
sequences can make life easier. Here we provide dynamic polymorphism
without the drawbacks of heap allocation or letter/envelope, and we don't
need a virtual operator!=().
Sequence objects are not part of the current C++ standard. I am lobbying
for them to be included in future standards. Meanwhile,
IteratorSeq<iterator> shows how this approach can be layered on top of the
current std iterators. If Andre Majorel really needs dynamically
polymorphism, he might find this approach easier than the "virtual
iterators" approach discussed in the earlier thread.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
Andre Majorel
>You seem to be concerned that templated code will unnecessarily increase
>your executable size.
Yes.
>Actually you should be aware that template
>instantiation is typically only performed on-demand. If you only reference
>one type throughout your whole program to interact with this algorithm,
>there would literally be no difference in the resulting code-size than if
>you wrote it non-templated.
Yes.
>If you use twenty distinct types with the
>algorithm, there would be no code-size difference between using a simple
>templated function or doing it the long way and writing out (or worse,
>copy/pasting) separate functions for each different type you reference in
>your program...
Yes but that's not what I'm comparing it to. I'm comparing it to
code that uses virtual methods.
[Snip]
>Given that neither function is inlined, this is fully equivalent to the code
>in the other example. There is no detriment to your program due to using
>templates under these circumstances. If you still believe otherwise, you are
>mistaken.
Well I tried it, and the joined version had nearly twice the
code size of the split version.
$ wc -l split.s joined.s
5719 split.s
7666 joined.s
$ readelf -l joined >joined.readelf
$ readelf -l split >split.readelf
$ diff split.readelf joined.readelf
11,13c11,13
< LOAD 0x000000 0x08048000 0x08048000 0x02b54 0x02b54 R E 0x1000
---
> LOAD 0x000000 0x08048000 0x08048000 0x04954 0x04954 R E 0x1000
^^^^^^^
The actual code is on-line at
http://www.teaser.fr/~amajorel/tmptbloat/
--
André Majorel <amaj...@teezer.fr> (it's really "teaser")
http://www.teaser.fr/~amajorel/
A properly functioning grocery clerk is a linear system -- Erik Spjut
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
James Kanze
> >Seriously, templates will seem to cause code bloat because it
> >allows you to get a large of executable from a little source. If
> >you write all N overloads of a function yourself, you'll get the
> >same size executable. But because of the work you've done you'll
> >probably accept it. If the compiler writes these N overloads for
> >you ( using your template ), the resulting executable will be
> >almost the same size. (Not counting debug information).
> The code is bloated compared to what it would be if using iterators
> only involved, say, calling virtual functions.
True. All of the standard functions are really small, probably for
this reason. Still, a small function which calls a small function
which calls a small function..., all of which are templates, will lead
to code bload as well.
Structurally, the STL almost always chooses execution speed over
space. For the small, low level functions which are part of the
standard, and with most modern implementations, this is a reasonable
choice. For application level functions, however, templates just
don't work well. Not only is code bloat a problem. There is also the
added dependancies because the template source must be included. And
there are the added difficulties of debugging.
> It's unfortunate because this contradicts somewhat one of the goals
> of the STL that is, I understand, to let programmers freely pick the
> best container for the job. If your function is big enough you will
> think twice before using it again with a different container.
In this regart, it's worth reading Item 2 of Scott Meyer's "Effective
STL". (This particular item is available on the web, see
http://cseng.aw.com/book/0,3828,0201749629,00.html. But don't use
this as an excuse not to buy the book; I've not got my copy yet, but
from the extracts on the web and Scott's previous books, I have the
feeling that this book will be just as important as his first book.)
I'll go Scott one further, even. On two points:
- The rule is general, and applies to *any* standard library
component, in any language. Never use a standard library
component, or any non-specific component, to represent an
application specific concept. Your TextBuffer may just be an
std::string, and your ObjectInstantiator a pre-initialized
std::map, but if you just use a typedef, client code will use all
of the interface, and lock you in. Later, when you want to
optimize for the specific use in the application, you're stuck.
By their very nature, general components have wide interfaces;
application components should have narrow ones.
- Scott sort of hints at it, but I'll make it explicit. Don't let
iterators escape either. If your application level component is a
container, and external iteration makes sense, provide an iterator
class, and expose only that to the client. Make only the
necessary guarantees concerning validity, etc.
> Disclaimer: I'm *not* implying that implementing the STL using
> polymorphism instead of templates is possible or even desirable.
It's not difficult to create a polymorphic STL iterator, if that is
what is needed. See http://www.gabi-soft.de/codebase-en.html,
component Collections/iterator. Note, however, that it *doesn't*
address the problem that iterators into different containers have
different semantics, especially with regards to what you can do
without invalidating them. (It's nice for read-only functions,
however.)
> You have probably all learned to live with this nasty aspect of the
> STL, but I'm new to this. I was under the impression that there was
> something magical about the STL and I've just been told Santa
> doesn't exist.
> The lesson for me is that, if you have a function that goes :
>
> template<typename Iterator>
> myfunc (Iterator begin, Iterator end)
> {
> for (Iterator i = begin; i != end; i++)
> {
> // 200 lines of code
> }
> }
> you'd better write it :
>
> template<typename Iterator>
> myfunc (Iterator begin, Iterator end)
> {
> for (Iterator i = begin; i != end; i++)
> foo (*i);
> }
> void foo (mytype)
> {
> // 200 lines of code
> }
That's probably true even without STL. Who wants 200 lines in a
single function.
With STL, of course, you'd write:
std::for_each( container.begin() , container.end() , foo ) ;
and be done with it.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
James Kanze
> ston...@phatbasset.com (stonerCT) wrote (abridged):
> > > template<typename Iterator>
> > > myfunc (Iterator begin, Iterator end)
> > > {
> > > for (Iterator i = begin; i != end; i++)
> > > foo (*i);
> > > }
> > > void foo (mytype)
> > > {
> > > // 200 lines of code
> > > }
> > I will assume you are worried here about large inlined template
> > functions (though the myfunc<>() function above does not actually
> > appear to be inlined, unless it is really inside a class {} block)
> > causing code bloat.
> He's worried about instantiating myfunc with a dozen different
> iterator types, where they all have the same value_type (namely
> mytype). The idea is that objects of type mytype are being stored in
> a variety of containers.
I'm just curious. Is this a problem in real life? While it's true
that you will often have objects stored in different containers, does
it actually occur that you have significant operations which take
place over different containers in the same program?
> He expects the above form to replicate the 2 lines of myfunc 12
> times, and the 200 lines of foo only once. Whereas the other form,
> with foo manually inlined, replicates the 200 lines of foo 12 times
> as well. Thus the above form is less bloated by a factor of about
> 100. This is about inlining foo into myfunc, not inlining myfunc
> into its callers.
> I think he's right; his understanding is pretty good.
> If iterators had dynamic polymorphism, he could write it as:
> template <typename T>
> class Pit { // Polymorphic iterator.
> // ...
> };
> void myfunc( Pit<mytype> begin, Pit<mytype> end ) {
> for (Pit<mytype> i = begin; i != end; ++i) {
> // 200 lines of code using *i.
> }
> }
> This uses dynamic polymorphism instead of compile-time polymorphism.
> Myfunc is not a template, so there will (probably) be less bloat.
In my experience, the bloat is rarely a problem. What occasionally
does occur is that you encounter different container/iterator types
when iterating over a structure; in such cases, you *need* dynamic
polymorphism, since the type varies, and cannot be known at compile
time. From experience, such cases aren't particularly frequent
either, but when they occur, there aren't in general any good
alternatives. (Unlike his example, where you would probably want to
decompose anyway, regardless of templates or code bloat.)
> Against that we have the overhead of the indirection and virtual
> function calls, plus the difficulty of designing and implementing
> Pit<T>. I imagine we need a letter-and-envelope idiom, which in turn
> means heap allocation, and possible exceptions due to
> heap-exhaustion when copying iterators. Also we need a virtual
> operator!=(), which is often a problem area. It's all doable, but
> it's not trivial or especially efficient. (See the earlier "virtual
> iterators" thread for more details.)
It's quite doable, and not even very difficult. For an example, see
http://www.gabi-soft.de/codebase-en.html, component
Collections/iterator. (FWIW: I wrote the entire component, as posted,
included tests, in less than two hours.) It's not especially
efficient, but it is probably efficient enough for most cases; the
dynamic allocation only occurs when copying, and a custom allocation
function could probably reduce the overhead to bearable limits there
as well.
> Another approach would be to use a single sequence object instead of
> a pair of iterators, and pass by reference to avoid copying and
> slicing problems (which tend to destroy polymorphism).
I'm of two minds about this. I think I was one of the first to
suggest that a single iterator idiom might be preferrable to the
current two iterator idiom. I still think it overall better. But I'm
not convinced that the difference is sufficient to justify two
standard idioms. There's enough in the C++ standard already to learn.
The question of one iterator or two is fully orthogonal to the
question of static or run-time polymorphism. Again, see my
implementation of polymorphic STL iterators, cited above.
> Eg:
> // Abstract polymorphic base class for sequences.
> template <typename T>
> class Seq {
> public:
> virtual bool empty() const = 0;
> virtual T &operator*() = 0;
> virtual void operator++() = 0;
> };
I don't like this approach at all. Virtual functions should never be
public. And I don't like virtual overloaded operators. Both operator
overloading and virtual functions add complexity; one thing at a time,
please.
I'm also not quite sure what the abstraction here is supposed to be.
Collections or containers or complete sequences can be empty, but
can't logically be incremented or dereferenced. Iterators, cursors,
or sequence pointers can be incremented and dereferenced, but have no
concept of "empty".
Historically, my pre-STL iterators had four functions:
template< typename valueT >
struct Iterator
{
virtual bool isDone() const = 0 ;
virtual bool isValid() const = 0 ;
virtual valueT& current() const = 0 ;
virtual void next() = 0 ;
} ;
(This is just an exposition. In fact, my pre-STL iterators weren't
dynamically polymorphic either.)
The distinction between isDone() and isValid() is due to the fact that
my iterators were "safe". If you deleted an element under the
iterator, the iterator continued pointing to a virtual element until
advanced. During this time, isValid() was false, and a call to
current() caused an assertion failure.
For an excellent implementation of dynamically polymorphic iterators,
along the lines of what you seem to want, see
http://ose.sourceforge.net/.
I get the impression that you are somehow combining two distinct
issues. There's no problem defining an abstract base which implements
the STL iterator interface, and passing references to it. And there
would be no problem defining single iterators (sequences, if you
prefer) to use value semantics. (My pre-STL iterators did.)
> Sequence objects are not part of the current C++ standard. I am
> lobbying for them to be included in future standards. Meanwhile,
> IteratorSeq<iterator> shows how this approach can be layered on top
> of the current std iterators. If Andre Majorel really needs
> dynamically polymorphism, he might find this approach easier than
> the "virtual iterators" approach discussed in the earlier thread.
I'm not certain which thread you are referring to, but if all he wants
is dynamic polymorphism, my Collections/iterator above would fit the
bill. From his description, however, I'm not sure if he doesn't have
a design problem, however, or is simply misusing STL. One of the
characteristics of STL is to separate the iteration from the actual
behavior, by means of functions like std::for_each, std::accumulate,
std::transform, std::replace and std::replace_if. Extensive use of
these algorithms means that the user code rarely has to manipulate
iterators directly.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
Andre Majorel
>In this regart, it's worth reading Item 2 of Scott Meyer's "Effective
>STL". (This particular item is available on the web, see
>http://cseng.aw.com/book/0,3828,0201749629,00.html. But don't use
>this as an excuse not to buy the book; I've not got my copy yet, but
>from the extracts on the web and Scott's previous books, I have the
>feeling that this book will be just as important as his first book.)
Yes, I wish Effective STL had been available earlier.
(Incidentally, I also wish it was available in electronic form.
You can only carry so many books with you.)
> - Scott sort of hints at it, but I'll make it explicit. Don't let
> iterators escape either. If your application level component is a
> container, and external iteration makes sense, provide an iterator
> class, and expose only that to the client. Make only the
> necessary guarantees concerning validity, etc.
Any pointers handy on "writing STL-compatible iterators for
dummies ?"
>Who wants 200 lines in a single function.
Not all algorithms nicely break into small functions.
>With STL, of course, you'd write:
>
> std::for_each( container.begin() , container.end() , foo ) ;
>
>and be done with it.
I had looked into for_each() but my (mis)understanding was that
it passed the iterator itself, not the data, and therefore
required the callback to be a template.
Looks like for_each() is just what the doctor ordered. :-)
Many thanks to all for your help.
--
André Majorel <amaj...@teezer.fr> (it's really "teaser")
http://www.teaser.fr/~amajorel/
A properly functioning grocery clerk is a linear system -- Erik Spjut
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dave Harris
> I'm just curious. Is this a problem in real life?
Not for me. The nearest I've come is having to forward-declare some
iterators, which replaced a dependency on a container with a dependency on
the fact that the container wrapped a std::vector. This was less than
ideal, but I wouldn't have wanted the overhead of extra indirection.
I commented because I felt I understood what Andre Majorel was saying. The
lack of dynamic polymorphism in C++ iterators is surprising if we are used
to, eg, how Java approaches things. It's interesting to think about what a
Java-like approach might look like in C++.
> I'm of two minds about this. I think I was one of the first to
> suggest that a single iterator idiom might be preferrable to the
> current two iterator idiom. I still think it overall better. But I'm
> not convinced that the difference is sufficient to justify two
> standard idioms. There's enough in the C++ standard already to learn.
Yes, I think you were one of the first too, especially in the newsgroups.
I might not have dared such sacrilege :-)
I'm not convinced it is better overall. Raw iterators are good if what we
want is actually a pointer (eg the result of std::find()) or for random
access.
Still, the single-object's utility for things like returning sequences, or
for getting a sequence which refers to an entire container, seems good to
me, worth looking into.
> The question of one iterator or two is fully orthogonal to the
> question of static or run-time polymorphism.
It's more orthogonal than I thought when I wrote that message, but like
all things, spreading the state over two objects does make it a bit
harder. It mainly shows up in the test for an empty sequence. With one
object, there is just the basic overhead of a virtual function call for
empty(). With two objects, we need something like:
bool Subclass::operator==( const Baseclass &rhs ) const {
const Subclass &sub = dynamic_cast<const Subclass &>(rhs);
return sub.it == it;
}
in other words, a second type-test for the second object. Now we have to
worry about what happens if the cast fails.
> Virtual functions should never be public. And I don't like
> virtual overloaded operators.
Whatever. In a serious proposal I probably wouldn't use member functions
at all. I'd prefer isEmpty() to empty() for representing an empty
sequence, but generally wanted to be consistent with the STD. I think
conciseness matters in heavily-used idioms, and a name like "current" is a
little more verbose than I'd like. I suppose we could use front() instead
of operator*(), and pop_front() instead of operator++().
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Ross Smith
>
> In article <3B36D9A7...@dresdner-bank.com>, James Kanze wrote:
>
> > - Scott sort of hints at it, but I'll make it explicit. Don't let
> > iterators escape either. If your application level component is a
> > container, and external iteration makes sense, provide an iterator
> > class, and expose only that to the client. Make only the
> > necessary guarantees concerning validity, etc.
>
> Any pointers handy on "writing STL-compatible iterators for
> dummies ?"
I'll give it a try...
The usual situation requiring user-defined iterators is that you have
a type that bears some resemblance to an STL container, and you want
to provide iterators so it can be used with STL algorithms. You need
to ask three questions:
First, is this simply a wrapper for an underlying collection of
objects that's held somewhere as a real STL container, or is it a
"virtual container" for which iteration is (under the hood) more
complicated than simply incrementing some underlying iterator (or
pointer or index or whatever)? In the former case you can frequently
get away with making your container's iterators simply typedefs for
those of the underlying container; your begin() function would call
member_container.begin(), and so on.
Second, do you only need read-only iterators, or do you need separate
read-only (const) and read-write (non-const) iterators?
Third, which kind of iterator (input, output, forward, bidirectional,
or random access) is appropriate? If you're familiar with the
properties of the iterator types (if not, visit
http://www.sgi.com/tech/stl/), the appropriate choice should be
obvious from the semantics of the container.
I'll start with forward iterators, as the simplest case that's likely
to come up in normal code. Input and output iterators have some odd
properties and rarely need to be implemented in user code; I'll leave
them out of discussion. Bidirectional and random access iterators are
covered below.
The exact behaviour of a forward iterator is spelled out in the
Standard in terms of a set of expressions with specified behaviour,
rather than a set of member functions, which leaves some leeway in how
you actually implement it. Typically it looks something like this
(I'll start with the const-iterator-only situation):
#include <iterator>
class container {
public:
typedef something_or_other value_type;
class const_iterator:
public std::iterator<std::forward_iterator_tag, value_type> {
friend class container;
public:
const value_type& operator*() const;
const value_type* operator->() const;
const_iterator& operator++();
const_iterator operator++(int);
friend bool operator==(const_iterator lhs,
const_iterator rhs);
friend bool operator!=(const_iterator lhs,
const_iterator rhs);
private:
//...
};
//...
};
An iterator should always be derived from an instantiation of the
std::iterator template. The iterator's life cycle functions
(constructors, destructor, and assignment operator) aren't declared
here; in most cases the compiler-generated ones are sufficient. The
container needs to be a friend of the iterator so that the container's
begin() and end() functions can fill in the iterator's private members
with the appropriate values.
There are normally only three member functions that need nontrivial
implementations; the rest are just boilerplate.
const container::value_type&
container::const_iterator::operator*() const {
// find the element and return a reference to it
}
const container::value_type*
container::const_iterator::operator->() const {
return &**this;
}
If there's an underlying real container, operator*() can just return a
reference to the appropriate element. If there's no actual container
and the elements need to be generated on the fly -- what I think of as
a "virtual container" -- things get a bit more complicated; you'll
probably need to give the iterator a value_type member object, and
fill it in when you need to. This might be done as part of the
increment operator (below), or if the operation is nontrivial, you
might choose the "lazy" approach and only generate the actual value
when one of the dereferencing operators is called.
The operator->() function is just boilerplate around a call to
operator*().
container::const_iterator&
container::const_iterator::operator++() {
// the incrementing logic goes here
return *this;
}
container::const_iterator
container::const_iterator::operator++(int) {
const_iterator old(*this);
++*this;
return old;
}
Again, the incrementing logic will usually be trivial if there's a
real container involved, more complicated if you're working with a
virtual container. In particular, watch out for what happens when you
increment past the last valid item -- this needs to produce an
iterator that will compare equal to container.end(), and making this
work is often nontrivial for virtual containers.
The post-increment function is just boilerplate again (and
incidentally makes it obvious why all the experts recommend using
pre-increment wherever possible).
bool operator==(container::const_iterator lhs,
container::const_iterator rhs) {
// equality comparison goes here
}
bool operator!=(container::const_iterator lhs,
container::const_iterator rhs) {
return !(lhs == rhs);
}
For a real container, the equality comparison will usually just
compare the underlying iterators (or pointers or indices or whatever).
The semantics of comparisons for virtual container iterators are often
tricky. Remember that iterator comparison only needs to be defined for
iterators into the same container, so you can often simplify things by
taking for granted that lhs and rhs both point into the same container
object. Again, the second function is just boilerplate.
It's a matter of taste whether iterator arguments are passed by value
or reference; I've shown tham passed by value to reduce clutter, but
if the iterator contains several data members, passing by reference
may be better.
That convers the const-iterator-only situation. When we need separate
const and mutable iterators, one small complication is added beyond
the simple addition of a second class.
class container {
public:
typedef something_or_other value_type;
class const_iterator;
class iterator:
public std::iterator<std::forward_iterator_tag, value_type> {
friend class container;
friend class container::const_iterator;
public:
value_type& operator*() const;
value_type* operator->() const;
iterator& operator++();
iterator operator++(int);
friend bool operator==(iterator lhs, iterator rhs);
friend bool operator!=(iterator lhs, iterator rhs);
private:
//...
};
class const_iterator:
public std::iterator<std::forward_iterator_tag, value_type> {
friend class container;
public:
const_iterator();
const_iterator(const iterator& i);
const value_type& operator*() const;
const value_type* operator->() const;
const_iterator& operator++();
const_iterator operator++(int);
friend bool operator==(const_iterator lhs,
const_iterator rhs);
friend bool operator!=(const_iterator lhs,
const_iterator rhs);
private:
//...
};
//...
};
There needs to be a conversion from iterator to const_iterator (so
that mixed-type operations, such as comparison between an iterator and
a const_iterator, will work). This is done here by giving
const_iterator a conversion constructor from iterator (equivalently,
we could have given iterator an operator const_iterator()), which
requires const_iterator to be a friend of iterator, so it can copy its
data members. (It also requires the addition of an explicit default
constructor to const_iterator, since the existence of another
user-defined constructor inhibits the compiler-defined one.)
Bidirectional iterators add just two member functions to forward
iterators:
class iterator:
public std::iterator<std::bidirectional_iterator_tag, value_type> {
public:
//...
iterator& operator--();
iterator operator--(int);
//...
};
I won't detail the implementations, they're obvious variations on
operator++().
Random access iterators add several more member and friend functions:
class iterator:
public std::iterator<std::random_access_iterator_tag, value_type> {
public:
//...
iterator& operator+=(difference_type rhs);
iterator& operator-=(difference_type rhs);
friend iterator operator+(iterator lhs, difference_type rhs);
friend iterator operator+(difference_type lhs, iterator rhs);
friend iterator operator-(iterator lhs, difference_type rhs);
friend difference_type operator-(iterator lhs, iterator rhs);
friend bool operator<(iterator lhs, iterator rhs);
friend bool operator>(iterator lhs, iterator rhs);
friend bool operator<=(iterator lhs, iterator rhs);
friend bool operator>=(iterator lhs, iterator rhs);
//...
};
container::iterator&
container::iterator::operator+=(container::difference_type rhs) {
// add rhs to iterator position
return *this;
}
container::iterator&
container::iterator::operator-=(container::difference_type rhs) {
// subtract rhs from iterator position
return *this;
}
container::iterator operator+(container::iterator lhs,
container::difference_type rhs) {
return iterator(lhs) += rhs;
}
container::iterator operator+(container::difference_type lhs,
container::iterator rhs) {
return iterator(rhs) += lhs;
}
container::iterator operator-(container::iterator lhs,
container::difference_type rhs) {
return iterator(lhs) -= rhs;
}
container::difference_type operator-(container::iterator lhs,
container::iterator rhs) {
// calculate distance between iterators
}
bool operator<(container::iterator lhs, container::iterator rhs) {
// perform less-than comparison
}
bool operator>(container::iterator lhs, container::iterator rhs) {
return rhs < lhs;
}
bool operator<=(container::iterator lhs, container::iterator rhs) {
return !(rhs < lhs);
}
bool operator>=(container::iterator lhs, container::iterator rhs) {
return !(lhs < rhs);
}
Four of the functions (operator+=(), operator-=(), the second
operator-(), and operator<()) are nontrivial; the rest are
boilerplate.
One feature of the above code that some experts may disapprove of is
the declaration of all the free functions as friends, when in fact
only a few of them need direct access to the iterator's private data.
I originally got into the habit of doing this simply to keep the
declarations together; declaring some functions inside the class and
some outside seemed awkward. Since then, though, I've been told that
there's a subtle difference in the way name lookup works for functions
declared inside a class (as friends) and outside, so keeping them
together in the class is probably a good idea for practical as well as
aesthetic reasons.
I hope all this is some help to anyone who needs to write their own
STL-like containers and iterators.
--
Ross Smith <ros...@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"Unix has always lurked provocatively in the background of the operating
system wars, like the Russian Army." -- Neal Stephenson
James Kanze
[We're talking about polymorphic iterators here, I think...]
> James...@dresdner-bank.com (James Kanze) wrote (abridged):
> > I'm just curious. Is this a problem in real life?
> Not for me. The nearest I've come is having to forward-declare some
> iterators, which replaced a dependency on a container with a
> dependency on the fact that the container wrapped a std::vector.
> This was less than ideal, but I wouldn't have wanted the overhead of
> extra indirection.
> I commented because I felt I understood what Andre Majorel was
> saying. The lack of dynamic polymorphism in C++ iterators is
> surprising if we are used to, eg, how Java approaches things. It's
> interesting to think about what a Java-like approach might look like
> in C++.
It's not too surprising; Java and C++ are different languages, with
different philosophies. But how often is the polymorphism actually
used in Java. Or rather, how often does this polymorphism actually
result in an advantage. We used the polymorphism of Collection rather
regularly. But mainly because it was there; in most cases, there
would have been no problem saying that we wanted a HashSet, rather
than a Collection. The only case I can think of where it
realistically offered something is when I used containers to define a
sort of tree like structure; the elements of the collection were
either Action, or a similar collection.
In C++, I think I'd create a discriminated union handle class to
handle the case: the discriminated union would contain either an
Action or a container of discriminated union handles. While the Java
implementation didn't allowed the user complete freedom with regards
to the type of the container, in practice, imposing a vector or a
deque wouldn't have caused any particular problem. And the C++
solution would offer complete static type checking; because the code
creating some of the sublists was quite remote from the code using
them, it was easy to slip in an element of the wrong type (and it
happened once or twice).
The result is that the C++ design (with only limited polymorphism,
implemented through a handle) is significantly more robust (although
also a little more work) than the Java design.
I'm not saying that there aren't cases where the polymophism wouldn't
be useful. Only that I've yet to encounter one.
> > I'm of two minds about this. I think I was one of the first to
> > suggest that a single iterator idiom might be preferrable to the
> > current two iterator idiom. I still think it overall better. But
> > I'm not convinced that the difference is sufficient to justify two
> > standard idioms. There's enough in the C++ standard already to
> > learn.
> Yes, I think you were one of the first too, especially in the
> newsgroups. I might not have dared such sacrilege :-)
> I'm not convinced it is better overall. Raw iterators are good if
> what we want is actually a pointer (eg the result of std::find()) or
> for random access.
For random access, I prefer view objects (like the Java idiom). You
have a point though concerning iterators that just designate single
objects; most of the time you could just return a pointer and be done
with it, but then you've excluded the occasional case where the client
wants to look at the next (or the surrounding) objects. I suspect
that most such cases will use containers with random access iterators,
however, which can generally be modeled using indexes (like the
std::string::find functions).
In practice, I've found myself frequently constrainted by the double
iterator idiom, and having to write a lot of extra code in order to
use it. Whereas in the past (and in Java), I've consistently used
single iterators, and have never felt a problem with them. But of
course, my experience isn't universal.
Globally, of course, both work. And I don't think that the difference
is great enough to justify supporting two idioms in the standard.
(FWIW: I have a polymorphic version of an STL iterator available on my
web site, and I posted an example of chained iterators -- an iterator
bases itself on another iterator, rather than on a container -- in
fr.comp.lang.c++ yesterday. Both were cases that I though would be
difficult because of the double iterator idiom. In both cases, the
double iterator solution was a little more complex than if I had based
the code on single iterators, but in both cases, the difference was
much less than I had initially expected.)
> Still, the single-object's utility for things like returning
> sequences, or for getting a sequence which refers to an entire
> container, seems good to me, worth looking into.
> > The question of one iterator or two is fully orthogonal to the
> > question of static or run-time polymorphism.
> It's more orthogonal than I thought when I wrote that message, but
> like all things, spreading the state over two objects does make it a
> bit harder.
Slightly. Still, if you really think polymorphic iterators important,
I'd suggest lobbying for a polymorphic version (like the one I offer)
of the STL iterators, so that people don't have to handle two idioms.
Although quite frankly, I'm not convinced that everything belongs in
the standard. I have no real problem with pseudo-standards, like ACE
or booch::shared_ptr; the important thing is to convince people that
they are pseudo-standards, and to use them even if they think that
their own idea is slightly better.
> It mainly shows up in the test for an empty sequence. With one
> object, there is just the basic overhead of a virtual function call
> for empty(). With two objects, we need something like:
> bool Subclass::operator==( const Baseclass &rhs ) const {
> const Subclass &sub = dynamic_cast<const Subclass &>(rhs);
> return sub.it == it;
> }
> in other words, a second type-test for the second object. Now we
> have to worry about what happens if the cast fails.
My own implementation:
template< typename FwdIter >
bool
GB_STLIterator< FwdIter >::doIsEqual( Base const& other ) const
{
Self const* typedOther = dynamic_cast< Self const* >( &other ) ;
return typedOther == NULL
? false
: myIter == typedOther->myIter ;
}
Iterators of different types are, by definition, unequal.
This is, of course, a somewhat arbitrary design decision. I could
equally as well argue for an exception, an assertion failure, or even
undefined behavior.
My choice in this case is based on the behavior of pointers. If I
compare two pointers into two different C-style arrays, the will
normally compare unequal. (In fact, if the two arrays happen to be
physically adjacent in memory, the end pointer of one will compare
equal to the begin pointer of the other. In practice, the case is
probably extremely rare.) I'm not convinced that this is the best
alternative, but it is certainly the one closest to the STL philosophy
of modelling iterators on pointers.
In this regard, it's probably worth thinking about why we use a
standard at all. For any given application, I suspect that most of us
could design something that was better than the STL *for* *that*
*application*. The result would be, of course, that *every*
application would use a different set of containers, iterators and
algorithms. Which has two very expensive consequences:
- every one who comes on the application has to learn a new library,
and every one has to learn a new library for every new
application, and
- you have to reimplement it in every application.
Thus, unless the alternatives have very significant advantages, it is
besser to use the almost, but not quite as good standard solution.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
James Kanze
> In article <3B36D9A7...@dresdner-bank.com>, James Kanze wrote:
> > - Scott sort of hints at it, but I'll make it explicit. Don't let
> > iterators escape either. If your application level component is a
> > container, and external iteration makes sense, provide an iterator
> > class, and expose only that to the client. Make only the
> > necessary guarantees concerning validity, etc.
> Any pointers handy on "writing STL-compatible iterators for
> dummies ?"
Not that I know of. Some of Matt Austin's articles in CUJ might be of
use though.
What I'd like is to see some standard idioms develop. Things like
iterators based on other iterators, or iterators for cases where the
semantics really don't correspond to a double iterator idiom. For the
latter, we have the iostream iterators, of course. But I've not seen
much about how to implement them, and even less about the general
solution. A good excersice for both might be to write an iterator
which reads the next n int's (or whatever) from a stream.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
David Abrahams
"Ross Smith" <ros...@ihug.co.nz> wrote in message
news:3B3A8048...@ihug.co.nz...
> An iterator should always be derived from an instantiation of the
> std::iterator template.
Why (other than broken compilers and libraries)?
<snip lots of good advice>
Or, you could use the boost iterator adaptors library, which automates most
of this stuff:
http://www.boost.org/libs/utility/iterator_adaptors.htm
-Dave
Ross Smith
>
> "Ross Smith" <ros...@ihug.co.nz> wrote in message
> news:3B3A8048...@ihug.co.nz...
> > An iterator should always be derived from an instantiation of the
> > std::iterator template.
>
> Why (other than broken compilers and libraries)?
Because otherwise you have to add a bunch of (otherwise unnecessary)
typedefs to your iterator so std::iterator_traits will work.
--
Ross Smith <ros...@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"Unix has always lurked provocatively in the background of the operating
system wars, like the Russian Army." -- Neal Stephenson
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
David Abrahams
> David Abrahams wrote:
> >
> > "Ross Smith" <ros...@ihug.co.nz> wrote in message
> > news:3B3A8048...@ihug.co.nz...
> > > An iterator should always be derived from an instantiation of the
> > > std::iterator template.
> >
> > Why (other than broken compilers and libraries)?
>
> Because otherwise you have to add a bunch of (otherwise unnecessary)
> typedefs to your iterator so std::iterator_traits will work.
But those typedefs are so much more explicit, and easier to remember than
the order of the std::iterator parameters... ;-)
-Dave
Ross Smith
>
> "Ross Smith" <ros...@ihug.co.nz> wrote in message
> news:3B3D4086...@ihug.co.nz...
> > David Abrahams wrote:
> > >
> > > "Ross Smith" <ros...@ihug.co.nz> wrote in message
> > > news:3B3A8048...@ihug.co.nz...
> > > > An iterator should always be derived from an instantiation of the
> > > > std::iterator template.
> > >
> > > Why (other than broken compilers and libraries)?
> >
> > Because otherwise you have to add a bunch of (otherwise unnecessary)
> > typedefs to your iterator so std::iterator_traits will work.
>
> But those typedefs are so much more explicit, and easier to remember than
> the order of the std::iterator parameters... ;-)
Only the first two arguments are required (iterator tag and value type).
The others are only needed on the very rare occasions when the defaults
aren't appropriate, i.e. when you're using a non-standard allocator.
--
Ross Smith <ros...@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"Unix has always lurked provocatively in the background of the operating
system wars, like the Russian Army." -- Neal Stephenson
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Matthew Austern
> > > Because otherwise you have to add a bunch of (otherwise unnecessary)
> > > typedefs to your iterator so std::iterator_traits will work.
> >
> > But those typedefs are so much more explicit, and easier to remember than
> > the order of the std::iterator parameters... ;-)
>
> Only the first two arguments are required (iterator tag and value type).
> The others are only needed on the very rare occasions when the defaults
> aren't appropriate, i.e. when you're using a non-standard allocator.
I wouldn't say "very rare". You need to specify the pointer and
reference types explicitly when you want them to be const T& and
const T*, i.e. whenever you're writing a const iterator. That's
not rare at all.
I rarely use std::iterator, except when it's required for strict
standard conformance.
Ross Smith
>
> Ross Smith <ros...@ihug.co.nz> writes:
>
> > > > Because otherwise you have to add a bunch of (otherwise unnecessary)
> > > > typedefs to your iterator so std::iterator_traits will work.
> > >
> > > But those typedefs are so much more explicit, and easier to remember
than
> > > the order of the std::iterator parameters... ;-)
> >
> > Only the first two arguments are required (iterator tag and value type).
> > The others are only needed on the very rare occasions when the defaults
> > aren't appropriate, i.e. when you're using a non-standard allocator.
>
> I wouldn't say "very rare". You need to specify the pointer and
> reference types explicitly when you want them to be const T& and
> const T*, i.e. whenever you're writing a const iterator. That's
> not rare at all.
Oh, I never realised that. I'd always been under the impression that,
because the value type of a const iterator is T (not const T), it
followed that the pointer and reference types would also be plain T* and
T&. Thanks for the correction.
--
Ross Smith <ros...@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"Unix has always lurked provocatively in the background of the operating
system wars, like the Russian Army." -- Neal Stephenson
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dave Harris
> different philosophies.
Indeed. The link model is especially different.
> Or rather, how often does this polymorphism actually result in
> an advantage.
Not often if we're dealing with monolithic apps. The dynamic polymorphism
helps with binary compatibility, though. I imagine that is significant for
long-lived server type apps, which load binary servlets dynamically.
> if you really think polymorphic iterators important,
I don't.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]