C++ Templates: Incomplete Type Problem

Discussion in 'C++' started by Anthony Borla, Dec 27, 2005.

  1. 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::eek:streambuf_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::eek: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::eek:streambuf_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);
    }
     
    Anthony Borla, Dec 27, 2005
    #1
    1. Advertising

  2. In article <hhasf.115290$>,
    "Anthony Borla" <> 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&>(StreamIterOut(cout),
    mandel, pred);
    // inspect pred here ...

    Just a thought.

    Hope this helps.

    -Howard
     
    Howard Hinnant, Dec 27, 2005
    #2
    1. Advertising

  3. "Howard Hinnant" <> wrote in message
    news:...
    > In article <hhasf.115290$>,
    > "Anthony Borla" <> 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&>(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
     
    Anthony Borla, Dec 28, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JKop
    Replies:
    3
    Views:
    522
  2. gk245
    Replies:
    2
    Views:
    1,264
    Christopher Benson-Manica
    May 6, 2006
  3. recover
    Replies:
    2
    Views:
    858
    recover
    Jul 25, 2006
  4. Belebele
    Replies:
    5
    Views:
    533
    Victor Bazarov
    Aug 29, 2007
  5. Replies:
    1
    Views:
    994
    Richard Bos
    Jan 17, 2008
Loading...

Share This Page