Re: Sorting two arrays with one call to sort()?
In article <87wstos2yl.fsf@grogan.peloton>,
David Abrahams <dave@boost-consulting.com> wrote:
This is precisely what happens with g++ - it implements std::sort in
terms of std::iter_swap, and that in terms of std::swap. The result
is that std::swap expects value_type&, and operator* on our iterator
returns an instance value_type by value, so we end up trying to bind
a temporary to a non- const reference. This is a known problem (see
http://gcc.gnu.org/ml/libstdc++/2005-03/msg00148.html, for example),
and std::vector<bool> iterators have similar problems for the same
reason.
Gnu's libstdc++ is designed to work with proxy iterators, at least in
some cases. If it isn't handling this case correctly it's because
iter_swap doesn't detect and handle proxy references correctly:
template <class It1, class It2>
void iter_swap(It1 p, It2 q)
{
iter_swap_impl(p, q, is_reference<It1>(), is_reference<It2>());
}
template <class It1, class It2>
void iter_swap_impl(p, q, ...)
{
typename iterator_traits<It1>::value_type x;
x = *p;
typename iterator_traits<It2>::value_type const& z = *q;
*p = z;
*q = x;
}
template <class It1, class It2>
void iter_swap_impl(p, q, true_type, true_type)
{
swap(*p,*q);
}
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.
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
}
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! That is, the overly helpful
iter_swap not only silently allows an overly expensive swap, it actively
prevents us from optimization even if we've properly prepared our proxy
iterator/reference.
-Howard
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]