By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,649 Members | 2,142 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,649 IT Pros & Developers. It's quick & easy.

Sorting two arrays with one call to sort()?

P: n/a

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...copying/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++.moderated. First time posters: Do this! ]

Sep 22 '07 #1
Share this Question
Share on Google+
10 Replies


P: n/a
"John" <we**********@yahoo.comwrote in message
news:11**********************@g4g2000hsf.googlegro ups.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...copying/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++.moderated. First time posters: Do this! ]

Sep 22 '07 #2

P: n/a
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(double_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++.moderated. First time posters: Do this! ]

Sep 22 '07 #3

P: n/a

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...copying/merging the arrays is out of
question...
You might be able to use boost::zip_iterator 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++.moderated. First time posters: Do this! ]

Sep 23 '07 #4

P: n/a
On Sep 22, 3:12 pm, Ben Rudiak-Gould <br276delet...@cam.ac.ukwrote:
John wrote:
I havetwoseparatearraysA 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 doneusinginternalsort() 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(double_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(double_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++.moderated. First time posters: Do this! ]

Sep 23 '07 #5

P: n/a
In article <11**********************@g4g2000hsf.googlegroups. com>, John
<we**********@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...copying/merging the arrays is out of
question...

Thanks a lot for your help.
using boost::zip_iterator 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::iteratoriter_tuple;
// will use zip_iterator<iter_tuplevia make_zip_iterator.

/*
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.be gin()),
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++.moderated. First time posters: Do this! ]

Sep 23 '07 #6

P: n/a

John <we**********@yahoo.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++.moderated. First time posters: Do this! ]

Sep 23 '07 #7

P: n/a
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

Sep 24 '07 #8

P: n/a
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

Sep 24 '07 #9

P: n/a
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
Sep 24 '07 #10

P: n/a
On Sep 24, 8:30 pm, xz <zhang.xi...@gmail.comwrote:
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.
It depends. The fact that vector has all of the functionality
of a C style array (or almost) means that it can always be used
where a C style array can be used. The real issue, however, is
that array types in C are broken, so it's best to avoid them as
much as possible. I believe that the next release of the
standard will have boost::array in it, which is a very valid
alternative to vector in cases where you don't need (or want)
the extra functionality.

If the fact that the array contains exactly 10 elements is an
important invariant, the possibility to change the size of
std::vector is a disadvantage. But not enough to outweigh the
disavantages of a C style array. Today, without boost::array,
you will normally only use C style arrays when either 1) you
need static initialization, or 2) you want the compiler to
calculate the size from the initialization list. Boost::array
will also provide 1; I think that there are also proposals to
cover 2, but I'm less familiar with them.

Note that for case 2, above, C style arrays are often combined
with standard containers. Thus, if you want a constant map of
strings to ints, you might write something like:

typedef std::map< std::string, int Map ;
struct MapInit
{
char const* key ;
int value ;
operator Map::value_type() const
{
return Map::value_type( std::string( key ), value ) ;
}
} ;

MapInit const mapInit[] =
{
{ "one" , 1 },
{ "two" , 2 },
{ "five" , 5 },
{ "ten" , 10 },
{ "twenty" , 20 },
{ "one hundred", 100 },
} ;
Map const map( begin( mapInit ), end( mapInit ) ) ;

Only the map itself would be visible to users, of course.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Sep 25 '07 #11

This discussion thread is closed

Replies have been disabled for this discussion.