Re: [boost] [utility/swap] Okay to add array support to Boost.Swap(sandbox/swap)?

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-29 10:29:07

Matt Calabrese wrote:

> I think the problem here is that you are talking about a swap operation
> being a strictly O(1) operation and therefore there shouldn't be an array
> swap because it would have to be O(n), but the actual underlying problem is
> that in the context of a generic swap, at least in the sense of std::swap,
> there simply _is_no_ "n" to even be talking about in a meaningful sense.
> When working with the STL, we get into the habit of assuming that "n" is
> always the size of a range we are dealing with and the reason we can do that
> is because those algorithms are required to be working over a range. In that
> context, "n" is the size of the range. Again, we are able to do this because
> being passed a range is a requirement of these algorithms and a range must
> always have a size.
> 
> However, in the context of std::swap, this is not the case. std::swap has no
> requirement that what you pass is some type of container or range. As Neils
> pointed out earlier:
> 
> "For a particular template instantiation of boost::swap, for a particular
> type of arrays, the number of element swaps would be constant.  Doesn't that
> make it O(1)?"
> 
> What he is saying is perfectly fine because "n" was never appropriately
> defined before it was decided that swap must be an O(1) operation as opposed
> to an O(n) operation. So in the general sense, how do you define "n" here?

It's proportional to the memory footprint of the data values that, after
the swap is complete, must to be accessible as part of the opposite
argument from the one from which they were accessible befpre the swap.
You might look for swap in Stepanov's March 1995 Dr. Dobb's interview if
that helps.