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