[allocator.concept] smart pointer clarifications

[Phil Bouchard]

I am currently writting a smart pointer which is reasonnably stable and I
decided supporting allocators for completion because of its increase in
efficiency when the same pool used by containers is shared. I was told the
new standards are being finalized and I am hoping minor but important
changes could be applied before anything else.

To give a quick overview on the current status of this topic, you will find
below the latest text relating to allocator member functions (n2641). We
see over there there are no dictinction between the pointer type returned by
allocate() and the pointer type expected by deallocate() and destroy().
This is a big problem because this logic doesn't make sense anymore if smart
pointers are to be used. Smart pointers are owners of their objects and
aren't in no way going to give away external access to its object. We need
these functions to use
1) distinct pointer type from the one returned by allocate()
2) make the parameter (pointer) passed as a non-const reference

The latter is necessary to make changes to either the smart pointer itself
or the object pointed to in case raw pointer are used. We can see my
personnal implementation here and I would like to propose the following
function signatures:

template <typename T>
class shifted_allocator
{
public:
typedef shifted<T value_type;
typedef shifted_ptr<T pointer;
typedef shifted_ptr<const T const_pointer;

value_type * allocate(size_type s, const void * = 0);
void deallocate(pointer & p, size_type);
void construct(value_type * p, const T & x);
void destroy(pointer & p);
...
};

** Allocator member functions **
1)
pointer X::allocate(size_type n);
pointer X::allocate(size_type n, const_generic_pointer hint);

Effects: Memory is allocated for n objects of type value_type but the
objects are not constructed. [Footnote: It is intended that a.allocate be an
efficient means of allocating a single object of type T, even when sizeof(T)
is small. That is, there is no need for a container to maintain its own
"free list". - end footnote] The optional argument, p, may

Returns: A pointer to the allocated memory. [Note: If n == 0, the return
value is unspecified. If n 1, the means by which a program gains access to
the second and subsequent allocated objects is determined outside of the
Allocator concept. See RandomAccessAllocator, below, for one common
approach. - end note]

Throws: allocate may raise an appropriate exception.

Remark: The use of hint is unspecified, but intended as an aid to locality
if an implementation so desires. [ Note: In a container member function, the
address of an adjacent element is often a good choice to pass for the hint
argument. - end note ]

2)
void X::deallocate(pointer p, size_type n);

Preconditions: All n value_type objects in the area pointed to by p shall be
destroyed prior to this call. n shall match the value passed to allocate to
obtain this memory. [Note: p shall not be singular. - end note]

Throws: Does not throw exceptions.

3)
void X::destroy(pointer p);

Effects: Calls the destructor on the object at p but does not deallocate it.

Regards,
-Phil

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[mlimber]

On Aug 18, 7:28*pm, "Phil Bouchard" <[e-mail]:

I am currently writting a smart pointer which is reasonnably stable and I
decided supporting allocators for completion because of its increase in
efficiency when the same pool used by containers is shared. *I was toldthe
new standards are being finalized and I am hoping minor but important
changes could be applied before anything else.

To give a quick overview on the current status of this topic, you will find
below the latest text relating to allocator member functions (n2641). *We
see over there there are no dictinction between the pointer type returnedby
allocate() and the pointer type expected by deallocate() and destroy().
This is a big problem because this logic doesn't make sense anymore if smart
pointers are to be used. *Smart pointers are owners of their objects and
aren't in no way going to give away external access to its object. *We need
these functions to use
1) distinct pointer type from the one returned by allocate()
2) make the parameter (pointer) passed as a non-const reference

The latter is necessary to make changes to either the smart pointer itself
or the object pointed to in case raw pointer are used. *We can see my
personnal implementation here and I would like to propose the following
function signatures:

template <typename T>
* * class shifted_allocator
* * {
* * public:
* * * * typedef shifted<T* * * * * * *value_type;
* * * * typedef shifted_ptr<T* * * * *pointer;
* * * * typedef shifted_ptr<const T* *const_pointer;

* * * * value_type * allocate(size_type s, const void * = 0);
* * * * void deallocate(pointer & p, size_type);
* * * * void construct(value_type * p, const T & x);
* * * * void destroy(pointer & p);
* * * * ...
* * };

[snip]

Perhaps I'm missing something. Smart pointers generally take over
ownership AFTER allocation, e.g.:

tr1::shared_ptr<intspi1( new int(42) );
tr1::shared_ptr<intspi2( FactoryFunction() );

A shared_ptr's deleter can tell it how to do some special release
procedure, e.g.:

tr1::shared_ptr<FILEfile( fopen( "some.txt", "r" ), &fclose );

Why do allocators need to become aware of smart pointers?

Cheers! --M

[Phil Bouchard]

"mlimber" <ml*****@gmail.comwrote in message
news:e8**********************************@x35g2000 hsb.googlegroups.com...

[...]

Perhaps I'm missing something. Smart pointers generally take over
ownership AFTER allocation, e.g.:

tr1::shared_ptr<intspi1( new int(42) );
tr1::shared_ptr<intspi2( FactoryFunction() );

A shared_ptr's deleter can tell it how to do some special release
procedure, e.g.:

tr1::shared_ptr<FILEfile( fopen( "some.txt", "r" ), &fclose );

Why do allocators need to become aware of smart pointers?

Cheers! --M

Well the idea of having of defining an allocator is to centralized in one
class instanciation everything related to memory management. If the
allocator have to be explicitly shared between the container and the smart
pointer itself then the idea becomes pointless. The allocator should be
responsible for all types of deallocations, including smart pointers.
-Phil

[mlimber]

On Aug 20, 4:26*am, "Phil Bouchard" <[e-mail]:

"mlimber" <[e-mail] in message

news:e8**********************************@x35g2000 hsb.googlegroups.com...

[...]

Perhaps I'm missing something. Smart pointers generally take over
ownership AFTER allocation, e.g.:

*tr1::shared_ptr<intspi1( new int(42) );
*tr1::shared_ptr<intspi2( FactoryFunction() );

A shared_ptr's deleter can tell it how to do some special release
procedure, e.g.:

*tr1::shared_ptr<FILEfile( fopen( "some.txt", "r" ), &fclose );

Why do allocators need to become aware of smart pointers?

Well the idea of having of defining an allocator is to centralized in one
class instanciation everything related to memory management. *If the
allocator have to be explicitly shared between the container and the smart
pointer itself then the idea becomes pointless. *The allocator should be
responsible for all types of deallocations, including smart pointers.

I still don't get it. Let's say you're designing std::vector, which
has an allocator template parameter. It doesn't matter if the user-
defined class or a smart pointer (as long as it has value semantics).
Given this code:

class C { */...*/ };
// ...
std::vector<Cv1( 10 );
std::vector< std::tr1::shared_ptr<C v2( 10 );

Under the hood, each of the latter two lines will use vector's
(default) allocator to grab memory for the 10 instances of the
contained type and then placement-new to construct the instances in
that memory. (Note that all the shared_ptr's pointees are null at this
point.) Why does the allocator care if it's making a C or a
shared_ptr<C>?

Cheers! --M

[Phil Bouchard]

"mlimber" <ml*****@gmail.comwrote in message
news:b5**********************************@e53g2000 hsa.googlegroups.com...
On Aug 20, 4:26 am, "Phil Bouchard" <[e-mail]:

[...]

I still don't get it. Let's say you're designing std::vector, which
has an allocator template parameter. It doesn't matter if the user-
defined class or a smart pointer (as long as it has value semantics).
Given this code:

class C { */...*/ };
// ...
std::vector<Cv1( 10 );
std::vector< std::tr1::shared_ptr<C v2( 10 );

Under the hood, each of the latter two lines will use vector's
(default) allocator to grab memory for the 10 instances of the
contained type and then placement-new to construct the instances in
that memory. (Note that all the shared_ptr's pointees are null at this
point.) Why does the allocator care if it's making a C or a
shared_ptr<C>?

Cheers! --M

Indeed in that case it won't matter because the pools used to allocate nodes
from the container and to deallocate objects from the smart pointer are not
shared. Sometimes it is in our favor to share to same pool used by the
container and the smart pointer. For example shifted_ptr<uses this to
prevent cyclicism (still requires STL modifications).

Either we do it this way or we share the allocator across the container and
smart pointer so that the smart pointer uses deallocate(void *):

1)
std::vector<shifted_ptr<int>, shifted_allocator<shifted_ptr<int c1;

2)
std::vector<shifted_ptr<int, shifted_allocator<int,
shifted_allocator<shifted_ptr<int, shifted_allocator<int c2;

I don't even think option 2) is implementable.
-Phil

[Phil Bouchard]

"Phil Bouchard" <ph**@fornux.comwrote in message
news:g8**********@aioe.org...

[...]

The latter is necessary to make changes to either the smart pointer itself
or the object pointed to in case raw pointer are used. We can see my
personnal implementation here and I would like to propose the following
function signatures:

template <typename T>
class shifted_allocator
{
public:
typedef shifted<T value_type;
typedef shifted_ptr<T pointer;
typedef shifted_ptr<const T const_pointer;

value_type * allocate(size_type s, const void * = 0);
void deallocate(pointer & p, size_type);
void construct(value_type * p, const T & x);
void destroy(pointer & p);
...
};

[...]

Moreover it turns out this will become an even bigger problem if the new
rule of virtualizing allocator is accepted because the parameters will be
totaly different:

namespace std
{
class allocator_implementation
{
typedef void * pointer;

virtual void deallocate(pointer p, size_type) = 0;
...
};
}

template <typename T>
class shifted_allocator : std::allocator_implementation
{
public:
typedef shifted<T value_type;
typedef shifted_ptr<T pointer;
typedef shifted_ptr<const T const_pointer;

virtual void deallocate(pointer & p, size_type) // won't override
{
}
...
};

I think the idea of virtualizing the allocators should not be accepted
because it will be irreversible. Correct me if I'm wrong but I don't see
why we couldn't virtualize containers instead. Everybody thinks this means
slower performance but most of today's compilers are smart enough to bypass
the virtual tables. Let's consider the following:

template <typename T>
class list_base : public ...{ /* common operations */ ... };

template <typename T, typename Alloc>
class list : public list_base<T{ ... };
-Phil

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[mlimber]

On Aug 20, 12:57*pm, "Phil Bouchard" <[e-mail]:

"mlimber" <[e-mail] in message

news:b5**********************************@e53g2000 hsa.googlegroups.com...
On Aug 20, 4:26 am, "Phil Bouchard" <[e-mail]:

[...]

I still don't get it. Let's say you're designing std::vector, which
has an allocator template parameter. It doesn't matter if the user-
defined class or a smart pointer (as long as it has value semantics).
Given this code:

*class C { */...*/ };
*// ...
*std::vector<Cv1( 10 );
*std::vector< std::tr1::shared_ptr<C v2( 10 );

Under the hood, each of the latter two lines will use vector's
(default) allocator to grab memory for the 10 instances of the
contained type and then placement-new to construct the instances in
that memory. (Note that all the shared_ptr's pointees are null at this
point.) Why does the allocator care if it's making a C or a
shared_ptr<C>?

Cheers! --M

Indeed in that case it won't matter because the pools used to allocate nodes
from the container and to deallocate objects from the smart pointer are not
shared. *Sometimes it is in our favor to share to same pool used by the
container and the smart pointer. *For example shifted_ptr<uses this to
prevent cyclicism (still requires STL modifications).

Either we do it this way or we share the allocator across the container and
smart pointer so that the smart pointer uses deallocate(void *):

1)
std::vector<shifted_ptr<int>, shifted_allocator<shifted_ptr<int c1;

2)
std::vector<shifted_ptr<int, shifted_allocator<int,
shifted_allocator<shifted_ptr<int, shifted_allocator<int c2;

I don't even think option 2) is implementable.

I may just be dense, but I still don't see what you're getting at.
Can't you just use the deleter parameter to indicate special deletion?
Something like this (untested):

class C { /*...*/ };

template<class Alloc>
class MyDeleter
{
Alloc& m_alloc;

typedef typename Alloc::value_type T;

public:
MyDeleter( Alloc& alloc ) : m_alloc( alloc ) {}

// Might want a const T* version also
void operator()( T* const ptr )
{
m_alloc.destroy( ptr );
m_alloc.deallocate( ptr, sizeof(T) );
}
};

void Foo( MyAllocator<C>& alloc, const C& initVal )
{
typedef std::vector< std::tr1::shared_ptr<C VSPC;
VSPC v( 10 );
for( VSPC::iterator it=v.begin(); it != v.end(); ++it )
{
// Could hide these next lines in a factory function
C* const c = alloc.allocate( sizeof(C) );
alloc.construct( c, initVal );

it->reset( c, MyDeleter( m_alloc ) );
}
// ...
}

Now, when the vector "v" goes out of scope, the shared_ptrs use the
"alloc" object to deallocate their pointees.

Cheers! --M

[mlimber]

mlimber wrote:

template<class Alloc>
class MyDeleter
{
Alloc& m_alloc;

typedef typename Alloc::value_type T;

public:
MyDeleter( Alloc& alloc ) : m_alloc( alloc ) {}

// Might want a const T* version also
void operator()( T* const ptr )
{
m_alloc.destroy( ptr );
m_alloc.deallocate( ptr, sizeof(T) );
}
};

Oops. This won't work as written because of the reference member and
the default copy constructor, but that's easy to fix and you get the
idea.

Cheers! --M

[Phil Bouchard]

"mlimber" <ml*****@gmail.comwrote in message
news:2e**********************************@d77g2000 hsb.googlegroups.com...

On Aug 20, 12:57 pm, "Phil Bouchard" <[e-mail]:

[...]

Either we do it this way or we share the allocator across the container
and
smart pointer so that the smart pointer uses deallocate(void *):

1)
std::vector<shifted_ptr<int>, shifted_allocator<shifted_ptr<int c1;

2)
std::vector<shifted_ptr<int, shifted_allocator<int,
shifted_allocator<shifted_ptr<int, shifted_allocator<int c2;

I don't even think option 2) is implementable.

I may just be dense, but I still don't see what you're getting at.
Can't you just use the deleter parameter to indicate special deletion?
Something like this (untested):

class C { /*...*/ };

template<class Alloc>
class MyDeleter
{
Alloc& m_alloc;

typedef typename Alloc::value_type T;

public:
MyDeleter( Alloc& alloc ) : m_alloc( alloc ) {}

// Might want a const T* version also
void operator()( T* const ptr )
{
m_alloc.destroy( ptr );
m_alloc.deallocate( ptr, sizeof(T) );
}
};

void Foo( MyAllocator<C>& alloc, const C& initVal )
{
typedef std::vector< std::tr1::shared_ptr<C VSPC;
VSPC v( 10 );
for( VSPC::iterator it=v.begin(); it != v.end(); ++it )
{
// Could hide these next lines in a factory function
C* const c = alloc.allocate( sizeof(C) );
alloc.construct( c, initVal );

it->reset( c, MyDeleter( m_alloc ) );
}
// ...
}

Now, when the vector "v" goes out of scope, the shared_ptrs use the
"alloc" object to deallocate their pointees.

What you are suggesting is very similar to option 2) I was anteriorly
explaining. In my case I was using the allocator passed in as a template
parameter as a deleter so that there is no need to repeatedly call the
overloaded constructor shared_ptr(T *, D *). I can't imagine calling this
special constructor for each node pointer inside a container in a flexible
way. If I forget calling it for one pointer the compiler will not report
any compilation error.
-Phil

[mlimber]

On Aug 21, 8:40*am, "Phil Bouchard" <[e-mail]:

"mlimber" <[e-mail] in message

news:2e**********************************@d77g2000 hsb.googlegroups.com...

On Aug 20, 12:57 pm, "Phil Bouchard" <[e-mail]:

[...]

Either we do it this way or we share the allocator across the container
and
smart pointer so that the smart pointer uses deallocate(void *):

1)
std::vector<shifted_ptr<int>, shifted_allocator<shifted_ptr<int c1;

2)
std::vector<shifted_ptr<int, shifted_allocator<int,
shifted_allocator<shifted_ptr<int, shifted_allocator<int c2;

I don't even think option 2) is implementable.

I may just be dense, but I still don't see what you're getting at.
Can't you just use the deleter parameter to indicate special deletion?
Something like this (untested):

* class C { /*...*/ };

* template<class Alloc>
* class MyDeleter
* {
* * Alloc& m_alloc;

* * typedef typename Alloc::value_type T;

* public:
* * MyDeleter( Alloc& alloc ) : m_alloc( alloc ) {}

* * // Might want a const T* version also
* * void operator()( T* const ptr )
* * {
* * * m_alloc.destroy( ptr );
* * * m_alloc.deallocate( ptr, sizeof(T) );
* * }
* };

* void Foo( MyAllocator<C>& alloc, const C& initVal )
* {
* * typedef std::vector< std::tr1::shared_ptr<C VSPC;
* * VSPC v( 10 );
* * for( VSPC::iterator it=v.begin(); it != v.end(); ++it )
* * {
* * * // Could hide these next lines in a factory function
* * * C* const c = alloc.allocate( sizeof(C) );
* * * alloc.construct( c, initVal );

* * * it->reset( c, MyDeleter( m_alloc ) );
* * }
* * // ...
* }

Now, when the vector "v" goes out of scope, the shared_ptrs use the
"alloc" object to deallocate their pointees.

What you are suggesting is very similar to option 2) I was anteriorly
explaining. *In my case I was using the allocator passed in as a template
parameter as a deleter so that there is no need to repeatedly call the
overloaded constructor shared_ptr(T *, D *). *I can't imagine calling this
special constructor for each node pointer inside a container in a flexible
way. *If I forget calling it for one pointer the compiler will not report
any compilation error.

You said your option 2 was not implementable (perhaps it isn't; my
attempt was a little different). Have I presented a working
implementation supported by the standard and the approved extensions
in TR1 that accomplishes your goal of not having a smart pointer
expose itself for the sake of custom allocators? If so, it seems to me
that no change in the standard libraries is necessary, and authors of
smart pointers just need to model their own smart pointer design on
the standard one (cf. Scott Meyers's explanation of custom deleters:
http://www.artima.com/cppsource/top_..._moments.html).

Moreover, use of custom allocators is rather rare in my experience,
but those who need them will need to be diligent in their use. Calling
an alternate constructor/reset function doesn't seem like a heavy
burden for that small number of advanced users, particularly when it
is combined with RAII techniques for proper destruction.

Compare also the discussion of memory pools in the FAQs:

http://www.parashift.com/c++-faq-lit...html#faq-11.14

Cheers! --M

[Phil Bouchard]

"Phil Bouchard" <ph**@fornux.comwrote in message
news:g8**********@aioe.org...

[...]

template <typename T>
class list_base : public ...{ /* common operations */ ... };

template <typename T, typename Alloc>
class list : public list_base<T{ ... };

Where:
template <typename T>
virtual allocator_type list_base<T>::get_allocator() const = 0;

And, for example:
template <typename T, typename Alloc>
virtual allocator_type list<T, Alloc>::get_allocator() const
{
return allocator_type(*static_cast<const
_Node_Alloc_type*>(&this->_M_impl));
}
-Phil

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Phil Bouchard]

"mlimber" <ml*****@gmail.comwrote in message
news:57**********************************@l64g2000 hse.googlegroups.com...

any compilation error.

You said your option 2 was not implementable (perhaps it isn't; my
attempt was a little different). Have I presented a working
implementation supported by the standard and the approved extensions
in TR1 that accomplishes your goal of not having a smart pointer
expose itself for the sake of custom allocators? If so, it seems to me
that no change in the standard libraries is necessary, and authors of
smart pointers just need to model their own smart pointer design on
the standard one (cf. Scott Meyers's explanation of custom deleters:
http://www.artima.com/cppsource/top_..._moments.html).

No changes are required, I just want to make sure allocator do not become
virtual! I think there was a paper on this but I haven't followed up latest
clarifications.

Moreover, use of custom allocators is rather rare in my experience,
but those who need them will need to be diligent in their use. Calling
an alternate constructor/reset function doesn't seem like a heavy
burden for that small number of advanced users, particularly when it
is combined with RAII techniques for proper destruction.

Compare also the discussion of memory pools in the FAQs:

http://www.parashift.com/c++-faq-lit...html#faq-11.14

I will read those later... ;)
-Phil

[Phil Bouchard]

"Phil Bouchard" <ph**@fornux.comwrote in message
news:g8**********@aioe.org...

[...]

Where:
template <typename T>
virtual allocator_type list_base<T>::get_allocator() const = 0;

And, for example:
template <typename T, typename Alloc>
virtual allocator_type list<T, Alloc>::get_allocator() const
{
return allocator_type(*static_cast<const
_Node_Alloc_type*>(&this->_M_impl));
}

Sorry here I meant protected functions should be virtual, not
get_allocator():

template <typename T>
class list_base : public ...
{
virtual _List_node<_Tp>* _M_get_node() = 0;
virtual void _M_put_node(_List_node<_Tp>* __p) = 0;
};

template <typename T, typename Alloc>
class list : public list_base<T>
{
protected:
_List_impl _M_impl;

virtual _List_node<_Tp>* _M_get_node()
{
return _M_impl._Node_Alloc_type::allocate(1);
}

virtual void _M_put_node(_List_node<_Tp>* __p)
{
_M_impl._Node_Alloc_type::deallocate(__p, 1);
}

public:
_Alloc get_allocator() const
{
return _Alloc(*static_cast<const
_Node_Alloc_type*>(&this->_M_impl));
}

...
};
-Phil

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Phil Bouchard]

"Phil Bouchard" <ph**@fornux.comwrote in message
news:g8**********@aioe.org...

[...]

No changes are required, I just want to make sure allocator do not become
virtual! I think there was a paper on this but I haven't followed up
latest clarifications.

[...]

Yeah that was n2387:
http://www.open-std.org/jtc1/sc22/wg...2007/n2387.pdf

This one needs to be canceled.
-Phil