Re: Sorting two arrays with one call to sort()?
on Thu Sep 27 2007, int19h-AT-gmail.com wrote:
On Sep 28, 2:19 am, John <weekender...@yahoo.com> wrote:
On Sep 27, 6:10 am, jtorjo2...@yahoo.com wrote:
Here is what you get with g++ 3.4.4,
I do not have VS...sorry. Please post portable code.
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h: In
function `const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&)
[with _Tp = double_iterator<int, float>::value_type]':
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2482:
instantiated from `void std::__introsort_loop(_RandomAccessIterator,
_RandomAccessIterator, _Size) [with _RandomAccessIterator =
double_iterator<int, float>, _Size = int]'
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2553:
instantiated from `void std::sort(_RandomAccessIterator,
_RandomAccessIterator) [with _RandomAccessIterator =
double_iterator<int, float>]'
x.cpp:108: instantiated from here
The reason why this didn't work (aside from a couple of const-
correctness errors, e.g. on value_type::operator<), and why other
similar approaches will fail as well, is that it is, unfortunately,
impossible to define such a random-access iterator. The problem is
that we have to return a wrapper in operator*() in this case
(to provide overloaded operator= and operator< for std::sort),
Yes, that's the proxy reference I was referring to.
and the requirement for forward iterators (and thus random-access
iterators) is that operator* for them returns a plain reference -
(C++03, [lib.forward.iterators]). In other words, the iterator
defined above, and any similar one, is not a RandomAccessIterator,
and therefore std::sort is not guaranteed to work with it.
Yes, that's the trouble I was referring to.
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);
}
.....or because there's no swap implementation in boost for tuples of
references (a likely possibility, and if so one that should arguably
be fixed).
Also, while it might be tempting to "fix" the problem by keeping an
instance of value_type inside the iterator, and changing operator* to
return a reference to that, it is still broken, since the reference
returned by operator* should not change afterwards, even if the
iterator is changed.
I don't think that's the real problem. The real problem is that
there's no operation one can use to write the values stored in the
iterator back into the arrays.
It would most likely work in this case, but by the letter of the
Standard it would still be broken.
True, but given the existence of vector<bool> I would have hoped most
standard library implementations could deal with this issue by now.
--
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! ]