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

From: Matt Calabrese (rivorus_at_[hidden])
Date: 2008-06-26 18:28:07

On Thu, Jun 26, 2008 at 10:51 AM, David Abrahams <dave_at_[hidden]> wrote:
>
> But the efficiency is a different issue.  It's like the same reason we
> don't provide random access for list iterators: operator++ on an
> iterator is supposed to be fundamentally O(1) (notwithstanding
> filter_iterator -- how do you measure /that/?!)
>
> I am inclined to agree that a fast swap for array is useful and thus
> should be provided, but I still have a nagging doubt about whether it's
> "the right thing to do."  Maybe I've been brainwashed by a certain
> disciple of Alex Stepanov's, because nobody else seems to share that
> doubt... so feel free to ignore me if you're unconvinced.

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?
Remember that std::swap may be used with types other than containers (ints,
floats, pods, etc.). If you want to state the complexity of a general
algorithm, then any variables you refer to (i.e. "n") have to be expressible
in terms of the concept requirements of that algorithm. In the context of
most STL algorithms we use "n" to mean the size of the range we are
operating over, but we can only do that because it is required that a range
is passed to those algorithms. With respect to the general concept of a
swap, there is no such requirement and so it doesn't make sense to define
"n" in that manner.

A quick example -- what is the complexity of the swap operation here:
_________________________________________________

struct complex_type { /**/ };

struct a { complex_type b, c, d; } left, right;

swap( left, right );

_________________________________________________

You would probably say O(1), but then what is the complexity of the same
swap done here (assume the above definition of a):

_________________________________________________

BOOST_FUSION_ADAPT_STRUCT( a,
(complex_type,b)(complex_type,c)(complex_type,d) )

swap( left, right );

_________________________________________________

Did the complexity of the general swap operation now change to O(n) simply
because we adapted the struct to be a fusion sequence of size n? No. The
fact that it is a sequence is meaningless with respect to the general idea
of the swap operation. It's true that because we are using a fusion sequence
we can now say "the swap operation in this context is O(n) where n is equal
to the size of the fusion sequence being passed," but that doesn't mean that
it's an O(n) swap in the general sense of the swap operation because "n"
simply has no meaning in the general sense of std::swap.

Because of this, I see absolutely no reason why std::swap should not be
defined for arrays and boost::array, at least with respect to complexity.

-- 
-Matt Calabrese