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,A[j], but also
B,B[j] ; whenever it swaps A,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.

 

[Guest]

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,A[j], but also
B,B[j] ; whenever it swaps A,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...

No, it can not be done with any of the standard C++ algorithms, you
would have to implement your own sort function for this.

It seems to me that you greatest problem is an error in the design,
keeping related data in two separate containers, if element A is
somehow related to B then you need to make that relation explicit in
the code. Without knowing about your circumstances I would say that a
second design error is to use an array instead of std::vector.

You ought to store the data in an std::vector<std:air<A,B> >, where A
and B is the types of the elements in A and B respectively. Another
alternative is to use std::map<A,B> which is sorted from the beginning.
A third possibility, depending on how you need to access the elements in
B is to make each element in A an std:air<A, B*> and let the pointer
point to the correct element in B, using this scheme will not sort B but
you will keep the relationship between the elements.

Yes, I know that you said that copying or merging the arrays were out of
question, but on the other hand you said that speed was paramount, and
any one of the schemes above will most probably be faster than whatever
you come up with while trying to re-implement a sorting function.

I would probably do something like this if I was required to keep the
two structures separate:

// Create a vector to store the elements
std::vector<std:air<A, B> > vec;
vec.reserve(SIZE); // SIZE is the number of elements in the arrays

// Add the elements
for (size_t i = 0; i < SIZE; ++i)
{
vec.push_back(std::make_pair(A, B));
}

// Sort
std::sort(vec.begin(), vec.end(), Comp); // Comp is a comparator that
// sorts after the first element in the pair

// Write values back sorted into the arrays
for (size_t i = 0; i < SIZE; ++i)
{
A = vec.first;
B = vec.second;
}

 

[Jim Langston]

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,A[j], but also
B,B[j] ; whenever it swaps A,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?

 

[xz]

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,A[j], but also
B,B[j] ; whenever it swaps A,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...

No, it can not be done with any of the standard C++ algorithms, you
would have to implement your own sort function for this.

It seems to me that you greatest problem is an error in the design,
keeping related data in two separate containers, if element A is
somehow related to B then you need to make that relation explicit in
the code. Without knowing about your circumstances

I would say that a
second design error is to use an array instead of std::vector.

I agree that the logically related A and B should be explicitly
related in the code.
However, I have got the part why vector is better than array in this
case?

You ought to store the data in an std::vector<std:air<A,B> >, where A
and B is the types of the elements in A and B respectively. Another
alternative is to use std::map<A,B> which is sorted from the beginning.
A third possibility, depending on how you need to access the elements in
B is to make each element in A an std:air<A, B*> and let the pointer
point to the correct element in B, using this scheme will not sort B but
you will keep the relationship between the elements.

Yes, I know that you said that copying or merging the arrays were out of
question, but on the other hand you said that speed was paramount, and
any one of the schemes above will most probably be faster than whatever
you come up with while trying to re-implement a sorting function.

I would probably do something like this if I was required to keep the
two structures separate:

// Create a vector to store the elements
std::vector<std:air<A, B> > vec;
vec.reserve(SIZE); // SIZE is the number of elements in the arrays

// Add the elements
for (size_t i = 0; i < SIZE; ++i)
{
vec.push_back(std::make_pair(A, B));
}

// Sort
std::sort(vec.begin(), vec.end(), Comp); // Comp is a comparator that
// sorts after the first element in the pair

// Write values back sorted into the arrays
for (size_t i = 0; i < SIZE; ++i)
{
A = vec.first;
B = vec.second;
}

 

[Guest]

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,A[j], but also
B,B[j] ; whenever it swaps A,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...

No, it can not be done with any of the standard C++ algorithms, you
would have to implement your own sort function for this.

It seems to me that you greatest problem is an error in the design,
keeping related data in two separate containers, if element A is
somehow related to B then you need to make that relation explicit in
the code. Without knowing about your circumstances

I would say that a
second design error is to use an array instead of std::vector.

I agree that the logically related A and B should be explicitly
related in the code.
However, I have got the part why vector is better than array in this
case?

Because a vector is almost always better than an array, if you can use
either a vector or an array, go for the vector.

A vector can do the same things as an array, plus a number of other
things, and in most cases it will be just as effective as an array. In
almost all cases you can use a vector wherever you use an array, but by
using a vector you gain more functionality and have less limitations.

 

[Ben Rudiak-Gould]

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,A[j], but also
B,B[j] ; whenever it swaps A,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, b); }

// ...

};

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

 

[David Abrahams]

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,A[j], but also
B,B[j] ; whenever it swaps A,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! ]

 

[Carl Barron]

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,A[j], but also
B,B[j] ; whenever it swaps A,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::iterator> iter_tuple;
// will use zip_iterator<iter_tuple> via 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_type> arg;
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()
};

 

[John]

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,A[j], but also
B,B[j] ; whenever it swaps A,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, b); }

// ...

};

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,b); }
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 = rand(); B = A % 10;
cout << "\t" << A << "\t" << B << 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 << "\t" << B << endl;
}

return 0;
}

 

[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,A[j], but also
B,B[j] ; whenever it swaps A,A[j].
Can this be done using internalsort() 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...

No, it can not be done with any of the standard C++ algorithms, you
would have to implement your ownsortfunction for this.

It seems to me that you greatest problem is an error in the design,
keeping related data in two separate containers, if element A is
somehow related to B then you need to make that relation explicit in
the code. Without knowing about your circumstances I would say that a
second design error is to use an array instead of std::vector.

You ought to store the data in an std::vector<std:air<A,B> >, where A
and B is the types of the elements in A and B respectively. Another
alternative is to use std::map<A,B> which is sorted from the beginning.
A third possibility, depending on how you need to access the elements in
B is to make each element in A an std:air<A, B*> and let the pointer
point to the correct element in B, using this scheme will notsortB but
you will keep the relationship between the elements.

Yes, I know that you said that copying or merging the arrays were out of
question, but on the other hand you said that speed was paramount, and
any one of the schemes above will most probably be faster than whatever
you come up with while trying to re-implement a sorting function.

I would probably do something like this if I was required to keep the
two structures separate:

// Create a vector to store the elements
std::vector<std:air<A, B> > vec;
vec.reserve(SIZE); // SIZE is the number of elements in the arrays

// Add the elements
for (size_t i = 0; i < SIZE; ++i)
{
vec.push_back(std::make_pair(A, B));
}

//Sort
std::sort(vec.begin(), vec.end(), Comp); // Comp is a comparator that
// sorts after the first element in the pair

// Write values back sorted into the arrays
for (size_t i = 0; i < SIZE; ++i)
{
A = vec.first;
B = vec.second;
}

There is a reason I can not keep both that data in a pair.
Of course that would have made my life easier..

Thanks for your thoughts thou. I presented the question using
arrays, but I indeed the data is kept in vectors.

 

[BobR]

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! ]

 

[xz]

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.

 

[xz]

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.

 

[Guest]

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.

 

[James Kanze]

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.