correct usage of allocator::construct in a container

Discussion in 'C++' started by Dennis Jones, Feb 24, 2009.

  1. Dennis Jones

    Dennis Jones Guest

    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> >::eek: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, Feb 24, 2009
    #1
    1. Advertising

  2. Dennis Jones

    Dennis Jones Guest

    "Dennis Jones" <> wrote in message
    news:lAXol.1395$...

    <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
    Dennis Jones, Feb 24, 2009
    #2
    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. Vivi Orunitia
    Replies:
    11
    Views:
    4,453
    Martijn Lievaart
    Feb 4, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    514
    Maitre Bart
    Feb 11, 2004
  3. Steven T. Hatton
    Replies:
    4
    Views:
    3,874
    Rob Williscroft
    Dec 5, 2004
  4. Replies:
    4
    Views:
    786
    Daniel T.
    Feb 16, 2006
  5. Mukesh
    Replies:
    4
    Views:
    608
    Paul N
    Mar 26, 2010
Loading...

Share This Page