[boost] How much should I care about allocators?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-20 19:33:20

Hi all,

I'm in the process of putting together my own submission for a
boost::tree<>, which has been discussed here on occasion before.
Without getting into much detail about the tree itself, I have two
nuts-and-bolts questions about conventions using allocators in
containers.

First: The standard allocator concept has several distinct typedefs:
"value_type", "pointer", "reference", etc. My understanding is that
the main motivation for allocators was the necessity to  abstract out
differences in pointer types on different platforms. So I assume this
implies that to use an allocator properly, one can't necessarily
expect that "pointer" is identical to "value_type*". I hope this
assumption is correct so far.

What I take this to further imply is that in my container, I need to
write code of this nature:

template <typename T, typename A = std::allocator<T> >
class tree {

public:

  typedef A allocator_type;
  typedef typename A::value_type value_type;
  typedef typename A::pointer pointer;
  typedef typename A::reference reference;
  // etc.

private:

  class node_t;

  typedef typename A::template rebind<node_t>::other node_allocator;
  typedef typename node_allocator::value_type node;
  typedef typename node_allocator::pointer node_pointer;

  class node_t {

    pointer t_;
    node_pointer parent_;
    // etc.

  };
  // etc.

};

In other words, to respect the allocator I've been given, I need to
make sure my internal node structure uses the rebound node allocator's
pointer and value types, and so forth. So my first question is, is
this assumption correct? The reason I ask is that looking over the
standard library implementation that comes with gcc 4.0, I noticed
that their implementation of std::list<> has nodes which contain
straight pointers, rather than the allocator typedef equivalents. To
me that seems to contradict my assumption, assuming the gcc
implementation is correct.

My second question is about allocator's construct() method. The
implementation of std::allocator has construct() invoking the copy
ctor using placement new(). That much is self-explanatory. It also
seems reasonable to me that allocator does not have construct()
methods taking arbitrary parameters. But I'm not sure I understand the
reason why it does not have a construct() method to invoke an object's
default ctor. What that implies to me, and seems to be supported by
gcc's list implementation, is that the nodes in my tree mustn't have a
default ctor that actually does anything, because the only way to
properly initialize objects using an allocator is through copying. Is
that correct?

What this boils down to is, using allocators seems to dictate some
aspects of how I design and implement this tree (or any container). So
how much should I strive to operate within their limitations, and am I
understanding these limitations correctly? I hope this is an
appropriate forum for these questions.

Thanks very much,
dr