Re: [boost] implementation of moveconstructor

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2007-04-24 14:22:12

On Apr 24, 2007, at 1:45 PM, Ion Gaztañaga wrote:

> Howard Hinnant wrote:
>>
>> [snip]
>>
>> I now prefer the semantics of clear(); swap();.  This means that move
>> assignment is O(N) instead of O(1).  Ok Ion, take a deep breath and
>> stay with me for just a minute longer. :-)
>>
>> [snip]
>>
>> First, for vector<type with trivial destructor>, clear() is O(1) in
>> practice (or it should be).  And clear() does not dump capacity, so
>> the capacity gets reused via the swap.  So we only have to worry  
>> about
>> vector<type with non-trivial destructor>.
>
> Right now I'm thinking about std::list and (unordered_)map/set.  
> clear()
> does not sound very lightweight... ¿collateral damage? ;-)

I think list is manageable, but I haven't figured out the standardeeze  
for it yet.  I'm thinking something like (untested):

template <class T, class A>
list<T,A>&
list<T,A>::operator=(list&& x)
{
     iterator i = begin();
     iterator j = x.begin();
     size_type nodes_to_splice = x.size();
     for (; i != end() && j != x.end(); ++i, ++j, --nodes_to_splice)
        *i = std::move(*j);
     if (i != end())
         erase(i, end());
     else if (j != end())
         splice(x, j, end(), nodes_to_splice);
     return *this;
}

I.e. this is O(this->size()).  It recycles existing nodes, takes  
advantage of the element's move assignment (if it exists), and is O(1)  
if this->size() == 0 (and yes, I'm assuming size() is O(1) and I don't  
even want to get into that side topic ;-)).  The above needs to be  
fixed up to support unequal allocators, most likely reverting to  
clear() + swap() in that case.  Also know that Swappable is going to  
be optional for C++0X allocators.  If the allocator is swappable, you  
can swap it with swap.  If the allocator isn't swappable (and is  
unequal), one will have to revert to creating nodes in the target.

For (unordered_)map/set recycling nodes may be more trouble than it is  
worth.  And the only saving grace is that most of the time one move  
assigns, the target is already empty, and so the clear() is dirt cheap  
(which also helps in the list case).

The basic philosophy is that for:

     a = std::move(b);

For every element in "a" before the move, either the element is move  
assigned or destructed within the move assignment (thus achieving the  
deterministic resource management you mentioned in your other post).

-Howard