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

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-23 15:54:30

Niels Dekker - mail address until 2008-12-31 wrote:
>>> Would it be okay to you if we would add support for array types to
>>> the Boost.Swap utility that is located in the sandbox?
> 
>> Whether or not this is a good idea depends on whether you think swap
>> is fundamentally an O(1) and/or nonthrowing operation.
> 
>>> The array support I would like to add to boost::swap is
>>> non-throwing, as long as the array element type has a
>>> non-throwing swap.
> 
> David Abrahams wrote:
>> Sure, but it is not O(1) no matter what the element type does.
> 
> 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)?  :-)

Sneaky.

I don't think so, but I can see how it could be considered a matter of
opinion.

> Maybe I just don't understand the definition of O(1) well enough. Do you
> consider the following swap_pod<T> function O(1)?  Or is it O(n), having
> n = sizeof(T)?  It would support swapping arrays, as long as their
> element type is POD.
> 
>  template<typename T>
>  void swap_pod(T & lhs, T & rhs)
>  {
>    unsigned char tmp[sizeof(T)];
>    std::memcpy(tmp, lhs, sizeof(T));
>    std::memcpy(lhs, rhs, sizeof(T));
>    std::memcpy(rhs, tmp, sizeof(T));
>  }

I consider the above O(N)

> (BTW, my proposal wasn't to use std::memcpy, but instead, to do the swap
> elementwise, using the custom swap function of the element type,
> whenever found by ADL.)
> 
> So do you think that adding array support to boost::swap is /not/ a good
> idea?

I haven't formed an opinion yet, but the fact remains that swapping a
boost::array would have very different efficiency characteristics from
swapping the analogous std::vector, so we ought to think it through
carefully.

> Note that boost::array<T,N> /does/ have a swap function, even though it
> is documented to have no constant complexity.
> www.boost.org/doc/libs/1_35_0/doc/html/array.html  Do you think that
> boost::array<T,N> should not have one?

It's basically the same question, so my answer is the same.

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