N3000 Problem replacing the allocator for node based containers using a sentinel
Bo Persson
work. Assuming a node based container using a sentinel node, how are
you supposed to re-establish the sentinel in an exception safe manner
after replacing the allocator?
I tried with this code:
_RedBlackTree& operator=(const _RedBlackTree& _Other)
{
if (this != &_Other)
{
clear();
if (__node_allocator_traits::
propagate_on_container_copy_assignment::value)
{
_DropSentinel();
_MyAllocator = _Other._MyAllocator;
_CreateSentinel();
}
insert(_Other.cbegin(), _Other.cend());
}
return *this;
}
Before replacing the allocator, I obviously must deallocate everything
through the old allocator, including the sentinel node.
Now, if _CreateSentinel() throws a bad_alloc because the new allocator
is fresh out of resources, I cannot re-establish my invariant that the
container always has a sentinel node! I'm toast!!
Then what??
Bo Persson
--
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@netlab.cs.rpi.edu]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Bo Persson
> Perhaps I need a How-to guide for this, but I just cannot get it to
> work. Assuming a node based container using a sentinel node, how are
> you supposed to re-establish the sentinel in an exception safe
> manner after replacing the allocator?
>
> I tried with this code:
>
> _RedBlackTree& operator=(const _RedBlackTree& _Other)
> {
> if (this != &_Other)
> {
> clear();
>
> if (__node_allocator_traits::
> propagate_on_container_copy_assignment::value)
> {
> _DropSentinel();
> _MyAllocator = _Other._MyAllocator;
> _CreateSentinel();
> }
>
> insert(_Other.cbegin(), _Other.cend());
> }
>
> return *this;
> }
>
>
> Before replacing the allocator, I obviously must deallocate
> everything through the old allocator, including the sentinel node.
>
> Now, if _CreateSentinel() throws a bad_alloc because the new
> allocator is fresh out of resources, I cannot re-establish my
> invariant that the container always has a sentinel node! I'm toast!!
>
> Then what??
>
Answering myself again (it was late yesterday :-)
This must be one place to use the copy-swap idiom:
First make a copy of the parameter and then, if that works, swap the
copy with the current object.
if (__node_allocator_traits::
propagate_on_container_copy_assignment::value)
{
_RedBlackTree _Tmp(_Other);
this->swap(_Tmp);
}
else
{
insert(_Other.cbegin(), _Other.cend());
}
Was that too hard? :-)
Kaz Kylheku
> Perhaps I need a How-to guide for this, but I just cannot get it to
> work. Assuming a node based container using a sentinel node, how are
> you supposed to re-establish the sentinel in an exception safe manner
> after replacing the allocator?
>
> I tried with this code:
>
> _RedBlackTree& operator=(const _RedBlackTree& _Other)
> {
> if (this != &_Other)
> {
> clear();
>
> if (__node_allocator_traits::
> propagate_on_container_copy_assignment::value)
> {
> _DropSentinel();
> _MyAllocator = _Other._MyAllocator;
> _CreateSentinel();
> }
>
> insert(_Other.cbegin(), _Other.cend());
> }
>
> return *this;
> }
>
>
> Before replacing the allocator, I obviously must deallocate everything
> through the old allocator, including the sentinel node.
Isn't the sentinel node embedded in the _RedBlackTree object itself?
If not, that's silly. Since the tree always needs a sentinel node,
there is no point in allocating it separately. Just make it a member.
class _RedBlackTree {
...
private:
_RedBlackNode _sentinel;
...
};
There is a 1:1 association between trees and sentinels; each tree
needs its own, for any hope of thread safety.
> Now, if _CreateSentinel() throws a bad_alloc because the new allocator
The functions _CreateSentinel() and _DropSentinel() shouldn't even exist;
this makes no sense.
The constructor of _RedBlackTree should initialize the sentinel node,
which should be correctly maintained thereafter by all of the
operations.
The clear() operation should result in an empty tree, with a sentinel
that points back to itself, ready to accept new insertions.
Bo Persson
Having a separate sentinel node makes it easier to swap the entire
tree to another container. Otherwise you might have to find and adjust
all pointers pointing back to the sentinel.
>
>> Now, if _CreateSentinel() throws a bad_alloc because the new
>> allocator
>
> The functions _CreateSentinel() and _DropSentinel() shouldn't even
> exist; this makes no sense.
True, that is my problem. :-)
However, when the container's allocator is replaced, all of its
allocated memory must first be released through the old allocator.
This is a new requirement that might have effects that require some
retuning of other container operations.
>
> The constructor of _RedBlackTree should initialize the sentinel
> node, which should be correctly maintained thereafter by all of the
> operations.
>
> The clear() operation should result in an empty tree, with a
> sentinel that points back to itself, ready to accept new insertions.
True, but if the sentinel is a separate object is has to go, before
replacing the allocator. Like I wrote elsewhere, I later recognized
that this can be solved by creating the new copy before destroying the
old one. The copy-swap idiom.
Bo Persson