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