Re: Sorting two arrays with one call to sort()?
Tom arken
the quoted article by "x...@gmail.com" doesn't appear to have been posted
in clc++m, although the inner quoted article by John was. Note 2: Tom
arken has the same e-mail address as John, the original poster. -mod }
I think all the comp.lang.c++.moderated replies
were BS! I wasted time on each one of them and it was
a total waste of time...! None of those suggestions
work...the zip iterator was not designed to do what I
want to do...(well I'm glad I learnt about its useless
existence for my problem) and the other solution is
not that trivial...as it looks...beware...
your suggestion doesnt work either :) Try them
urself and you will find out why...its a waste of
time to overload those operators!
I think I found a solution, but its way more
complicated than I thought it would be...so I guess
I'll let all the gurus in c++.moderated think about
it...I know others have posted solutions elsewhere to
this problem...but I wish there was a clean way to
solve the problem...a nice,clean, short answer...
If this email ever gets posted to moderated,
please do not post any pseudo-code solutions to this
problem...And make sure you can sort two
vectors/arrays with your code before you post. (If
you need pseudo-code to sort two arrays in
code...well...shall we say, keep it to yourself...!)
Thanks.
> x...@gmail.com wrote:
> On Sep 23, 11:38 am, John wrote:
>
> > Here is as far as I got, it still doesnt work :(
> ...
> > template < typename tA, typename tB >
> > struct double_iterator {
> > tA* a;
> > tB* b;
> > size_t i;
> >
> > struct ref {
> > tA& p; tB& q;
> > ref(tA& p, tB& q) : p(p), q(q) {};
> > void operator=(ref y){
> > p= y.p; q = y.q;
> > };
> > void operator<(ref y){
> > return p < y.p;
> > };
> > };
> >
> > ref operator*(){ return ref(a[i],b[i]); }
> > double_iterator(tA* _a, tB* _b, size_t _i){
> > a = _a;
> > b = _b;
> > i = _i;
> > };
> >
> > };
>
> 1. double_iterator::ref::operator< should return
> bool, not void.
>
> 2. std::sort requires the iterators to be
> random-access, and your
> double_iterator is not an iterator at all; you need
> to define operator+
> +, operator-- (both prefix and postfix versions),
> operator==,
> operator<, operator+, operator-, operator+=,
> operator-=, operator[],
> and operator* for it to be a random-access iterator.
> All these are
> easily implemented by delegation to both underlying
> pointers.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
jtorj...@yahoo.com
> were BS! I wasted time on each one of them and it was
> a total waste of time...! None of those suggestions
> work...the zip iterator was not designed to do what I
> want to do...(well I'm glad I learnt about its useless
> existence for my problem) and the other solution is
> not that trivial...as it looks...beware...
I compiled and run this using VS2003:
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
const int N = 10;
template < typename tA, typename tB >
struct double_iterator {
typedef double_iterator<tA,tB> self;
tA* a;
tB* b;
int idx;
double_iterator(tA* _a, tB* _b, int idx = 0) : idx(idx) {
a = _a ;
b = _b ;
};
struct value_type {
tA a; tB b;
tA *pa; tB *pb;
value_type(tA *pa, tB *pb) : pa(pa), pb(pb), a(*pa),
b(*pb) {};
void operator=(value_type other){
*pa = other.a; *pb = other.b;
};
bool operator<(value_type other){
return a < other.a ;
};
};
typedef std::random_access_iterator_tag iterator_category;
typedef int difference_type;
typedef int distance_type;
typedef value_type& reference;
typedef value_type* pointer;
value_type operator*(){ return value_type(a+idx,b+idx); }
bool operator<(const self & other) const {
assert( a == other.a && b == other.b );
return idx < other.idx;
}
bool operator==(const self & other) const {
return a == other.a && b == other.b && idx == other.idx;
}
bool operator!=(const self & other) const {
return !(*this == other);
}
int operator-(const self & other) {
return idx - other.idx;
}
self operator-(int to_del) const {
self ret = *this;
ret.idx -= to_del;
return ret;
}
self operator++(int) {
self temp = *this;
++idx;
return temp;
}
self &operator++() {
++idx;
return *this;
}
self operator--(int) {
self temp = *this;
--idx;
return temp;
}
self &operator--() {
--idx;
return *this;
}
};
template < typename tA, typename tB >
double_iterator<tA,tB> operator+(double_iterator<tA,tB> it, int
to_add) {
it.idx += to_add;
return it;
}
template < typename tA, typename tB >
double_iterator<tA,tB> operator+(int to_add, double_iterator<tA,tB>
it) {
it.idx += to_add;
return it;
}
int main(void){
int A[N];
float B[N];
for (int i = 0; i < N; ++i){
A[i] = rand(); B[i] = A[i] % 10;
cout << "\t" << A[i] << "\t" << B[i] << endl;
}
std::sort(double_iterator<int,float>(A,B),
double_iterator<int,float>(A,B,N));
for (int i = 0; i < N; ++i){
cout << "\t" << A[i] << "\t" << B[i] << endl;
}
return 0;
}
Best,
John
--
http://John.Torjo.com -- C++ expert
... call me only if you want things done right
John
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
....
There are more...
Another question is: Can this code be made portable and simplified
to make it shorter? Maybe by deriving it from std::iterator?
--
Geert-Jan Giezeman
> On Sep 27, 6:10 am, jtorjo2...@yahoo.com wrote:
>> I compiled and run this using VS2003:
>>
>> struct double_iterator {
>>
>> struct value_type {
>> tA a; tB b;
>> tA *pa; tB *pb;
>> value_type(tA *pa, tB *pb) : pa(pa), pb(pb), a(*pa),
>> b(*pb) {};
>> void operator=(value_type other){
>> *pa = other.a; *pb = other.b;
>> };
>> bool operator<(value_type other){
>> return a < other.a ;
>> };
>> };
>
>
> 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
Please post relevant error messages.
Those first messages only tell you something about the instantiation
path. When I compile the code (g++ 3.4.6), the first line containing the
word 'error' is:
/usr/lib/gcc/i386-redhat-linux/3.4.6/../../../../include/c++/3.4.6/bits/stl_algo.h:90:
error: passing `const double_iterator<int, float>::value_type' as `this'
argument of
`bool double_iterator<tA,tB>::value_type::operator<(
double_iterator<tA, tB>::value_type)
[with tA = int, tB = float]' discards qualifiers
The second thing to do is try to understand this error message. I think
this one is quite clear. It points to the operator< of internal class
value_type of double_iterator. It tells you that there is a problem with
the 'this' parameter: it discards qualifiers. It even tells you that the
argument passed to it is const.
So, let's add a 'const' to this method
bool operator<(value_type other) const{
return a < other.a ;
};
and the errors are gone.
I think you should have put in some more effort in understanding the
error messages before posting to the newsgroup. John Torjo supplies code
to you that solves your problem, checked the code on a compiler, and now
you are dissatisfied because he did not check this on -your- compiler.
> There are more...
> Another question is: Can this code be made portable and simplified
> to make it shorter? Maybe by deriving it from std::iterator?
Probably it can be made shorter if you use the Boost iterator library.
Geert-Jan Giezeman
Roman.Pe...@gmail.com
> I think all the comp.lang.c++.moderated replies
> were BS! I wasted time on each one of them and it was
> a total waste of time...! None of those suggestions
> work...the zip iterator was not designed to do what I
> want to do...(well I'm glad I learnt about its useless
> existence for my problem) and the other solution is
> not that trivial...as it looks...beware...
>
> your suggestion doesnt work either :) Try them
> urself and you will find out why...its a waste of
> time to overload those operators!
>
> I think I found a solution, but its way more
> complicated than I thought it would be...so I guess
> I'll let all the gurus in c++.moderated think about
> it...I know others have posted solutions elsewhere to
> this problem...but I wish there was a clean way to
> solve the problem...a nice,clean, short answer...
>
> If this email ever gets posted to moderated,
> please do not post any pseudo-code solutions to this
> problem...And make sure you can sort two
> vectors/arrays with your code before you post. (If
> you need pseudo-code to sort two arrays in
> code...well...shall we say, keep it to yourself...!)
I believe that it's impossible to solve your problem
portably. That is you cant sort two arrays with a
single call to std::sort. Problem is in the signature
of std::sort -- it accepts RandomAccessIterators, which
should be dereferenced to T &. And as far as I
understand, this reference should not be invalidated
when you increment/decrement iterator. Thus, you
need N valid objects during the execution of sort,
and sort will swap these objects when appropriate.
IMHO, these constraints are enough to make this
problem unsolvable.
Roman Perepelitsa.
P.S.
John's solution is not portable, because
double_iterator is not RandomAccessIterator
(operator* does not return reference).
David Abrahams
on Thu Sep 27 2007, int19h-AT-gmail.com wrote:
> 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
David Abrahams
> I think all the comp.lang.c++.moderated replies
> were BS! I wasted time on each one of them and it was
> a total waste of time...! None of those suggestions
> work...the zip iterator was not designed to do what I
> want to do...
Unless you've described your goal very badly, yes, zip_iterator was
designed for exactly that purpose.
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Howard Hinnant
David Abrahams <da...@boost-consulting.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.
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
--
David Abrahams
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 ]
Daniel Krügler
> I don't see a swap for tuple in Boost or in the draft; I think that's
> a serious oversight on our part.
At least it's an open issue ;-)
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#522
Greetings from Bremen,
Daniel
--
kostas
> on Wed Sep 26 2007, Tom arken <weekender_ny-AT-yahoo.com> wrote:
>
> > I think all the comp.lang.c++.moderated replies
> > were BS! I wasted time on each one of them and it was
> > a total waste of time...! None of those suggestions
> > work...the zip iterator was not designed to do what I
> > want to do...
>
> Unless you've described your goal very badly, yes, zip_iterator was
> designed for exactly that purpose.
>
I had missed this discussion. I hope it's not too late.
zip_iterator cannot do sorting even with libraries that support proxy
iterators(like GNU's libstdc++) because its value_type and reference
are the same. I copy from zip_iterator.hpp(boost 1.34.1)
---------------------------------------------------------------------------------------------
template<typename IteratorTuple>
struct zip_iterator_base
{
private:
// Reference type is the type of the tuple obtained from the
// iterators' reference types.
typedef typename
detail::tuple_of_references<IteratorTuple>::type reference;
// Value type is the same as reference type.
typedef reference value_type;
---------------------------------------------------------------------------------------------
iter_swap cannot work with this design. It needs a true value_type.
(and there is not only iter_swap that needs a true value_type)
regards
Kostas
--