template question: preallocation for the underlying deque in user-defined queue

Discussion in 'C++' started by Victor Bazarov, Oct 3, 2007.

  1. Heck wrote:
    > I borrowed N. Josuttis's code for a queue ("The C++ Standard Library",
    > 1999, p. 450), with which he modifies the interface to read and
    > discard the front element on pop() and to throw an exception if
    > front() or pop() is called when the queue is empty.
    >
    > I want to further modify the new queue class to accept an int as the
    > number of elements the underlying deque will allocate upon
    > construction. std::deque's got a constructor for this but I can't
    > figure out how to access it. I just don't understand templates
    > sufficiently clearly. Would you please suggest a syntax I can use and
    > explain how it works? Thanks.
    >
    > Here's the relevant part of the code:
    > #include <deque>
    > #include <exception>
    >
    > template <class T> class QUEUE2 {
    > protected:
    > std::deque<T> c; // the actual container
    >
    > public:
    > /* *********
    > This sad business makes the code fail to compile. I've tried a
    > number of variations which result in redefinitions of c (the actual
    > container) or c not found.
    > // constructor - allow a pre-allocation for the deque's elements
    > QUEUE2( int prealloc) {
    > std::deque<T> c( prealloc ); // the actual container


    If you want to give your 'c' some size to begin with (not sure why
    you would want this), you need to _initialise_ it, not try to declare
    a local variable 'c' in the constructor's body.

    I am guessing you're not familiar with *initialiser lists*. Read up
    on proper implementations of constructors. Read the FAQ as well.

    If I were you, I would still revisit your intent to give 'c' some
    initial size. What for? Are you going to do assignment instead of
    'push_back' until the size grows up to your 'prealloc'? Why bother?
    I say, let 'std::deque' worry about allocations, it usually does
    a very good job.

    > }
    > ********** */
    > // exception class
    > class read_empty : public std::exception {
    > public:
    > virtual const char * what() const throw() {
    > return "Read or popped an empty QUEUE2";
    > }
    > };
    >
    > // read front element, return its value then discard it
    > T pop()
    > {
    > if ( c.empty())
    > throw read_empty();
    >
    > // otherwise, we're OK
    > T elem( c.front() );
    > c.pop_front();
    > return elem;
    > }
    >
    > // the rest of the usual queue funcs are implemented, e.g.,
    > // size()
    > // empty()
    > // push()
    > // front() like pop(), w/ the throw
    > };


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Oct 3, 2007
    #1
    1. Advertising

  2. Victor Bazarov

    Heck Guest

    I borrowed N. Josuttis's code for a queue ("The C++ Standard Library",
    1999, p. 450), with which he modifies the interface to read and
    discard the front element on pop() and to throw an exception if
    front() or pop() is called when the queue is empty.

    I want to further modify the new queue class to accept an int as the
    number of elements the underlying deque will allocate upon
    construction. std::deque's got a constructor for this but I can't
    figure out how to access it. I just don't understand templates
    sufficiently clearly. Would you please suggest a syntax I can use and
    explain how it works? Thanks.

    Here's the relevant part of the code:
    #include <deque>
    #include <exception>

    template <class T> class QUEUE2 {
    protected:
    std::deque<T> c; // the actual container

    public:
    /* *********
    This sad business makes the code fail to compile. I've tried a
    number of variations which result in redefinitions of c (the actual
    container) or c not found.
    // constructor - allow a pre-allocation for the deque's elements
    QUEUE2( int prealloc) {
    std::deque<T> c( prealloc ); // the actual container
    }
    ********** */
    // exception class
    class read_empty : public std::exception {
    public:
    virtual const char * what() const throw() {
    return "Read or popped an empty QUEUE2";
    }
    };

    // read front element, return its value then discard it
    T pop()
    {
    if ( c.empty())
    throw read_empty();

    // otherwise, we're OK
    T elem( c.front() );
    c.pop_front();
    return elem;
    }

    // the rest of the usual queue funcs are implemented, e.g.,
    // size()
    // empty()
    // push()
    // front() like pop(), w/ the throw
    };


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Heck, Oct 3, 2007
    #2
    1. Advertising

  3. Re: template question: preallocation for the underlying deque in user-defined queue

    On 3 Oct, 20:58, Heck <>
    wrote:
    >
    > template <class T> class QUEUE2 {
    > protected:
    > std::deque<T> c; // the actual container
    >
    > public:
    > /* *********
    > This sad business makes the code fail to compile. I've tried a
    > number of variations which result in redefinitions of c (the actual
    > container) or c not found.
    > // constructor - allow a pre-allocation for the deque's elements
    > QUEUE2( int prealloc) {
    > std::deque<T> c( prealloc ); // the actual container
    > }


    Try:
    QUEUE2(int prealloc) : c(prealloc) {}


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    tragomaskhalos, Oct 3, 2007
    #3
  4. Victor Bazarov

    red floyd Guest

    Heck wrote:
    > I borrowed N. Josuttis's code for a queue ("The C++ Standard Library",
    >
    > /* *********
    > This sad business makes the code fail to compile. I've tried a
    > number of variations which result in redefinitions of c (the actual
    > container) or c not found.
    > // constructor - allow a pre-allocation for the deque's elements

    QUEUE2 (int prealloc) : c(prealloc) {
    std::deque<T> c;

    > QUEUE2( int prealloc) {
    > std::deque<T> c( prealloc ); // the actual container
    > }
    >



    Read your C++ book (not Josuttis -- it's a library ref) , especially
    where it discusses initialization lists.

    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    red floyd, Oct 3, 2007
    #4
  5. Victor Bazarov

    jg Guest

    Re: template question: preallocation for the underlying deque in user-defined queue

    On Oct 3, 12:58 pm, Heck <>
    wrote:

    >
    > template <class T> class QUEUE2 {
    > protected:
    > std::deque<T> c; // the actual container
    >
    > public:
    > /* *********
    > This sad business makes the code fail to compile. I've tried a
    > number of variations which result in redefinitions of c (the actual
    > container) or c not found.
    > // constructor - allow a pre-allocation for the deque's elements
    > QUEUE2( int prealloc) {
    > std::deque<T> c( prealloc ); // the actual container
    > }


    The c in the ctor is a local object that also hides the field c
    in class QUEUE2, which is not what you want.

    You can try the following:

    template <class T> class QUEUE2 {
    ...
    std::deque<T> *c;
    ....
    QUEUE2( int prealloc) {
    c = new std::deque<T> (prealloc);
    }

    Or
    template <class T, int n> class QUEUE2 {
    ...
    std::deque<T> c(n);
    ...
    }
    where I think 'n' must be compile-time constant when
    instantiating QUEUE2.

    JG


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    jg, Oct 3, 2007
    #5
  6. Re: template question: preallocation for the underlying deque in user-defined queue

    On 3 Okt., 21:58, Heck <>
    wrote:
    > I want to further modify the new queue class to accept an int as the
    > number of elements the underlying deque will allocate upon
    > construction. std::deque's got a constructor for this but I can't
    > figure out how to access it. I just don't understand templates
    > sufficiently clearly. Would you please suggest a syntax I can use and
    > explain how it works? Thanks.


    Actually your problem is not related to templates at all.
    You need to use the initializer list of the class, v.i.


    > Here's the relevant part of the code:
    > #include <deque>
    > #include <exception>
    >
    > template <class T> class QUEUE2 {


    I strongly recommend that you don't use all-upper-case
    names for non-macro entities. Why is Queue2 not ok for you?
    I have the above mentioned book not at my hands, but if
    this also uses this nameing scheme, you should not copy
    this style.


    > protected:
    > std::deque<T> c; // the actual container
    >
    > public:
    > /* *********
    > This sad business makes the code fail to compile. I've tried a
    > number of variations which result in redefinitions of c (the actual
    > container) or c not found.
    > // constructor - allow a pre-allocation for the deque's elements
    > QUEUE2( int prealloc) {
    > std::deque<T> c( prealloc ); // the actual container
    > }
    > ********** */


    As you already recognize, you are defining a new, local
    entity c here. If you want to initialize base classes
    or members (as the member c in your example), you have to
    use the so-called member-initializer list therefore:

    QUEUE2( int prealloc) : c(prealloc) {
    }

    Greetings from Bremen,

    Daniel Krügler


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    =?iso-8859-1?q?Daniel_Kr=FCgler?=, Oct 3, 2007
    #6
  7. Re: template question: preallocation for the underlying deque in user-defined queue

    On 4 Okt., 00:37, jg <> wrote:
    > On Oct 3, 12:58 pm, Heck <>
    > You can try the following:
    >
    > template <class T> class QUEUE2 {
    > ...
    > std::deque<T> *c;
    > ....
    > QUEUE2( int prealloc) {
    > c = new std::deque<T> (prealloc);
    > }


    Although possible, this is not recommended here. Now the OP
    has to define copy c'tor, assignment op, and the destructor
    as well with no real advantage compared to the simple way.

    > Or
    > template <class T, int n> class QUEUE2 {
    > ...
    > std::deque<T> c(n);
    > ...}
    >
    > where I think 'n' must be compile-time constant when
    > instantiating QUEUE2.


    This is currently no valid C++, albeit their exists a proposal which
    would allow exactly this, see:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2354.htm

    What you are thinking of is only possible for static constants
    of integral or enumeration type where the initialization expression
    is an ICE. This constraint will be probably lifted somewhat in
    C++0x, but also only for static members of literal types which
    are initialized with a constant expression, see the most recent
    draft N2369.

    Greetings from Bremen,

    Daniel Krügler


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    =?iso-8859-1?q?Daniel_Kr=FCgler?=, Oct 4, 2007
    #7
  8. Victor Bazarov

    Heck Guest

    Re: Re: template question: preallocation for the underlying deque in user-defined queue

    Daniel Krügler!
    >On 3 Okt., 21:58, Heck <>


    snip

    Thank you all very much for your help. You made it clear to me that
    it was not templates that I was failing to understand but the scoping
    rules. I realize I imagined, with no justification, I might be able
    to simply send the int on to the underlying class because I was
    working inside a template.

    Victor, I wanted to preallocate the deque because I believe I will be
    able to guess my queue's minimum and maximum number of elements
    and so want to save my program the extra work of allocating the
    elements individually. Even if makes no appreciable difference, with
    this code, I'll be able to tell.

    Thank you, Dave and Daniel for providing the snippet of code
    queue2( int prealloc) : c(prealloc) {}
    I didn't know such syntax (i.e., c(prealloc) ) was valid.

    Thank you, JG for your suggestions and Daniel for your comments to
    him.

    Josuttis doesn't use the all-cap QUEUE2. I chose that to signal that
    this was my own modified version of queue. "queue2" serves also. Is
    it really so very unusual for people to use all caps for other than
    #defines that you should consider it unacceptable?


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Heck, Oct 7, 2007
    #8
    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. Gernot Frisch

    std::container - preallocation size?

    Gernot Frisch, Jul 21, 2004, in forum: C++
    Replies:
    5
    Views:
    1,312
    John Harrison
    Jul 21, 2004
  2. Russell Warren
    Replies:
    5
    Views:
    406
    Tim Peters
    May 2, 2006
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    672
    Russell Warren
    Jun 27, 2006
  4. Kris
    Replies:
    0
    Views:
    467
  5. bintom
    Replies:
    6
    Views:
    607
    Öö Tiib
    Nov 3, 2012
Loading...

Share This Page