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

[Victor Bazarov]

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

 

[Heck]

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
};

 

[tragomaskhalos]

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) {}

 

[red floyd]

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) {

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.

 

[jg]

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

 

[=?iso-8859-1?q?Daniel_Kr=FCgler?=]

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

 

[=?iso-8859-1?q?Daniel_Kr=FCgler?=]

On Oct 3, 12:58 pm, Heck <[email protected]>
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

 

[Heck]

Daniel Krügler!

On 3 Okt., 21:58, Heck <[email protected]>

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?