 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Eugene Gershnik
Guest
|
 Posted: Fri Sep 19, 2003 11:25 am Post subject: Type assignable to dereferenced output iterator |
 |
|
Consider the following
template<typename T>
T foo() {...}
template<typename OutIt>
void bar(OutIt out)
{
X val = foo<X>();
*out = val;
}
where OutIt can be any output iterator.
My question is how to determine the type X?
iterator_traits<>::value_type won't always work since all "real" output
iterators (back_insert_iterator, ostream_iterator etc.) in standard library
are required to define it as void. As one knowledgeable person told me
| Quote: | C++ standard 24.3.1/1:
In the case of an output iterator, the types
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
are both defined as void.
|
The funny thing is that both (back_)insert_iterator and
ostream(buf)_iterator know the type that can be assigned perfectly well.
There just isn't any standard way to refer to them.
In my code I ended up providing a class similar to iterator_traits that is
partially specialized for all standard output iterator types. Any better
solution would be much appreciated.
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
johnchx
Guest
|
| Posted: Sat Sep 20, 2003 10:07 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
"Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote
| Quote: |
template<typename T
T foo() {...}
template
void bar(OutIt out)
{
X val = foo
*out = val;
}
where OutIt can be any output iterator.
My question is how to determine the type X?
|
The trouble is that for any output iterator, there is no guarantee
that there *is* a unique type X (assuming X means "the type assignable
to *out"). Of course, for those included in the standard library,
like ostream_iterator and back_insert_iterator, there is...but it's
not a requirement on output iterators in general.
Actually, it's possible to read the standard to imply that there just
might be such a requirement, but there's a DR in the pipleline to
clarify the situation:
http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#324
So, since being able to infer a unique assignable type from an output
iterator type is basically a "special case," a roll-your-own
type-trait is probably the best solution at hand.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Siemel Naran
Guest
|
| Posted: Sun Sep 21, 2003 10:14 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
"Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote in message
| Quote: | template<typename OutIt
void bar(OutIt out)
{
X val = foo
*out = val;
}
|
Good question. I was thinking about this the other day. Here's a guess
towards a solution, though it's not a great one.
template <class Iter>
struct smart_iterator_traits {
typedef typename std::iterator_traits<Iter>::iterator_category
iterator_category;
typedef typename std::iterator_traits<Iter>::value_type value_type;
difference_type;
pointer;
reference;
};
// partial specialization
template <class Iter where Iter has a typedef container_type> {
typedef typename std::iterator_traits<Iter>::iterator_category
iterator_category;
typedef typename Iter::container_type::value_type value_type;
difference_type;
pointer;
reference;
};
--
+++++++++++
Siemel Naran
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Mon Sep 22, 2003 3:18 pm Post subject: Re: Type assignable to dereferenced output iterator |
|
|
Siemel Naran <SiemelNaran (AT) REMOVE (DOT) att.net> wrote:
| Quote: | "Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote in message
template<typename OutIt
void bar(OutIt out)
{
X val = foo
*out = val;
}
Good question. I was thinking about this the other day. Here's a guess
towards a solution, though it's not a great one.
template <class Iter
struct smart_iterator_traits {
typedef typename std::iterator_traits
iterator_category;
typedef typename std::iterator_traits<Iter>::value_type value_type;
difference_type;
pointer;
reference;
};
// partial specialization
template <class Iter where Iter has a typedef container_type> {
typedef typename std::iterator_traits<Iter>::iterator_category
iterator_category;
typedef typename Iter::container_type::value_type value_type;
difference_type;
pointer;
reference;
};
A general solution is not available since the following is a valid |
output iterator:
template <class charT=char,class Tr=std::char_traits
class gen_ostream_iterator
:public std::iterator<std::output_iterator_tag,void,void,void,void>
{
public:
typedef std::basic_ostream<charT,Tr> stream_type;
typedef gen_ostream_iterator<charT,Tr> self;
gen_ostream_iterator():stream(0),delim(0){}
explicit gen_ostream_iterator(stream_type &os,charT *d=0)
:stream(&os),delim(d){}
self & operator ++() {return *this;}
self & operator ++(int) {return *this;}
self & operator *() {return *this;}
template <class T>
self & operator = (T const &x)
{
*stream << x;
if(delim) *stream << delim;
return *this;
}
private:
stream_type *stream;
charT *delim;
};
any type T, that can be inserted [operator << ()] into a stream is a
vaild assignable type.:)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Wed Sep 24, 2003 11:36 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
[email]cbarron3 (AT) ix (DOT) netcom.com[/email] (Carl Barron) wrote in message news:<1g1n3u8.mxvu0ie64zqoN%cbarron3 (AT) ix (DOT) netcom.com>...
| Quote: | A general solution is not available since the following is a valid
output iterator:
template <class charT=char,class Tr=std::char_traits
class gen_ostream_iterator
:public std::iterator
{
public:
typedef std::basic_ostream
typedef gen_ostream_iterator<charT,Tr> self;
gen_ostream_iterator():stream(0),delim(0){}
explicit gen_ostream_iterator(stream_type &os,charT *d=0)
:stream(&os),delim(d){}
self & operator ++() {return *this;}
self & operator ++(int) {return *this;}
self & operator *() {return *this;}
template
self & operator = (T const &x)
{
*stream << x;
if(delim) *stream << delim;
return *this;
}
private:
stream_type *stream;
charT *delim;
};
any type T, that can be inserted [operator << ()] into a stream is a
vaild assignable type.:)
|
Well the "assign any type" functionality of this iterator isn't really
usable in generic code isn't it? A generic algorithm should expect any
kind of output iterator such as raw pointer or std::string::iterator.
All of them do not support the above semantics. This basically means
that in any kind of generic algorithm one must assume that the output
iterator accepts only a single type.
Maybe I have wrong expectations but for me iterators are a tool to
write generic algorithms. If I need to insert any type into a stream I
just use the stream object itself 
My problem is that by allowing this kind of freedom for output
iterators only, the standard effectively makes their use in generic
algorithms unnecessary hard without any real benefit.
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
johnchx
Guest
|
| Posted: Wed Sep 24, 2003 10:49 pm Post subject: Re: Type assignable to dereferenced output iterator |
|
|
[email]gershnik (AT) hotmail (DOT) com[/email] (Eugene Gershnik) wrote
| Quote: | A generic algorithm should expect any
kind of output iterator such as raw pointer or std::string::iterator.
All of them do not support the above semantics. This basically means
that in any kind of generic algorithm one must assume that the output
iterator accepts only a single type.
|
No, it's trickier than that.
The standard provides no method for a generic algorithm to discover
what type or types are writeable through an output iterator.
Therefore, generic algorithms are written in complete ignorance of
what types an output iterator might accept.
Instead, the algorithm places an implied compile-time constraint on
the iterator types it can work with. The following, for instance,
won't compile:
#include <vector>
#include <algorithm>
class foo {};
int main() {
std::vector<int> vi;
std::vector<foo> vf;
std::copy( vi.begin(), vi.end(), std::back_inserter(vf) );
}
Put another way, algorithms which accept an output iterator as a
template parameter are never completely generic with respect to the
type of the output iterator (unless they don't write to it, which
would be kind of pointless). There are always perfectly conforming
output iterators that just won't work, because they don't meet the
implicit requirements of the algorithm.
(Of course, documenting those implicit requirements is always a good
practice.)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Thu Sep 25, 2003 1:35 pm Post subject: Re: Type assignable to dereferenced output iterator |
|
|
johnchx wrote:
| Quote: | gershnik (AT) hotmail (DOT) com (Eugene Gershnik) wrote
A generic algorithm should expect any
kind of output iterator such as raw pointer or
std::string::iterator. All of them do not support the above
semantics. This basically means that in any kind of generic
algorithm one must assume that the output iterator accepts only a
single type.
#include <vector
#include
class foo {};
int main() {
std::vector
std::vector<foo> vf;
std::copy( vi.begin(), vi.end(), std::back_inserter(vf) );
}
Put another way, algorithms which accept an output iterator as a
template parameter are never completely generic with respect to the
type of the output iterator (unless they don't write to it, which
would be kind of pointless). There are always perfectly conforming
output iterators that just won't work, because they don't meet the
implicit requirements of the algorithm.
|
I think this is a different issue. std::copy restricts the output iterator's
_single_ type as much as it restricts what the second parameter could be.
Any non-trivial algorithm will restrict the iterators passed to it in some
way.
However, making an algorithm that expects an output iterator to support
multiple types will automatically make it unusable with all the iterators in
existence now. Of course this conclusion comes from my personal experience
and I am perfectly ready to admit that I haven't seen all possible
algorithms and iterators out there
So here is the question: does anyone have any example of real-life algorithm
that:
a. requires multi-type output iterators, and
b. couldn't be rewritten (without loss of speed or clarity) using a
single-typed version
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
johnchx
Guest
|
| Posted: Fri Sep 26, 2003 10:33 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
"Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote
| Quote: | I think this is a different issue. std::copy restricts the output iterator's
_single_ type as much as it restricts what the second parameter could be.
Any non-trivial algorithm will restrict the iterators passed to it in some
way.
|
Looks like the same issue to me ;-)
Namely: there's no such thing as a (non-trivial) algorithm that works
correctly with *any* conforming output iterator.
| Quote: | However, making an algorithm that expects an output iterator to support
multiple types will automatically make it unusable with all the iterators in
existence now.
|
Not at all! But it might not be useable with the output iterators in
the standard library. (Or it might, if the multiple types happen to
be implicitly convertible to a single type.)
The thing about the standard library's output iterators is that they
all happen to model insertion into a homogenous container. It's easy
to see why this would be the case for, say, back_insert_iterator: it
IS inserting into a homogenous container. It's less easy to see why
something like ostream_iterator is designed like this. (My own
speculation: it looks like a false parallel with istream_iterator.
But I may be completely wrong about that.)
But the abstract concept of an output iterator is not limited to the
semantics of insert-into-homogenous-container. It allows us to
express a much more general notion, along the lines of "My function is
going to output zero or more values of some type or types (which
should be documented). Do with them whatever you want: store them in
any fashion you please, throw them away, pass them one at a time to
some other arbitrary function, add them up and throw an exception when
the total exceeds some value...whatever."
Of course, output iterators have to meet the particular requirements
of the algorithms you use them with...but that's always true. Put
another way, output iterators adapt to the requirements of algorithms,
not the other way around.
| Quote: | Of course this conclusion comes from my personal experience
and I am perfectly ready to admit that I haven't seen all possible
algorithms and iterators out there
So here is the question: does anyone have any example of real-life algorithm
that:
a. requires multi-type output iterators, and
b. couldn't be rewritten (without loss of speed or clarity) using a
single-typed version
|
It depends on what you mean by algorithm, I guess. The algorithms in
the standard library have an interesting property: their input is
typically in the form of homogenous sequences, and in c++, homogenous
operations on homogenous inputs typically yields output of homogenous
types. (And notice, by the way, that it's the input iterator types and
the operation that define the output type, not the output iterator
type.) So it's not surprising that their outputs can be inserted into
homogenous containers...and you'd have to be rather tricky to get some
other result.
But if by algorithm you mean "any old program logic," it's easier to
come up with examples. I'll go think some up.... ;-)
Of course, there's no reason to go overboard: if some algorithm's
output happens to be a sequence of objects of homogenous type, then by
all means write it that way. Which, I suppose, is more or less your
point. :-)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Fri Sep 26, 2003 10:51 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
On 25 Sep 2003 09:35:21 -0400, "Eugene Gershnik"
<gershnik (AT) nospam (DOT) hotmail.com> wrote:
| Quote: | So here is the question: does anyone have any example of real-life algorithm
that:
a. requires multi-type output iterators, and
b. couldn't be rewritten (without loss of speed or clarity) using a
single-typed version
|
This line goes nowhere. The counter: Does anyone have any example of a
real-life algorithm that requires knowledge of the output iterator type?
Note that your example of writing a default constructed item to it is
not an algorithm much less a "real-life" one. I have not seen any
example, but I also have not seen everything.
Have you considered a DR by contradiction?
24.1/9: ... t denotes a value of value type T.
24.1.2/1 Table 73: *a = t
24.3.1: value_type is the value type of the iterator and for an output
iterator it is void.
Conclusion: It is required that *a = void be supported for output
iterators.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Sat Sep 27, 2003 10:34 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
johnchx wrote:
| Quote: | "Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote
However, making an algorithm that expects an output iterator to
support multiple types will automatically make it unusable with
all the iterators in existence now.
Not at all! But it might not be useable with the output iterators
in
the standard library. (Or it might, if the multiple types happen to
be implicitly convertible to a single type.)
The thing about the standard library's output iterators is that they
all happen to model insertion into a homogenous container.
|
I guess our disagreement is precisely this. I see insertion into a
homogenous container as the defining property of iterators. The standard and
you obviously disagree ;-)
| Quote: | It's easy
to see why this would be the case for, say, back_insert_iterator: it
IS inserting into a homogenous container. It's less easy to see why
something like ostream_iterator is designed like this. (My own
speculation: it looks like a false parallel with istream_iterator.
But I may be completely wrong about that.)
|
Reason 1: Efficiency. A single type iterator can be made very fast. A
multi-type will have the same performance penalty as the stream.
Reason 2: Genericity. An algorithm written for a single type iterator can
work with a pointer, with a homogenous container. A multi-type
ostream_iterator wil be usable only for streams.
| Quote: |
But the abstract concept of an output iterator is not limited to the
semantics of insert-into-homogenous-container. It allows us to
express a much more general notion, along the lines of "My function
is
going to output zero or more values of some type or types (which
should be documented). Do with them whatever you want: store them
in
any fashion you please, throw them away, pass them one at a time to
some other arbitrary function, add them up and throw an exception
when
the total exceeds some value...whatever."
|
Yes it is possible. However, this algorithm wouldn't be usable with anything
except the iterators specially crafted for it. As such I wouldn't bother
with writing it as STL-like algorithm or designing iterators for it. The
promise of STL approach is to write an algorithm that could work on many
different kinds of sequences. By requiring multu-type support you eliminate
homogenous sequences which are the prevalent kind. Effectively by allowing
more genericity you make your code less generic.
| Quote: | So here is the question: does anyone have any example of
real-life algorithm that:
a. requires multi-type output iterators, and
b. couldn't be rewritten (without loss of speed or clarity)
using a single-typed version
It depends on what you mean by algorithm, I guess.
|
An algorithm in STL sense.
| Quote: | The algorithms in
the standard library have an interesting property: their input is
typically in the form of homogenous sequences, and in c++,
homogenous operations on homogenous inputs typically yields output
of homogenous types.
(And notice, by the way, that it's the input iterator types
and
the operation that define the output type, not the output iterator
type.) So it's not surprising that their outputs can be inserted
into homogenous containers...and you'd have to be rather tricky to
get some other result.
|
As input iterators are required to have value_type (and you cannot overload
on return value) it follows that input sequence to any STL algorithm will
allways be homogenous. Then by your own logic we should expect the output to
be homogenous too :-)
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Sat Sep 27, 2003 10:36 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
John Potter wrote:
| Quote: | Does anyone have any example
of a real-life algorithm that requires knowledge of the output
iterator type?
Note that your example of writing a default constructed item to it
is
not an algorithm much less a "real-life" one. I have not seen any
example, but I also have not seen everything.
|
Easy. Take any kind of table lookup encoding. It probably would look like
the following:
template<typename InIt, typename OutIt>
OutIt encode(InIt first, InIt last, OutIt out)
{
typedef typename std::iterator_traits<InIt>::value_type key_type;
typedef ??? X;
for(; first != last; ++first)
{
key_type key = derive_a_key_from(*first);
X val = lookup_table<key_type, X>::get_value_for(key);
*out = val;
}
}
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Sep 28, 2003 1:27 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
On 27 Sep 2003 06:36:14 -0400, "Eugene Gershnik"
<gershnik (AT) nospam (DOT) hotmail.com> wrote:
| Quote: | John Potter wrote:
Does anyone have any example
of a real-life algorithm that requires knowledge of the output
iterator type?
Note that your example of writing a default constructed item to it
is
not an algorithm much less a "real-life" one. I have not seen any
example, but I also have not seen everything.
Easy. Take any kind of table lookup encoding. It probably would look like
the following:
|
Probably is not an example. Write complete code and I will rewrite it
in standard STL form without any need for output type.
| Quote: | template<typename InIt, typename OutIt
OutIt encode(InIt first, InIt last, OutIt out)
{
typedef typename std::iterator_traits
typedef ??? X;
for(; first != last; ++first)
{
key_type key = derive_a_key_from(*first);
X val = lookup_table<key_type, X>::get_value_for(key);
*out = val;
}
}
|
You are fighting the STL and complaining that it does not contain
something you need in your fight. How does that global lookup_table
fit in a generic algorithm? How does a templated member function
select one of several values of the same type? The algorithm is
transform and your loop body is the function. Please give a real
compilable example.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Sun Sep 28, 2003 10:29 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
John Potter wrote:
| Quote: | On 27 Sep 2003 06:36:14 -0400, "Eugene Gershnik"
[email]gershnik (AT) nospam (DOT) hotmail.com[/email]> wrote:
Easy. Take any kind of table lookup encoding. It probably would
look like the following:
Probably is not an example. Write complete code and I will rewrite
it in standard STL form without any need for output type.
|
Here is the simplest one (I have a few more but they are much longer).
Requirements: InIt - any input iterator with value_type implicitly
convertible to a byte. Complexity - O(N). Speed - for a trivial case of InIt
and Out being pointers the speed should not be less than that of a portable
C implementation (on at least one compiler/platform). The user should be
able to control output alphabet either through global traits as given below
or in any other way. However, no additional parameters or template
parameters that pass output type to algorithm are allowed.
template<typename Char>
class base64_traits
{
public:
static Char encode(uint8_t val)
{ return encode_table[val]; }
private:
//this is explicitly instatiated for char and wchar_t
//in a separate cpp
static const Char encode_table[65];
};
template<typename InIt, typename OutIt>
OutIt encode_base64(InIt first, InIt last, OutIt out)
{
typedef base64_traits<???> traits;
while(first != last)
{
uint8_t bytes[3];
size_t len = 0;
for( ; len != 3 && first != last; ++len, ++first)
bytes[len] = *first;
uint8_t chars[4];
chars[3] = (len == 3 ? bytes[2] & 0x3F : 64);
chars[2] = (len == 3 ? bytes[2] >> 6 : 0) | (len >= 2 ? (bytes[1] << 2) &
0x3F : 64);
chars[1] = (len >= 2 ? bytes[1] >> 4 : 0) | (len >= 1 ? (bytes[0] << 4) &
0x3F : 64);
chars[0] = (len >= 1 ? bytes[0] >> 2 : 64);
for (size_t i = 0; i != 4; ++i, ++out)
*out = traits::encode(chars[i]);
}
return out;
}
In a separate cpp:
const char base64_encoding_traits<char>::encode_table[65] = {
'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f',
'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v',
'w','x','y','z','0','1','2','3','4','5','6','7','8','9','+','/',
'='
};
const wchar_t base64_encoding_traits<wchar_t>::encode_table[65] = {
L'A',L'B',L'C',L'D',L'E',L'F',L'G',L'H',L'I',L'J',L'K',L'L',L'M',L'N',L'O',L
'P',
L'Q',L'R',L'S',L'T',L'U',L'V',L'W',L'X',L'Y',L'Z',L'a',L'b',L'c',L'd',L'e',L
'f',
L'g',L'h',L'i',L'j',L'k',L'l',L'm',L'n',L'o',L'p',L'q',L'r',L's',L't',L'u',L
'v',
L'w',L'x',L'y',L'z',L'0',L'1',L'2',L'3',L'4',L'5',L'6',L'7',L'8',L'9',L'+',L
'/',
L'='
};
| Quote: |
You are fighting the STL and complaining that it does not contain
something you need in your fight. How does that global lookup_table
fit in a generic algorithm? How does a templated member function
select one of several values of the same type? The algorithm is
transform and your loop body is the function. Please give a real
compilable example.
|
Given above. Unless I am very mistaken the algorithm couldn't be written as
a transform. The algorithm is generic not so much with respect to types as
with respect to the _form_ of input and output. Thus, global 'lookup_table'
specialized for a couple of types fits perfectly.
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
johnchx
Guest
|
| Posted: Mon Sep 29, 2003 6:22 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
"Eugene Gershnik" <gershnik (AT) nospam (DOT) hotmail.com> wrote
| Quote: | johnchx wrote:
It's easy
to see why this would be the case for, say, back_insert_iterator: it
IS inserting into a homogenous container. It's less easy to see why
something like ostream_iterator is designed like this. (My own
speculation: it looks like a false parallel with istream_iterator.
But I may be completely wrong about that.)
Reason 1: Efficiency. A single type iterator can be made very fast. A
multi-type will have the same performance penalty as the stream.
|
I don't follow you. All the underlying function calls would be
resolved based on static type informtion at compile time. What
penalty do you have in mind?
| Quote: | Reason 2: Genericity. An algorithm written for a single type iterator can
work with a pointer, with a homogenous container. A multi-type
ostream_iterator wil be usable only for streams.
|
I don't follow this either. ostream_iterators *are* useable only with
streams...that what an ostream_iterator *is*.
Are you suggesting that an output iterator that accepts mulitiple
types could *only* be used with algorithms that output multiple types?
That's just not so. An iterator that accepts multiple types would
work fine with *all* the standard algorithms -- because none of them
is allowed to assume that an output iterator accepts only a single
type of output.
| Quote: | By requiring multu-type support you eliminate
homogenous sequences which are the prevalent kind. Effectively by allowing
more genericity you make your code less generic.
|
The requirements are dictated by the semantics of the algorithm -- you
can't be more generic than the algorithm itself. I'm sure you don't
mean to say that there should be some sort of rule that forbids the
expression of any algorithm that doesn't happen to yield a sequence of
homogenous type. :-)
I'm afraid that I'm in danger of losing sight of the point you're
making. Are you actually arguing that, since the STL algorithms
happen to output homogenous sequences, that the standard should be
made more restrictive so that using these algorithms with output
iterators that accept more than one type of output becomes an error?
What would the advantage be?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Mon Sep 29, 2003 6:31 am Post subject: Re: Type assignable to dereferenced output iterator |
|
|
On 28 Sep 2003 06:29:06 -0400, "Eugene Gershnik"
<gershnik (AT) nospam (DOT) hotmail.com> wrote:
| Quote: | John Potter wrote:
Probably is not an example. Write complete code and I will rewrite
it in standard STL form without any need for output type.
Here is the simplest one (I have a few more but they are much longer).
Requirements:
InIt - any input iterator with value_type implicitly
convertible to a byte.
|
Ok.
| Quote: | Complexity - O(N). Speed - for a trivial case of InIt
and Out being pointers the speed should not be less than that of a portable
C implementation (on at least one compiler/platform).
|
Ok.
| Quote: | The user should be
able to control output alphabet either through global traits as given below
or in any other way.
|
Why? I don't see any other way.
| Quote: | However, no additional parameters or template
parameters that pass output type to algorithm are allowed.
|
It is not allowed to follow the STL paradigm! Rigs the problem.
If I understand things, the problem with your code does not exist. It
makes no difference whether the output is char or wchar_t because the
characters used are in the common subset and either table will work.
| Quote: | template<typename InIt, typename OutIt
OutIt encode_base64(InIt first, InIt last, OutIt out)
|
You are doing MIME. Why can't I use this for uuencode? The algorithm
is the same with a different table. The STL paradigm would require the
table. I might even want some other invented encoding.
template
Oiter encode_base64 (Iiter first, Iiter past, Oiter result,
T const* codeTable);
Note that this is really transform with a function which uses []
rather than ().
This problem does not fit into the usual STL algorithms because the
number of accesses to the input and output iterators are not the same.
I agree with your creation of a new algorithm to handle it. Since there
are also those who prefer STL to explicit loops, we could do it that
way. The only algorithm that allows nonsense is for_each. We can use
for_each and a function object with state and a finalize function. Your
algorithm now becomes trivial. ;-)
template <class Iiter, class Oiter, class T>
Oiter encode_base64 (Iiter first, Iiter past, Oiter result,
T const* code) {
return for_each(first, past,
Encode<Oiter, T>(result, code)).finish();
}
| Quote: | You are fighting the STL and complaining that it does not contain
something you need in your fight. How does that global lookup_table
fit in a generic algorithm? How does a templated member function
select one of several values of the same type? The algorithm is
transform and your loop body is the function. Please give a real
compilable example.
Given above. Unless I am very mistaken the algorithm couldn't be written as
a transform. The algorithm is generic not so much with respect to types as
with respect to the _form_ of input and output. Thus, global 'lookup_table'
specialized for a couple of types fits perfectly.
|
Sorry, globals are never good in algorithms. Write a dumb function that
does the right thing given the right tools in total ignorance. Smart
functions are worthless. I guess that Encode<> should be provided.
Note that the dumb for_each does the right thing with it. Note that the
dumb Encode()(uint8_t) does the right thing given the right table.
template <class Oiter, class T>
struct Encode {
T const* tab;
Oiter it;
int pos;
uint8_t pre;
Encode (Oiter it, T const* tab) : it(it), tab(tab), pos(2) {
}
void operator() (uint8_t val) {
switch (pos = (pos + 1) % 3) {
case 0 :
*it = tab[val >> 2];
pre = val << 4 & 0X30;
break;
case 1 :
*it = tab[pre | val >> 4];
pre = val << 2 & 0X3C;
break;
case 2 :
*it = tab[pre | val >> 6];
*it = tab[val & 0X3F];
break;
}
}
Oiter finish () {
switch (pos) {
case 0 :
*it = tab[pre];
pre = 64;
case 1 :
*it = tab[pre];
*it = tab[64];
}
return it;
}
};
There are many views on things.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
