Re: indirect / index sorting with the STL Organization: University of Bielefeld
On 2011-05-20 03:45, Kai-Uwe Bux wrote:
Joshua Lehrer wrote:
On May 18, 4:49 pm, Kai-Uwe Bux<jkherci...@gmx.net> wrote:
Joshua Lehrer wrote:
I was challenged to come up with a way to use existing STL algorithms
to sort one vector but given sorting precedence in a separate vector.
An additional constraint is that only O(1) constant external storage
may be used.
to be modified and the first should stay the same. The following does
sort _both_ vectors based upon the comparison from the first. It is
faking the reference that you need as the return type for operator*.
Kai-Uwe, your solution is the closest, and I went this route as well.
However, there is still a problem. Operator* must return a true
reference, you can not return a temporary object.
swap(*a,*b)
is the problem. swap takes two non-const references. If *a returns a
temporary, not a true reference, then it can't bind this temporary to
a non-const reference, and it fails to compile.
Note first, that sort() does not necessarily use swap() directly but may use
iter_swap(), which in turn is somewhat underspecified.
Just to emphasize this: It's even worse in C++03, because sort() may
*neither* call swap() *nor* iter_swap().
In particular C++03
does not rule out that iter_swap is implemented directly as:
template< typename Iter>
iter_swap( Iter a, Iter b ) {
typedef typename iterator_traits< Iter>::value_type value_type;
value_type dummy = *a;
*a = *b;
*b = dummy;
}
In this case, there would be no conceptual problem with non-const
references.
However, there is a defect report
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#187
and the proposed resolution would require iter_swap to rely on swap()
thereby necessitating honest references.
Yes, this problem has been fixed in C++0x. But this does not mean that
iter_swap requires "honest references": The new swappable requirements
and the typical usage of these requirements in the library do *not*
require that the arguments must be lvalues. The new requirements are:
"*a shall be swappable with (17.6.3.2) *b"
which means that it only requires the existence of an ADL-available swap
overload that can accept the combination of these values (either both
are rvalues or both are lvalues).
I ran into this problem as well trying to implement it myself:
I did not as my STL implementation aparrently does not fully implement the
proposed solution to 187. On my machine, the code I posted compiles cleanly
and yields the desired output.
The proposed solution does only require the usage of a swap function,
not necessarily std::swap.
I ran into trouble when I had to implement operator* on my pointer class
because I had no real object to return a reference to
This shouldn't be so hard, but I continue to claim that it is not
possible with std::sort.
I am not entirely convinced yet. But I do see the problem. From a practical
point of view, one could of course overload iter_swap() or swap()
appropriately, but as those are overloads as opposed to specializations, it
formally triggers UB.
If these swap functions are found by ADL and thus may come from a
namespace (including the global namespace) of a user-defined type, there
is no UB in C++0x. In fact, it is designed to enable ADL here.
HTH & Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]