C++ Templates: Incomplete Type Problem

[Anthony Borla]

Greetings,

I hope everyone is enjoying the Holiday Season !

I'm attempting to implement a function template [called 'generate_while']
modelled somewhat on the STL's, 'generate' and 'generate_n' algorithms. Now,
'generate_while', requires the use of temporary storage [mind the
line-wrap]:

template <class OutputIter_, class Generator_, class Predicate_>
OutputIter_ generate_while(OutputIter_ first_,
Generator_& gen_, Predicate_ pred_)
{
typename std::iterator_traits<OutputIter_>::value_type value_(gen_());
for ( ; pred_(value_); ++first_)
{
*first_ = value_; value_ = gen_();
}
return first_;
}

and here is how I've instantiated it:

typedef ostreambuf_iterator<char> StreamIterOut;
...
generate_while(StreamIterOut(cout),
mandel,
MandelbrotGenerator:one(mandel));
...

As you can see I've attempted to use the iterator's type traits to obtain
the type on which the template function will operate. This appears to be a
legitimate approach to take [I used the example from section 7.5.1 of
Josuttis' Standard C++ Library]. The code [full code appears below at
message end] compiles using the Borland 5.51 compiler, and executes
correctly.

However, attempting to compile the same code under GCC 3.3.1 resulted in the
following errors:

mandelbrot.cpp: In function `OutputIter_ generate_while(OutputIter_,
Generator_&, Predicate_) [with OutputIter_ =
std:streambuf_iterator<char,
std::char_traits<char> >, Generator_ = MandelbrotGenerator, Predicate_ =
MandelbrotGenerator:one]':
mandelbrot.cpp:93: instantiated from here
mandelbrot.cpp:30: error: instantiation of `value_' as type `void'
mandelbrot.cpp:30: error: `value_' has incomplete type
mandelbrot.cpp:30: error: storage size of `value_' isn't known
mandelbrot.cpp:32: error: no match for call to
`(MandelbrotGenerator:one) (
<typeprefixerror>&)'
mandelbrot.cpp:64: error: candidates are: bool
MandelbrotGenerator:one:perator()(char) const
mandelbrot.cpp:34: confused by earlier errors, bailing out

A further check using the Comeau 'tryitout' compiler web-page emits the
following:

"ComeauTest.c", line 22: error: incomplete type is not allowed
typename std::iterator_traits<OutputIter_>::value_type value_(gen_());
^
detected during instantiation of "OutputIter_
generate_while(OutputIter_, Generator_ &, Predicate_)
[with OutputIter_=std:streambuf_iterator<char,
std::char_traits<char>>, Generator_=MandelbrotGenerator,
Predicate_=MandelbrotGenerator:one]"

Quite obviously the code is doing something 'non-standard', not to mention
'unacceptable', to these later, more Standard-conforming compilers. What I
would greatly appreciate [aside from a solution / fix of course !] is an
explanation of what appears to be going wrong as it's not at all clear to
me.

Cheers,

Anthony Borla

#include <cstdlib>
#include <complex>

#include <functional>
#include <algorithm>

#include <iterator>
#include <sstream>
#include <iostream>

using namespace std;

typedef complex<double> Complex;
typedef ostreambuf_iterator<char> StreamIterOut;

/* ----------------------------- */

// STL 'lookalike' algorithm [based on STL's 'generate_n']
template <class OutputIter_, class Generator_, class Predicate_>
OutputIter_ generate_while(OutputIter_ first_, Generator_& gen_, Predicate_
pred_)
{
typename std::iterator_traits<OutputIter_>::value_type value_(gen_());

for ( ; pred_(value_); ++first_)
{
*first_ = value_; value_ = gen_();
}

return first_;
}

/* ----------------------------- */

class MandelbrotGenerator
{
public:
enum { EOS = -1 };

public:
MandelbrotGenerator(int height, int width);

bool done() const { return eos_; }

char next();
void reset();
void header(ostream& out) const;

operator bool() const { return !done(); }
char operator()() { return next(); }

public:
struct Done
{
public:
Done(MandelbrotGenerator& mref) : mref_(mref) { mref_.reset(); }
bool operator()(char) const { return !mref_.done(); }

private:
MandelbrotGenerator& mref_;
};

private:
MandelbrotGenerator(const MandelbrotGenerator&);
MandelbrotGenerator& operator=(const MandelbrotGenerator&);

static int mandel(int n, const Complex& z, const Complex& c);

private:
int x_, y_, height_, width_;
bool eos_;
};

/* ----------------------------- */

int main(int argc, char* argv[])
{
ios_base::sync_with_stdio(false);

if (argc != 2) { cerr << "Usage: " << argv[0] << " height"; return
EXIT_FAILURE; }
int n; if (!(istringstream(argv[1]) >> n) || n < 1) n = 100;

MandelbrotGenerator mandel(n, n);

mandel.header(cout);
generate_while(StreamIterOut(cout), mandel,
MandelbrotGenerator:one(mandel));

return EXIT_SUCCESS;
}

/* ----------------------------- */

MandelbrotGenerator::MandelbrotGenerator(int height, int width)
: x_(0), y_(0), height_(height), width_(width), eos_(false)
{
}

/* ---------- */

char MandelbrotGenerator::next()
{
char byte = 0; int bitNumber = 0, limitMarker; bool output = false;

for ( ; y_ < height_; ++y_)
{
for ( ; x_ < width_; ++x_)
{
Complex z, c(2.0 * x_ / width_ - 1.5, 2.0 * y_ / height_ - 1.0);

limitMarker = mandel(50, z, c);

bitNumber += 1; if (bitNumber == 8) output = true;

byte = (byte << 1) | limitMarker;

if (x_ == width_ - 1 && bitNumber != 8)
{
byte = byte << (8 - width_ % 8); output = true;
}

if (output) { ++x_; return byte; }
}

x_ = 0;
}

eos_ = true ; return EOS;
}

/* ----------- */

void MandelbrotGenerator::reset()
{
x_ = 0; y_ = 0; eos_ = false;
}

/* ----------- */

void MandelbrotGenerator::header(ostream& out) const
{
out << "P4" << "\n" << width_ << " " << height_ << endl;
}

/* ----------- */

int MandelbrotGenerator::mandel(int n, const Complex& z, const Complex& c)
{
if (real(z * conj(z)) > 4.0) return 0;
if (n == 0) return 1;
return MandelbrotGenerator::mandel(--n, z * z + c, c);
}

 

[Howard Hinnant]

I hope everyone is enjoying the Holiday Season !

Thank you, likewise.

I'm attempting to implement a function template [called 'generate_while']
modelled somewhat on the STL's, 'generate' and 'generate_n' algorithms. Now,
'generate_while', requires the use of temporary storage [mind the
line-wrap]:

template <class OutputIter_, class Generator_, class Predicate_>
OutputIter_ generate_while(OutputIter_ first_,
Generator_& gen_, Predicate_ pred_)
{
typename std::iterator_traits<OutputIter_>::value_type value_(gen_());
for ( ; pred_(value_); ++first_)
{
*first_ = value_; value_ = gen_();
}
return first_;
}

Section 24.3.1p2 of the standard says that the value_type of an output
iterator is void. Section 24.5.4 confirms this with the definition of
ostreambuf_iterator (setting its value_type to void).

Imho, you're right and the standard is wrong. :-(

But it is what it is. There is a chance (that chance is growing smaller
every day) that C++0X will have improved iterator concepts, and this is
one detail I'd love to see fixed.

Here is one non-standard way that you can fix your code for gcc:

- typename std::iterator_traits<OutputIter_>::value_type value_(gen_());
+ __typeof__(gen_()) value_(gen_());

In C++0X we will likely have a standard keyword that looks a lot like
__typeof__ (not exactly) and can be used like:

decltype(gen_()) value_(gen_());

That will do what you want as long as gen_() returns a non-reference
type. If it returns a reference type, then value_ will have reference
type (which may or may not be what you want).

Another (more standard) solution is to require of your predicate that it
follow the requirements laid down by std::unary_function: It has nested
types: argument_type and result_type. Then you could:

typename Predicate_::argument_type value_(gen_());

Personally I like the __typeof__ solution better, but it isn't as
portable.

For your amusement, here's an "almost solution" that we tried with TR1:

typename std::tr1::result_of<Generator_()>::type value_(gen_());

std::tr1::result_of might appear in a <functional> or <tr1/functional>
near you. It isn't standard. It is a standard's experiment.
Unfortunately in this particular case, result_of has a difficult time
deducing the correct return type. In gcc 4.x (if you change
<functional> to <tr1/functional>) AND if you add this line to
MandelbrotGenerator:

typedef char result_type;

then your code works. Without the result_type, gcc 4.x will again
default to void for this type. CodeWarrior 10 gets it right without the
result_type typedef.

There's no advice here, just entertainment. If you have to put
result_type into your generator anyway, you might as well just use it,
instead of taking the trip through result_of. And only some of the very
newest compilers will have this TR1 feature anyway.

Fwiw, you might consider rearranging your template arguments:

template <class Predicate_, class Generator_, class OutputIter_>
OutputIter_ generate_while(OutputIter_ first_, Generator_& gen_,
Predicate_
pred_)
{
....

I.e. consider which template argument you might ever want to let the
client code explicitly specify, and put that first. In the order I have
above, I've put the Predicate_ first, just to make it easy in case the
client would ever like to pass the predicate by reference instead of by
value:

MandelbrotGenerator:one pred(mandel);
generate_while<MandelbrotGenerator:one&>(StreamIterOut(cout),
mandel, pred);
// inspect pred here ...

Just a thought.

Hope this helps.

-Howard

 

[Anthony Borla]

Howard,

I'm attempting to implement a function template [called
'generate_while'] modelled somewhat on the STL's,
'generate' and 'generate_n' algorithms. Now, 'generate_while',
requires the use of temporary storage [mind the
line-wrap]:

template <class OutputIter_, class Generator_, class Predicate_>
OutputIter_ generate_while(OutputIter_ first_,
Generator_& gen_, Predicate_ pred_)
{
typename std::iterator_traits<OutputIter_>::value_type
value_(gen_());
for ( ; pred_(value_); ++first_)
{
*first_ = value_; value_ = gen_();
}
return first_;
}

Section 24.3.1p2 of the standard says that the value_type
of an output iterator is void. Section 24.5.4 confirms this
with the definition of ostreambuf_iterator (setting its
value_type to void).

Imho, you're right and the standard is wrong. :-(

But it is what it is. There is a chance (that chance is
growing smaller every day) that C++0X will have improved
iterator concepts, and this is one detail I'd love to see fixed.

Well I certainly didn't *expect* an iterator type to be 'void'
[counter-intuitive to say the least] even though that's exactly what the
compiler diagnostics were indicating. Ah well !

<SNIP>

I opted for the '__typeof__' fix, thank you.

I realise now that I should have better investigated the matter [e.g. a
better reading of the GCC doco would have revealed the above fix], but I was
really thrown because I had a - surprisingly - trouble-free session with the
Borland compiler, and thought it a mere formality to recompile with GCC. I
really should have known better !

Fwiw, you might consider rearranging your
template arguments:

template <class Predicate_, class Generator_, class OutputIter_>
OutputIter_ generate_while(OutputIter_ first_, Generator_& gen_,
Predicate_
pred_)
{
...

I.e. consider which template argument you might ever want to let the
client code explicitly specify, and put that first. In the order I have
above, I've put the Predicate_ first, just to make it easy in case the
client would ever like to pass the predicate by reference instead of by
value:

MandelbrotGenerator:one pred(mandel);
generate_while<MandelbrotGenerator:one&>(StreamIterOut(cout),
mandel, pred);
// inspect pred here ...

Just a thought.

Yes, a far cleaner way of approaching it.

My thanks, Howard, for an informative, and very helpful, post. Enjoy the
rest of the Holiday Season !

Cheers,

Anthony Borla