correct usage of allocator::construct in a container

[Dennis Jones]

Hi,

I'm working on a node-based container class and I am having trouble
understanding why my contained objects are being constructed so many times.
Given a node class like this:

template <class T>
struct Node
{
Node *Next, *Prev;
T Data;
};

My understanding is that I need to allocate nodes like this:

template <class T, allocator_type = std::allocator<T> >
class Container
{
typedef typename allocator_type::template rebind< Node<T> >:ther
node_allocator_type;
node_allocator_type NodeAllocator;

Node *AddItem( const T &Item )
{
Node *NewNode = NodeAllocator.allocate(1,0);
NodeAllocator.construct( NewNode, Node() );
NewNode->Data = Item;
return NewNode;
}
};

This seems wasteful. First, it requires the Node class to have a default
constructor. So, I add a default constructor:

Node()
: Next( NULL ),
Prev( NULL ),
Data() {}

Second, it requires the value type to be assigned afterwards, resulting in
an operator=() call in my data type, including a swap() call. It occurred
to me that I could eliminate some of that waste by adding a constructor to
my Node class that accepts an instance of my data type:

Node( const T &Item )
: Next( NULL ),
Prev( NULL ),
Data( Item ) {}

.... and calling it like this:

Node *AddItem( const T &Item )
{
Node *NewNode = NodeAllocator.allocate(1,0);
NodeAllocator.construct( NewNode, Node(Item) ); // use Node( const
T &)
return NewNode;
}

Still, calling AddItem to insert a new node into the container results in
what seems like an extra, unnecessary constructor call of my data type. If
my data type is defined as:

struct Test
{
int x;
Test() : x( 0 ) {}
Test(int a) : x( a ) {}
Test( const Test &other ) : x( other.x ) {}
~Test() {}
Test &operator=( const Test &rhs )
{
Test( rhs ).swap( *this );
return *this;
}
void swap( Test &other ) { std::swap( x, other.x ); }
};

Then, adding an instance to the container like this:

Container<Test> container;
container.AddItem( Test(3) );

results in the following constructor/destructor calls (in this order):

1) Test (int a)
2) Test( const Test &other )
3) Test( const Test &other )
4) ~Test()
5) ~Test()
6) ~Test()

It seems to me that one of those copy-constructor calls is unnecessary.
Both copy-constructor calls are occuring here:

NodeAllocator.construct( NewNode, Node(Item) );

The first copy-constructor occurs when the temporary Node(Item) in the above
call is created. The second copy-constructor occurs when the placement new
operator is invoked from construct():

template <class T1, class T2>
inline void __construct (T1* p, const T2& value)
{
new (p) T1(value); <-- copy-constructor call
}

If I use new directly (instead of using the allocator), I can eliminate the
extra copy-constructor:

Node *NewNode = new Node( Item );


This might not seem like a big deal, but for large numbers of objects that
are expensive to copy/construct, the extra constructor call seems terribly
inefficient. Am I using the allocator correctly? If so, how can this be
acceptable in the STL? I realize that allocators give container users more
flexibility, but is it worth the cost of an extra constructor call for every
object in the container? If I am not using the allocator correctly, can
someone please show how to use it correctly?

Thanks,

Dennis

 

[Dennis Jones]

This might not seem like a big deal, but for large numbers of objects that
are expensive to copy/construct, the extra constructor call seems terribly
inefficient. Am I using the allocator correctly? If so, how can this be
acceptable in the STL? I realize that allocators give container users
more flexibility, but is it worth the cost of an extra constructor call
for every object in the container? If I am not using the allocator
correctly, can someone please show how to use it correctly?

I believe I found the answer to my own question. It seems I am not
using the allocator correctly. To minimize copy-construction for a
node-based container, I need to follow a slightly different approach,
specifically:

1) Allocate a Node (using the node allocator)
2) Construct a T at Node->Data (using the value allocator)

Node *NewNode = NodeAllocator.allocate(1,0);
ValueAllocator.construct( &NewNode->Data, Item );

.. . . and now I get only one copy-constructor call (instead of two) when
adding elements to my container.

- Dennis