Allocator probmels

[Orjan Westin]

Hi,

I have an interesting (read frustrating) problem. I'm writing a
generic container class, which holds data as well as links to other
instances of itself, like this:

template<class T>
class node
{
public:
typedef node<T>* pointer;
typedef T* data_pointer;
typedef std::vector<pointer> nodes;
typedef other_nodes::iterator iterator;
//...
iterator begin() {return _other_nodes.begin();}
//...
private:
pointer _one_node;
nodes _other_nodes;
data_pointer _data;
};

All fine and dandy. However, looking up how to write containers, I
read that any user-defined container is supposed to use the allocator
interface for all storage management, and define an iterator type.
Fine, that's no problem, I thought, especially since I had the
iterator anyway:

template<class T, class A = std::allocator<T> >
class node
{
public:
typedef node<T>* pointer;
typedef A:ointer data_pointer;
//...
data_pointer data() {return _data;}
//...
private:
pointer _one;
nodes _other_nodes;
data_pointer _data;
};

Still ok.

But.

Do I also need to use the allocator interface to manage my pointers?
If so, I should pass that allocator on to the vector class as well,
right? But since it's a different type, I need a new allocator:

template<class T, class A = std::allocator<T>, class P =
std::allocator<node*> >
class node
{
public:
typedef node<T>* pointer;
typedef std::vector<pointer, P> nodes;
//...
};

Silly me, of course that doesn't work, there are no template
arguments. Let's put one in:

template<class T, class A = std::allocator<T>, class P =
std::allocator<node<T>* > >
class node
{
public:
typedef node<T>* pointer;
typedef std::vector<pointer, P> nodes;
//...
};

And this is where I realised I had problems. Self-referential
declarations? Compiler nesting overload.

What bugs me is that it's ok to use the class inside its own class
declaration, like I do when declaring the vector with the pointers,
but not outside. Yes, of course I understand why, but it took a bit
of thinking.

So, any suggestions? Can I get away with only providing an allocator
interface to the templated class, and use std::allocator internally
for the pointers?

But since I will, on occasion, create another object to point at
internally, I wouldn't be using the allocator interface for that:

template<class T, class A = std::allocator<T> >
class node
{
public:
typedef node<T, A>* pointer;
typedef A::const_reference data_const_reference;

// Assignment constructor taking allocator
node(data_const_reference d, A al = A()) :
_one(NULL),
_alloc(al) {
_data = _alloc.allocate(1);
_alloc.construct(d);}

// Create a new node
void add_one(data_const_reference d) {
pointer p = new node<T, A>(d); // Argh!
_alloc.destroy(_one);
_one = p;}
//...
private:
A _alloc;
pointer _one;
nodes _other_nodes;
data_pointer _data;
};

Help!

//Orjan

 

[John Harrison]

Hi,

I have an interesting (read frustrating) problem. I'm writing a
generic container class, which holds data as well as links to other
instances of itself, like this:

template<class T>
class node
{
public:
typedef node<T>* pointer;
typedef T* data_pointer;
typedef std::vector<pointer> nodes;
typedef other_nodes::iterator iterator;
//...
iterator begin() {return _other_nodes.begin();}
//...
private:
pointer _one_node;
nodes _other_nodes;
data_pointer _data;
};

All fine and dandy. However, looking up how to write containers, I
read that any user-defined container is supposed to use the allocator
interface for all storage management, and define an iterator type.
Fine, that's no problem, I thought, especially since I had the
iterator anyway:

template<class T, class A = std::allocator<T> >
class node
{
public:
typedef node<T>* pointer;
typedef A:ointer data_pointer;
//...
data_pointer data() {return _data;}
//...
private:
pointer _one;
nodes _other_nodes;
data_pointer _data;
};

Still ok.

But.

Do I also need to use the allocator interface to manage my pointers?
If so, I should pass that allocator on to the vector class as well,
right? But since it's a different type, I need a new allocator:

That's where you are wrong. You can use the rebind facility of any allocator
to create a new allocator of a different type. The syntax is pretty hairy
however

typedef typename A::template rebind<pointer>:ther pointer_allocator;

typedef std::vector<pointer, pointer_allocator> nodes;

I hope I got that right.

john

 

[Siemel Naran]

typedef typename A::template rebind<pointer>:ther pointer_allocator;

This is right. Strange, when taking advantage of the empty base
optimization, on my compiler Borland 6 when I say

template <class T, class A = std::allocator<T> >
class lstack : public typename typename A::template ...

then it gives a syntax error, and the workaround is to remove the 'typename'
keyword above, though I think the keyword is necessary.

In the class definition, I have to define the typedef with the 'typename'
keyword in place.

typedef typename A::template ... real_allocator_type;

 

[Orjan Westin]

That's where you are wrong. You can use the rebind facility of any
allocator to create a new allocator of a different type. The syntax
is pretty hairy however

Ah, yes. Thank you very much. I'll have to write myself a little testing
allocator one of these days, but it's not something you would have to do
often I believe.

typedef typename A::template rebind<pointer>:ther
pointer_allocator;

typedef std::vector<pointer, pointer_allocator> nodes;

I hope I got that right.

Yup. Both compiles and works. Do you mind if I credit you with name and
where I found you? I'm writing a little article about this, you see.

Orjan