Sorting two arrays with one call to sort()?

[John]

I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...co pying/merging the arrays is out of
question...

Thanks a lot for your help.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Jim Langston]

"John" <we**********@y ahoo.comwrote in message
news:11******** **************@ g4g2000hsf.goog legroups.com...

>
I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...co pying/merging the arrays is out of
question...

Why isn't it a map? std::map<A, B>
Wouldn't that solve all your problems?
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Ben Rudiak-Gould]

John wrote:

I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++?

I should hope so, since the main point of the STL is to decouple algorithms
from data structures. Something like this ought to work:

struct double_iterator {

T* const a; U* const b; size_t i;

struct ref {
T& p; U& q;
ref(T& p, U& q) : p(p), q(q) {}
};

ref operator*() { return ref(a[i], b[i]); }

// ...

};

inline void operator=(ref x, ref y) { x.p = y.p; x.q = y.q; }
inline bool operator<(ref x, ref y) { return x.p < y.p; }

// ...

std::sort(doubl e_iterator(A,B, 0), double_iterator (A,B,size));

I think this will be as efficient as a hand-coded sort if you have a decent
compiler.

-- Ben

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[David Abrahams]

on Sat Sep 22 2007, John <weekender_ny-AT-yahoo.comwrote:

I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...co pying/merging the arrays is out of
question...

You might be able to use boost::zip_iter ator for this
(http://boost.org/libs/iterator/doc/zip_iterator.html)

Depending on details of your STL implementation, you may run into
trouble because zip_iterator's reference type is a proxy, and the
current C++ standard does not require proxy references to work.
However, several STL implementations *do* work with proxy references
(and the next standard does require them to work). The likelihood is
that if the code compiles, it will also give correct results -- but
you should verify that by testing.

HTH,

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

The Astoria Seminar ==http://www.astoriaseminar.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[John]

On Sep 22, 3:12 pm, Ben Rudiak-Gould <br276delet...@ cam.ac.ukwrote:

John wrote:

I havetwoseparate arraysA and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be doneusingintern alsort() of C++?

I should hope so, since the main point of the STL is to decouple algorithms
from data structures. Something like this ought to work:

struct double_iterator {

T* const a; U* const b; size_t i;

struct ref {
T& p; U& q;
ref(T& p, U& q) : p(p), q(q) {}
};

ref operator*() { return ref(a[i], b[i]); }

// ...

};

inline void operator=(ref x, ref y) { x.p = y.p; x.q = y.q; }
inline bool operator<(ref x, ref y) { return x.p < y.p; }

// ...

std::sort(doubl e_iterator(A,B, 0), double_iterator (A,B,size));

I think this will be as efficient as a hand-codedsortif you have a decent
compiler.

{ signature and clc++m banner removed - please remove them yourself. -mod }

Here is as far as I got, it still doesnt work :(

#include <iostream>

using namespace std;
const int N = 10;

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;
};
};
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(doubl e_iterator<int, float>(A,B,0),
double_iterator <int,float>(A,B ,N));

for (int i = 0; i < N; ++i){
cout << "\t" << A[i] << "\t" << B[i] << endl;
}

return 0;
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Carl Barron]

In article <11************ **********@g4g2 000hsf.googlegr oups.com>, John
<we**********@y ahoo.comwrote:

I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...co pying/merging the arrays is out of
question...

Thanks a lot for your help.

using boost::zip_iter ator looks like a solution that
allows the sort to work with const additional ram and
data is sorted. It requires a simple compare functor
since boost::tuple will compare the B entry if the A entries are equal.

see
http://boost.org/libs/iterator/doc/zip_iterator.html

typedef typename boost::tuple<A: :iterator,B::it eratoriter_tupl e;
// will use zip_iterator<it er_tuplevia make_zip_iterat or.

/*
sort || random access sequences A,B based on keyed on A only
should be fairly self explained:)
*/
struct compare_A_only
{
typedef typename boost::tuple<A: :value_type,B:: value_typearg;
bool operator (const arg &x,const arg &y) const
{
return boost::get<0>(x ) < boost::get<0>(y );
}
};
// ...
std::sort
(
boost::make_zip _iterator(iter_ tuple(a.begin() ,b.begin()),
boost::make_zip _iterator(iter_ tuple(a.end(),b .end()),
compare_A_only( )
};

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[BobR]

John <we**********@y ahoo.comwrote in message...

Please format (indent) your code. [ if you are using tabs, change them to
spaces for posting.]

Remove the extra semicolons, except where required.

You did not say what your problem is/was, or show the compiler errors (first
three).

FAQ http://www.parashift.com/c++-faq-lite
[ see section 5 ]

Thanks.
--
Bob R
POVrookie
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[xz]

On Sep 22, 12:42 pm, Erik Wikström <Erik-wikst...@telia. comwrote:

On 2007-09-22 16:52, xz wrote:

but by
using a vector you gain more functionality and have less limitations.

Is that always better? Even in the case you don't need those
functionality at all.
I thought, in the programming world, it's better for an object not to
have the function if it does not need the function.

>
--
Erik Wikström

[xz]

On Sep 22, 12:42 pm, Erik Wikström <Erik-wikst...@telia. comwrote:

On 2007-09-22 16:52, xz wrote:

but by
using a vector you gain more functionality and have less limitations.

Is that always better? Even in the case you don't need those
functionality at all.
I thought, in the programming world, it's better for an object not to
have the function if it does not need the function.

>
--
Erik Wikström

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

On 2007-09-24 20:30, xz wrote:

On Sep 22, 12:42 pm, Erik Wikström <Erik-wikst...@telia. comwrote:

>On 2007-09-22 16:52, xz wrote:

but by
using a vector you gain more functionality and have less limitations.

Is that always better? Even in the case you don't need those
functionality at all.
I thought, in the programming world, it's better for an object not to
have the function if it does not need the function.

If you would limit all objects to just provide the functionality you
require right now you would be in a lot of trouble, since most things
can do more than what you need. Also, by limiting the objects you make
it harder to extend the program in the future. One of the greatest
problems with arrays is that they have a fixes size, so if you find that
you need to have more elements in the array later on you will need to go
through all the code that uses the array and make sure that it works
with the new size, with a vector you do not usually have this problem.

But to answer you question, no it is not always better to use a vector
than an array. However those cases where it is not are pretty rare and
those who run into them usually recognise them when they seem them. To
date I have personally never been in such a situation, mostly because I
do not write programs where they arise.

--
Erik Wikström