Boost logo

Boost :

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>::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).


Boost list run by bdawes at, gregod at, cpdaniel at, john at