473,372 Members | 1,078 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,372 software developers and data experts.

C++ Templates: Incomplete Type Problem

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::Done(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::ostreambuf_iterator<char,
std::char_traits<char> >, Generator_ = MandelbrotGenerator, Predicate_ =
MandelbrotGenerator::Done]':
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::Done) (
<typeprefixerror>&)'
mandelbrot.cpp:64: error: candidates are: bool
MandelbrotGenerator::Done::operator()(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::ostreambuf_iterator<char,
std::char_traits<char>>, Generator_=MandelbrotGenerator,
Predicate_=MandelbrotGenerator::Done]"

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::Done(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);
}
Dec 27 '05 #1
2 9887
In article <hh*******************@news-server.bigpond.net.au>,
"Anthony Borla" <aj*****@bigpond.com> wrote:
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::Done pred(mandel);
generate_while<MandelbrotGenerator::Done&>(StreamI terOut(cout),
mandel, pred);
// inspect pred here ...

Just a thought.

Hope this helps.

-Howard
Dec 27 '05 #2
"Howard Hinnant" <ho************@gmail.com> wrote in message
news:ho**********************************@syrcnyrd rs-03-ge0.nyroc.rr.com...
In article <hh*******************@news-server.bigpond.net.au>,
"Anthony Borla" <aj*****@bigpond.com> wrote:

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 !

<SNIP>

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::Done pred(mandel);
generate_while<MandelbrotGenerator::Done&>(StreamI terOut(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
Dec 28 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Andrew Ward | last post by:
Hi All, Considering the following code: struct A; struct B { std::list<A> l; };
1
by: Bo Xu | last post by:
Object of Combination By Bo Xu Introduction A combination of n things, taken s at a time, often referred as an s-combination out of n, is a way to select a subset of size s from a given set of...
4
by: ro86 | last post by:
Hello everyone! I am a newbie to C++ (~1 Week experience) and I have a few months of experience with object-oriented languages (Objective-C). I am currently working just for fun on a particle...
5
by: Paul F. Dietz | last post by:
Is the following legal C? struct foo; struct foo (*p); /* Pointer to array of 10 foo structures */ struct foo { int bar; int baz; }; main() { printf("%d\n", sizeof(*p)); } Paul Dietz...
6
by: Pushkar Pradhan | last post by:
I tried to read the archives and solve this problem, but now I think I better post my problem: int main() { int blkSz = { {2,2}, {2,3}, ....., {6,6} }; write_bc_perf(mflops1, blkSz,...
2
by: dave_dp | last post by:
Hi folks, I'm interested as to what extent using incomplete types doesn't result in a undefined behavior, more generally it touches the usage of incomplete types.. for example, it is stated that...
9
by: Jerome Durand | last post by:
Hello, I'm trying to write something along the following lines but I cannot get this to compile. template <typename derivedstruct Base { typedef typename derived::valueType valueType;...
5
by: Belebele | last post by:
The code below does not compile under g++. There is an outer class template that contains and inner class template. The outer class template is fully specialized for int. Then a separate Foo...
50
by: Juha Nieminen | last post by:
I asked a long time ago in this group how to make a smart pointer which works with incomplete types. I got this answer (only relevant parts included): ...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.