Thread: Custom allocators

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262

    Custom allocators

    Hi everybody,

    I was looking through custom allocators. For example std::set is defined as follows:
    Code:
    template < class Key, class Compare = less<Key>,
               class Allocator = allocator<Key> > class set;
    What I find odd about this is that the allocator here apparently only allocates integer. A set will use an AVL tree or red-black tree internally, however, and each element inside a set will need more information than just the stored value. For example, each node in the tree will at least contain two child nodes.
    Imagine a set of integers: the allocator will only be able to allocate integers. So how does it work internally? Does it allocate the tree's nodes simply by using "new", bypassing the allocator, and store a pointer to the allocated integer in the node?
    That sounds to me as though it kind of defeats the purpose of the allocator, especially if it's used as optimization, for example using memory pools. Or am I missing something here?

    Thanks in advance,
    Evoex

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    The `std::set' class doesn't only allocate integers; it allocates whatever it wants by rebinding--with `allocator<???>::rebind'--the allocator to fit the purpose.

    There are esoteric data structures that also match the standard requirements; they simply don't perform as well in the real world.

    The containers can, basically, do whatever they want so long as the implementation matches the requirements.

    However, in practice most implementations will inherit the mutated allocator by virtue of a proxy for the sake of simplicity. (Yes, that's actually one of the simpler ways.)

    So then, if we pretend to expand the template inline we might have something like the following code.

    Code:
    set<int> a;
    // ...
    set<int, less<int>, allocator<int>> a;
    // ...
    set<int, less<int>, allocator<int>>: private set_base<int, less<int>, allocator<int>> a;
    // ...
    set<int, less<int>, allocator<int>>: private set_base<int, less<int>, allocator<int>>: public allocator<int>::rebind<set_base<int, less<int>, allocator<int>::node_type>::type a;
    With such a mechanism we can see how the allocation works where facilities need to add a new node.

    Code:
    pair<iterator, bool> set<???>::insert(const value_type & f)
    {
    // ...
    set<???>::node_type * loc(this->allocate(1));
    this->construct(loc, f); // `loc' is now a constructed node type of `node_type' which is an unspecified structure or class
    // ...
    }
    Soma

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Ahh, that makes sense, thanks!

    The reference I was looking at (allocator - C++ Reference) completely ignores rebind...


    Thanks!

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    It's just as well. Many sources explain the concept incorrectly.

    I think it is "The C++ Standard Library" by Nicolai M. Josuttis that you will want to read.

    Soma

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    You're assuming that an allocator<Key> simply allocates Keys.

    allocator<T> defines a templated rebind type. allocator<T>::rebind<U> is a struct type that contains a typedef named other. allocator<T>::rebind<U>::other is effectively a typedef for a SomeAllocator<U> (which is either an allocator<U> or some user supplied myallocator<U>). This means that, if the set is given a allocator<Key>, it can get any other allocator<U> to provide it services - such as memory allocation and deallocation - via rebind<U>::other.

    Since the substitution happens at compile time (when templates are expanded) there should (depending on quality of compiler implementation) be no undue runtime overhead of an allocator<int> getting (say) an allocator<something_else> to provide it memory.

    I'm not sure specifically about set, but this rebinding is critical to the working of std::list (which is typically akin to a single linked list). std::list<T> receives an allocator<T>, but is able to get an allocator<some_node<int> > to allocate memory for each node. I assume set does something along the same lines.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Custom URI schemes
    By Epy in forum C# Programming
    Replies: 2
    Last Post: 08-10-2010, 01:23 PM
  2. Custom Title
    By hauzer in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 10-30-2008, 03:56 PM
  3. Differences allocators malloc-new
    By Leite33 in forum C++ Programming
    Replies: 1
    Last Post: 10-09-2006, 03:34 PM
  4. Custom UI
    By cfrost in forum Windows Programming
    Replies: 5
    Last Post: 08-20-2004, 12:52 PM
  5. Custom Scroll Bar
    By lyx in forum Windows Programming
    Replies: 4
    Last Post: 11-22-2003, 04:37 AM

Tags for this Thread