Jump to content
  • Advertisement
Sign in to follow this  
dmatter

stl allocator query

This topic is 4832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

currently I am implementing a custom STL container for my generic resource manager. I have looked over my compilers implementation of the stl vector and have seen how it was done there, and using numerous web resources I am almost finished. However there are one or two parts that I don't fully understand regarding the allocation and deallocation of a raw array using an allocator. From looking at the stl vector I have pieced together some code that 'seems' to do the job - but I would like help to understand how it works and if there is a better way to achieve it. here is a simplified version of what I have:
template < class _T, class _Alloc = std::allocator<_T> >
class my_container
{
//All typedefs and the rest of it etc here
public:
  typedef T       value_type;
  typedef _Alloc  allocator_type;

//... etc, etc..

protected:
  struct raw_alloc : public _Alloc
  {
    raw_alloc(_Alloc const& a) : _Alloc(a), first(0), last(0) { }

    void impl_deallocate (value_type *Tp, size_t n) { if (Tp) this->deallocate(Tp, n); }
    value_type *first;
    value_type *last;
  };

  raw_alloc arr;

public:
  //Default Constructor - creates an empty container - (no problem here)
  my_container (const allocator_type &a = allocator_type()) : arr(a) { }

  //Sizing Constructor - supposed to make the array a set size
  my_container (size_t num, const allocator_type &a = allocator_type()) : arr(a)
   { arr.first = arr.allocate(num);
     arr.last = std::uninitialized_fill_n(arr.first, num, value_type());
   }

  //Destructor
  ~my_container ()
  { std::_Destroy(this->arr.first, this->arr.last);
    arr.impl_deallocate(arr.first, arr.last - arr.first);
  }

};



I hope that right. Anyway: 1) In the 'Sizing Constructor' I understand why I need the arr.allocate() but it doesn't seem to initialise the array's elements so I use uninitialized_fill_n which takes a pre-made value_type and initialises the elements with their copy constructor. Is there a better way of doing this? - I would like to be able to make the array and automatically construct all the elements using their default constructor. 2) In the destructor -this was pieced together from my cmopilers implementation of stl_vector- I don't understand why I need std::_Destroy (it seems to call the destructors of the array elements individually) but why doesn't _Alloc.deallocate() do that? So what does deallocate actually do? Its just a bit confusing. Any help would be most appreciated [smile] p.s. No dought once I've posted I will notice small mistakes (I don't usually like posting code for that very reason) so be wary of my editing the post and making minor changes. Again thanx.

Share this post


Link to post
Share on other sites
Advertisement
The standard library allocator concept separates allocation/deallocation and construction/destruction this is due to efficiency reasons for particular types of data structures (like dynamic arrays ala std::vector). This is the reason why you do not see allocate/deallocate invoke constructors/destructors, there are seperate member functions for that task.

how-ever there is a minor flaw in the allocator concept, typically implementations use allocators of nodes (like for trees or linked-lists) not allocators to the actual type to be contained. These nodes are typically aggregate types where no constructors are defined and they are only allocated/deallocated, only the value types they hold are constructed this is due to 2 reasons, one is efficiency the second is finer control over construction process where the value type's constructor may throw an exception.

The problem is that an allocator of nodes can only construct/destruct nodes so alot of compilers define the template functions std::_Construct/std::_Destruct to construct/destruct values, nodes are only allocated. std::_Construct typically uses the placement new operator and std::_Destruct typically explicitly invoke the destructor.

Another thing you'll notice most imps do is define a non-documented non-polymorphic base, these bases are used to implement some RAII and empty base optimization (EBO) for allocators, the base is mainly used to allocate uninitialized memory in the constructor and deallocate memory in the destructor so if a failure or exception occurs resources are more likely to be properly freed.

There are two minor problems in your code, first is the use of underscores on the front are reserved for implementators, the second is using the allocator directly like that is prone to error you should do something like this:


template < typename Tp, typename Alloc = std::allocator<Tp> >
struct foo {

typedef typename Alloc::template rebind<Tp>::other allocator;

struct foo_impl : allocator { //implements empty base optimizations
//....
foo_impl(const allocator& n = allocator())
: allocator(n) {}
};
//....
};


Take note that this is an example, if this was say to implement a list with a linked-list then typically you would rebind the allocator to make an allocator of list nodes not just the value type.

[Edited by - snk_kid on May 22, 2005 3:44:55 AM]

Share this post


Link to post
Share on other sites
Quote:

There are two minor problems in your code, first is the use of underscores on the front are reserved for implementators, the second is using the allocator directly like that is prone to error you should do something like this:



template < typename Tp, typename Alloc = std::allocator<Tp> >
struct foo {

typedef typename Alloc::template rebind<Tp>::other allocator;

struct foo_impl : allocator { //implements empty base optimizations
//....
foo_impl(const allocator& n = allocator())
: allocator(n) {}
};
//....
};


OK, thanks for the tip - i'll remove the underscores from my code.

erm, in your code you use rebind, as far as I know that simply allows you to get allocators for alternate types but in your example you rebind to the same type (rebind<Tp>) so I guess its not necessary (could you confirm that for me please - all this is a learning curve [smile]).

secondly, I too have used EBO in my code but the struct does not take a default value in its constructor (as yours does) because the my_container constructor always supplies it with one - So I see no real difference there.

Quote:

The problem is that an allocator of nodes can only construct/destruct nodes so alot of compilers define the template functions std::_Construct/std::_Destruct to construct/destruct values, nodes are only allocated. std::_Construct typically uses the placement new operator and std::_Destruct typically explicitly invoke the destructor.


Because the compilers define those functions does that mean it is not portable? so I shouldn't use them? Allocators do have the members construct() and destruct() - are they better to use alongside allocate() and deallocate() (although I don't remember how they work, might I have to use them in a loop?)

Again thanks for any help it is most apreciated.

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
erm, in your code you use rebind, as far as I know that simply allows you to get allocators for alternate types but in your example you rebind to the same type (rebind<Tp>) so I guess its not necessary (could you confirm that for me please - all this is a learning curve [smile]).


Yeah i wasn't sure exactly what kind of data structure your making (looks like some kind of dynamic array) and if you knew about the rebind trick, it just an example of how do it.

The reason for the rebind trick only really applies to data structures with nodes because without it would probably lead to clients making assumptions on implementation, for example if you where going to use a custom allocator type for std::list your instinct would probably make you write:


typedef std::list<foo, foobar_allocator<foo> > foo_list;


but really std::list will rebind it to an allocator of linked-list nodes which is an implementation detail, with-out the rebind trick clients would have specifiy the exact correct type of allocator thus making code non-portable. In your case it look likes it doesn't apply.

Quote:
Original post by dmatter
secondly, I too have used EBO in my code but the struct does not take a default value in its constructor (as yours does) because the my_container constructor always supplies it with one - So I see no real difference there.


No worry, i thought i would mention it if you didn't know the reason why that was being done (not the constructor bit), reason being EBO.

Quote:
Original post by dmatter
Because the compilers define those functions does that mean it is not portable? so I shouldn't use them?


Yeah sort of, you can tell from the underscores on the front that those are an imp details and generally non-portable, in anycase they are not defined in the standard as i'm aware of but it probably wont matter that much in this case because of the issues i mentioned previously. I've seen those template functions in VC++, GCC, and STLport probably other compiler vendors do the same.

Quote:
Original post by dmatter
Allocators do have the members construct() and destruct() - are they better to use alongside allocate() and deallocate() (although I don't remember how they work, might I have to use them in a loop?)


Using the uninitialized variants of the standard library algorithms are fine, as long as you remember to destruct elements later on, there is also a special iterator for uninitialized memory too called raw_storage_iterator

As your allocator type is an allocator of the actual type to be contained as opposed to an allocator of nodes you it would probably be best to use the allocator's member functions construct/destuct. To use them is easy, really simplified silly example [smile]:


Tp* create_element(const Tp& val) {

Tp* element = impl.allocate(1); // allocate only, one elememt

impl.construct(element, val); // in-place construct only

return element;
}

void put_element(Tp* p) {

impl.destruct(p); // in-place destruct only
impl.deallocate(p); // give memory back
}


of course you wouldn't normally do something like that for something like a dynamic array [smile].

Share this post


Link to post
Share on other sites
okaly-dokaly..

So for a (sort-of) array implementation I would have to loop right? (heres a quickly modified version to demostrate my meaning):


Tp* create_elements(size_t n, const Tp& val) {

Tp* element = impl.allocate(n); // allocate only, one elememt

for (size_t i = element, i < n, ++i)
impl.construct(element+i, val); // in-place construct only

return element;
}

void put_element(size_t n, Tp* p) {

for (size_t i = element, i < n, ++i)
impl.destruct(p); // in-place destruct only
impl.deallocate(p); // give memory back
}


NOTE: I know the loops are not optimul but..

is that the basic idea?

Thanx you've been a massive help anywayz [smile] (rating++)

Edit: wow wot a huge rating you have!!!

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
is that the basic idea?


Yeah but i think you made a slight typo in put_element by accident, also deallocate has a second parameter (which has a default value) that takes the number of elements to deallocate you should provide this because custom allocates may use that parameter and to match the number of elements you got from "allocate" i.e:


impl.deallocate(p, n);


What i think you should do is have a protected non-polymorphic base that deals with allocation/deallocation only (basically implement RAII), one of the base constructors can take size of the number of elements to allocate only, its destructor deallocates memory, this will be automatically invoked for the full derived class.

After thinking about it some more i think it would be better to use the uninitialized versions of standard library algorithms as it just makes the code cleaner but you'll have to forget about using the allocator's construct/destroy and just do destruction yourself (construction taken care by the uninitialized algorithms, they use placement new operator internally to construct in-place):


#include <cstddef> // size_t
#include <memory> // allocator, uninitialized_fill_n
#include <algorithm> // for_each

template < typename Tp, typename Alloc >
struct foo_base {

typedef std::size_t size_type;
typedef Alloc allocator_type;

struct foo_impl : Alloc {

Tp* first;
Tp* last;

foo_impl(const Alloc& a)
: Alloc(a), first(0), last(0) {}
};

foo_impl impl;

allocator_type get_allocator() const { return *static_cast<const Alloc*>(&this->impl); }

Tp* allocate(size_type n) {
return impl.allocate(n);
}

void deallocate(Tp* p, size_type n) {
if(p) // pointer is not permitted to be null
impl.deallocate(p, n);
}

foo_base(const allocator_type& a)
: impl(a) {}

foo_base(size_type n, const allocator_type& a)
: impl(a) {
impl.first = allocate(n);
impl.last = impl.first + n;
}

~foo_base() {
deallocate(impl.first, impl.last - impl.first);
}

};

template < typename Tp, typename Alloc = std::allocator<Tp> >
struct foo : protected foo_base<Tp, Alloc> {

typedef Tp value_type;

explicit foo(const allocator_type& a = allocator_type())
: foo_base(a) {}

foo(size_type n, const value_type& val = value_type(),
const allocator_type& a = allocator_type())
: foo_base(n, a) {
std::uninitialized_fill(impl.first, impl.last, val);
}

~foo() {

struct destroyer {
void operator()(const Tp& val) const {
val.~Tp();
}
};

std::for_each(impl.first, impl.last, destroyer());
}
};


There is one thing you need to be careful with when dealing with in-place copy construction, value type's constructors may throw exceptions so you should put a try catch block over it, if an exception is throw then just dellocate memory and rethrow the exception, to be able to catch any type of exception possiable use "..." :


try {

//in-place copy construction over an template iterator range

} catch(...) { //catch anything thrown by value_type's constructors

// exception thrown, deallocate memory

throw ; //rethrow exception

}


Do this with operations that deal with copying a number of elements in one go from a template iterator range, you'll see this done in your implementation of std::vector. The reason being if the iterators are stream iterators values are going to be read from a file or some where else like a network stream, the value type's constructor might throw an exception when an invalid value is read or something similar.

[Edited by - snk_kid on May 23, 2005 4:16:25 PM]

Share this post


Link to post
Share on other sites
wow, thanks snk_kid you've been tonnes of help (or is it tons - which ever is bigger [smile])

Quote:
Original post by snk_kid
Yeah but i think you made a slight typo in put_element by accident


hmm, when I make a typo I don't mess around either - there's mistakes all over that code. I was in a hurry to finish though. When theres a typo worth making might as well make it a good one :)

anywayz once agen youve been a big help cheerz

[Edited by - dmatter on May 24, 2005 5:52:18 AM]

Share this post


Link to post
Share on other sites
I'm not sure if it's been said, but note that because of the neccesity of the rebind trick and for speed reasons, implementations are allowed to assume that any allocator of the same type is the same, so you should only be using static data inside the allocator.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!