Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-26 10:51:22

Niels Dekker - mail address until 2008-12-31 wrote:
>> Howard Hinnant wrote:
>> swap1 time is 0.172796 seconds
>> swap2 time is 1.3e-05 seconds
> David Abrahams wrote:
>> Your program gives about the results I'd have expected for the case
>> you tested, but it doesn't address what I was concerned about.
> Howard's example shows that a swap overload for std::tr1::array
> effectively reduces the complexity of swapping a
> tr1::array<vector<int>,N> from O(M*N) to O(N), when the array has N
> vectors, each having size M. And it provides no-throw.

I know what it shows.

> Aren't those the issues you were concerned about?

No. swap for a given array<> is not guaranteed to be nothrow unless all
the elements have a nothrow swap. But I guess in a world where all
swaps are nothrow, this is a non-issue.

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.

> Any type that is both CopyConstructible and Assignable is Swappable, by
> definition.

Unless you define Swappable to mean "has an O(1) swap." or unless you
meant "by implementation" instead of "by definition" ;-)

> Within generic code, people typically use the well-known
> idiom to swap a pair of Swappable objects:
> // Allow argument-dependent lookup to find a custom swap.
> using std::swap;
> swap(lhs, rhs);
> As long as boost::swap hasn't come out of the sandbox, of course
> (hint)!


> Don't you think it /always/ makes sense to provide a custom
> swap overload for a Swappable type, as long as it outperforms the
> default std::swap, in one way or the other?

That's the whole question. I'm not 100% sure.

Dave Abrahams
BoostPro Computing

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