Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > correct usage of allocator::construct in a container

Reply
Thread Tools

correct usage of allocator::construct in a container

 
 
Dennis Jones
Guest
Posts: n/a
 
      02-24-2009
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


 
Reply With Quote
 
 
 
 
Dennis Jones
Guest
Posts: n/a
 
      02-24-2009
"Dennis Jones" <(E-Mail Removed)> wrote in message
news:lAXol.1395$(E-Mail Removed)...

<snip>
> 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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
container inside container in stl wolverine C++ 2 07-24-2006 03:08 PM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
std::transform container => std::abs(container) Steven T. Hatton C++ 4 12-05-2004 07:10 AM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments