Boost logo

Boost :

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)? :-)


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

> 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

> Note that boost::array<T,N> /does/ have a swap function, even though it
> is documented to have no constant complexity.
> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at