Allocator rebind from within template container class

[metamorphosis]

I've been working on a vector-like container class without pointer and iterator invalidation, and without some of the performance problems of vectors, called a colony.

The issue I'm having is using rebind within the template class.
I can run some of the examples I find on the net, but within the template, if I try something like this:

"
template <class the_type, class the_allocator = std::allocator<the_type> > class colony
{

...

the_allocator allocator;

...

group *first_group = the_allocator::rebind<group>::other(allocator.allocate(1, 0));
"

I of course get "expected primary-expression before '>' token", "::other has not been declared", etcetera.

Basically I have no idea what I'm doing.
I'm getting around it presently by using <char> in the std::allocator declaration and then reinterpret_cast on all allocations, but that's not going to work once I try to use other allocators.

Can anyone show me how to do this?

Thanks in advance.

[LB]

Have you tried looking at how standard library implementations do it?

metamorphosis wrote:

without some of the performance problems of vectors

If you're going to make such an outrageous claim, at least back it up with some links.

[JLBorges]

#include <iostream>
#include <memory>

template < typename T, typename ALLOCATOR = std::allocator<T> > struct colony
{
    struct group { group( int, double ) {} /* .. */ };

    explicit colony( const ALLOCATOR& a = ALLOCATOR() ) : the_allocator(a)
    {
        // type of rebound allocator
        using rebound_alloc_type = typename std::allocator_traits<ALLOCATOR>::template rebind_alloc<group> ;

        // create an object of type rebound allocator
        rebound_alloc_type rebound_allocator(the_allocator) ;

        // use the allocator object
        group* first_group = std::allocator_traits<rebound_alloc_type>::allocate( rebound_allocator, 1 ) ;
        std::allocator_traits<rebound_alloc_type>::construct( rebound_allocator, first_group, 12, 34.56 ) ;
        std::cout << "group* first_group == " << first_group << '\n' ;
        // etc.

        // ...
    }

    // ...

    private:
        ALLOCATOR the_allocator ;
        group* ptr = nullptr ;
};

int main()
{
    colony<int> c ;
}

http://coliru.stacked-crooked.com/a/db2ed65eae646fd8

[metamorphosis]

Thanks JLBorges, can you provide an example that meets C++0x requirements?
I am trying to have this work in both C++0x and C++11, for the compilers which don't properly support C++11 yet ie most of them.

LB I haven't published the link because it's not finished yet. There's no need to be so abrasive and to perform one-upmanship.

[LB]

Most compiler support C++11 fully and most if not all of C++14. Only Microsoft has partial support for C++11 and C++14, but everything in JLBorges' post should be fine (I haven't tested).

[metamorphosis]

JB- if you're not going to be helpful, please stop posting.

[JLBorges]

> for the compilers which don't properly support C++11 yet

If type aliases are not supported, replace the alias declaration on line 11 with a typedef:

// using rebound_alloc_type = typename std::allocator_traits<ALLOCATOR>::template rebind_alloc<group> ;
typedef typename std::allocator_traits<ALLOCATOR>::template rebind_alloc<group> rebound_alloc_type ;

If variadic templates are not supported, replace the in situ construction on line 18 with copy construction:

//std::allocator_traits<rebound_alloc_type>::construct( rebound_allocator, first_group, 12, 34.56 ) ;
std::allocator_traits<rebound_alloc_type>::construct( rebound_allocator, first_group, group( 12, 34.56) ) ;

If the implementation does not support std::allocator_traits<>, the allocators would need to be C++98 compatible allocators. The allocator must implement the complete interface of std::allocator<>, must be stateless, (instances of an allocator type must be interchangeable, instances must compare equal, and any allocator instance can deallocate memory allocated by any other instance of the same allocator type).

C++98:

#include <iostream>
#include <memory>

template < typename T, typename ALLOCATOR = std::allocator<T> > struct colony
{
    struct group { group( int, double ) {} /* .. */ };

    explicit colony( const ALLOCATOR& a = ALLOCATOR() ) : the_allocator(a), ptr(0)
    {
        // type of rebound allocator
        // using rebound_alloc_type = typename std::allocator_traits<ALLOCATOR>::template rebind_alloc<group> ;
        typedef typename ALLOCATOR::template rebind<group>::other rebound_alloc_type ;

        // create an object of type rebound allocator
        rebound_alloc_type rebound_allocator ;

        // use the allocator object
        group* first_group = rebound_allocator.allocate(1) ;
        rebound_allocator.construct( first_group, group( 12, 34.56) ) ;
        std::cout << "group* first_group == " << first_group << '\n' ;
        // etc.

        // ...
    }

    // ...

    private:
        ALLOCATOR the_allocator ;
        group* ptr ; // = nullptr ;
};

int main()
{
    colony<int> c ;
}

http://coliru.stacked-crooked.com/a/3fccd3d4463fc96f

[metamorphosis]

Thank you JLBorges,
I actually figured this out about 5 minutes ago, but thank you regardless.

An alternative for when variadic templates are not supported is to use placement new instead of construct, which AFAIK removes the temporary copy construction and instantiates directly:

new (first_group) group(12, 34.56);

You can also skip the typedef altogether and just declare the rebound allocator directly:

typename ALLOCATOR::template rebind<group>::other rebound_allocator;

The code then becomes:

#include <iostream>
#include <memory>

template < typename T, typename ALLOCATOR = std::allocator<T> > struct colony
{
    struct group { group( int, double ) {} /* .. */ };

    explicit colony( const ALLOCATOR& a = ALLOCATOR() ) : the_allocator(a)
    {
	typename ALLOCATOR::template rebind<group>::other rebound_allocator;

        // use the allocator object
        group* first_group = rebound_allocator.allocate(1, 0) ;
        new (first_group) group(12, 34.56);

        std::cout << "group* first_group == " << first_group << '\n' ;
        // etc.

        // ...
    }

    // ...

private:
	ALLOCATOR the_allocator ;
	group* ptr;
};

int main()
{
    colony<int> c ;
}

Cheers once again for helping me to understand all this.
m@

[JLBorges]

> An alternative for when variadic templates are not supported is to use placement new instead of construct,
> which AFAIK removes the temporary copy construction and instantiates directly:
> new (first_group) group(12, 34.56);

This is not a very good idea; this makes a blanket assumption about how and where the allocator allocates storage.

Allocators were introduced to the standard library in order to allow for allocation strategies other than just heap data allocated by new, and for alternative pointer types.
http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html

The only situation where we would need construction other than copy/move construction is for the emplace family of functions ( for instance emplace_back(); http://en.cppreference.com/w/cpp/container/vector/emplace_back ).
An implementation that does not support variadic templates would not support the emplace family of functions; and only the copy/move constructor would be needed.

[metamorphosis]

Hi JLBorges,
Regards using placement new after allocator.allocate, I'm not sure what you're meaning - do you mean that the memory that the allocator allocates may be fragmented in a way that prevents new from working with first_group?
In that case, most pointer arithmetic etc wouldn't work.

Most allocators use placement new under the hood for .construct anyway, so which is the scenario where this might cause issues?

Secondly, the main reason for me using placement new instead of construct was the necessity for temporary copy construction if using .construct with the copy constructor (assuming pre-C++11 semantics).
In other words, it prevents performance loss in the same way that emplace does, by avoiding unnecessary construction and copying.
This isn't for the stored type, this's for internal structural objects, which in this case are called groups.

Thanks,
Matt

[JLBorges]

> In that case, most pointer arithmetic etc wouldn't work.

We can be certain that the pointer type declared by the allocator would have the precise semantics of a pointer. But we can't assume that it would actually be a raw pointer.
See: http://www.cplusplus.com/forum/general/127466/#msg690093

[metamorphosis]

Thanks Jlborges, that makes sense, is this a common thing, that non-standard pointer types are used for allocators?

Also, is there any way, for internal structural objects in a container (as opposed to the objects being contained), that construction of those objects can take place without generating temporary copies, if we're using .construct and pre-C++11 semantics? This is merely a performance concern.
Thanks,
Matt

[JLBorges]

> is this a common thing, that non-standard pointer types are used for allocators?

Most of the time, the allocator would be std::allocator<> and its 'pointer' would be a raw pointer.
When user-defined allocators are used, it is not unusual for the allocator's pointer to be a smart pointer.
If we are writing a generic component which is allocator aware, we need to also cater to the possibility that the allocator's 'pointer' may not be a raw pointer.


> construction of those objects can take place without generating temporary copies,
> if we're using .construct and pre-C++11 semantics? This is merely a performance concern.

C++, from its inception has always had the as-if rule http://en.cppreference.com/w/cpp/language/as_if . If the implementation of the allocator's allocate function is visible to the compiler (the usual case) and copy construction of the object has no observable side effect, most implementations would optimise away the creation and then copying of the temporary object.

For instance, look at the code generated for 'foo' by clang++ and g++ in C++98 mode:

#include <new>

struct A { A( int a, int b ) : aval(a), bval(b) {} int aval ; int bval ; };

A* construct( void* here, const A& v ) { return new(here) A(v) ; }

A* foo( char* buffer, int a, int b )
{
    A temp( a, b ) ;
    A* p = buffer ? construct( buffer, temp ) : 0 ;
    return p ; 
}

http://coliru.stacked-crooked.com/a/2507eff0a909ed14

[metamorphosis]

Turns out that doesn't actually work - copy elision doesn't happen for the temporary copy construct in allocator.construct - regardless of optimisation levels. Tried on 3 compilers (GCC, Clang, MSVC++2010). Turns out you have to hack around it using pseudo-constructors and pseudo-copy-constructors, otherwise you get memory hits and fragmentation (from the double-ups of allocation with the first allocated block removed immediately afterwards) and possible memory limits reached (if your classes are storing something large, as mine are). But that's fine (so long as your specific class doesn't need a real copy constructor for other purposes, which this particular one does not). The C++11 code is pretty straightforward, and the minor hack in C++0x has negligible effect once you've moved all of the major allocation from the pseudoconstructor to the (pseudo) copy constructor.
For others reading in future, this becomes something equivalent to (though my code is much more diverse):

// group class
#if __cplusplus >= 201103L // ie. if this compiler supports c++11
	group(unsigned int size): group_size(size)
	{
		// Allocate elements according to size
	}

	// Note: in my case, a copy constructor isn't needed for C++11, variadic parameter .construct used by the group allocator and this would be the only place a copy constructor would be used

	~group()
	{
			// Deallocate elements according to size
	}

#else // ie. pre-C++11
	group(unsigned int size): elements(NULL), group_size(size)
	{}

	group(const group &source): group_size(source.group_size)
	{
		// Allocate elements according to size
	}

	~group()
	{
		if (elements != NULL)
			// Deallocate elements according to size
	}
#endif 

[metamorphosis]

Just wanted to say thanks for your help - allocators fully supported now.
Strangely, not much performance impact - in fact, more performance improvement from ability to give memory locale hints.
Cheers-