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

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-04 17:56:26

on Sun Jun 29 2008, David Abrahams <dave-AT-boostpro.com> wrote:

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

Oh, and see http://www.stepanovpapers.com/DeSt98.pdf

Cheers,

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com