Re: Sorting two arrays with one call to sort()?
on Mon Oct 15 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:
This formulation of iter_swap unfortunately (and needlessly) forces an
O(N) pessimization upon the client.
Consider a random access traversal iterator which references vector<int>
but uses a proxy reference to the vector as the return from operator*():
MyProxyIterator<std::vector<int>> begin, end;
...
Now consider sorting:
std::sort(begin, end);
With the above iter_swap everything compiles, but you have an O(N)
throw-ing swap each time sort calls iter_swap.
.....which is only a pessimization if the proxy author happened to
define a swap for the proxies, as I suggested later in my post.
Nothing in C++03 suggests that defining a swap for proxies will be
useful with the standard algorithms; it's definitely a good idea for
C++0x, since we codified the use of swap via ADL.
If instead iter_swap does nothing but swap(*a, *b), then one gets a
compile time error (as reported). The fix should not be to fix
iter_swap in the standard. The correct fix is to overload swap in the
proxy's namespace:
template <class T>
void
swap(MyProxyRef<T> a, MyProxyRef<T> b)
{
using std::swap;
swap(*a.ptr_, *b.ptr_); // or however MyProxyRef references T
}
Yes, and I was trying to make the point that we probably ought to do
that in C++0x and Boost for tuples of references (and proxies). That
could be accomplished very simply by defining swap on tuples to do a
member-by-member swap of the elements, and it would fix the issue with
zip_iterator.
I don't see a swap for tuple in Boost or in the draft; I think that's
a serious oversight on our part.
The user's overloaded MyProxyRef swap now forwards to the appropriate
swap for the referenced type (vector in our example) which subsequently
performs an O(1) no-throw operation.
Now consider what happens if we have both swap(MyProxyRef<T> a,
MyProxyRef<T> b), and the proposed "smart" iter_swap which detects
references: The swap(MyProxyRef<T> a, MyProxyRef<T> b) would be
completely (and silently) ignored!
Yes, I know. We can actually detect an overloaded swap and only swap
manually when such a swap is missing, but that's a lot more
complicated and I didn't really want to show all the code. Anyone who
wants the gory details can see them at
http://svn.boost.org/trac/boost/browser/trunk/boost/detail/is_incrementable.hpp,
which uses the same technique to detect overloaded increment operators.
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]