C++Talk.NET

dipa · Guest

Two arrays A[] and B[], same size, logically elements (A[i] -> B[i]) are
connected .
I need to sort A and still keep connection with B.
I don't want to create any extra arrays.
My goal is like this:
/////////////////////////////////////////////////////////////
long a[] = {3, 7, 5, 1, ..};
long b[] = {3, 7, 5, 1, ..};

my_iterator<my_pair> it_begin(a, b, 0);
my_iterator<my_pair> it_end(a, b, len);
std::sort(it_begin, it_end);
////////////////////////////////////////////////////////

I've almost working code.
VC 2003 std::sort() works as expected, but std::stable_sort().
g++ (GCC) 3.3.6 not sorting at all.

What is wrong?
Thanks,
Dima

-------------------------------------------------------------
//#include "stdafx.h"
#include <vector>
#include <algorithm>
struct my_pair
{
long &_a, &_b;
long _xa, _xb;
my_pair(long& a, long& b):_a(a), _b(b), _xa(_a), _xb(_b){}
//my_pair(const my_pair& c):_a(c._a), _b(c._b), _xa(_a), _xb(_b){}
const my_pair& operator = (const my_pair& c)
{
_a = c._xa;
_b = c._xb;
_xa = _a;
_xb = _b;
return *this;
}
};
template <typename _T>
class it
{
public:
typedef std::random_access_iterator_tag iterator_category;
typedef _T value_type;
typedef int difference_type;
typedef difference_type distance_type; // retained
typedef _T* pointer;
typedef _T& reference;
//typedef my_pair_r reference;
protected:
long _pos;
long* _a;
long* _b;
public:
it():_a(NULL), _b(NULL),_pos(-1){}
it(long *a, long *b, long pos):_pos(pos), _a(a), _b(b){}
it(const it& c):_pos(c._pos), _a(c._a), _b(c._b){}
public:
it operator-(difference_type d){ return it(_a, _b, _pos - d); }
it operator+(difference_type d){ return it(_a, _b, _pos + d);}
const it& operator+=(difference_type d){ _pos+=d; return *this; }
const it& operator-=(difference_type d) { _pos-=d; return *this; }
difference_type operator-(const it& c) { return _pos - c._pos; }
bool operator<(const it& c) const { return _pos < c._pos; }
bool operator>(const it& c) const { return _pos > c._pos; }
bool operator==(const it& c) const { return _pos == c._pos; }
bool operator!=(const it& c) const { return _pos != c._pos; }
const it& operator--() { _pos--; return *this; }
it operator--(int) { return it(_a, _b, _pos--); }
const it& operator++() { _pos++; return *this; }
it operator++(int) { return it(_a, _b, _pos++); }
value_type operator*() const { return value_type(_a[_pos], _b[_pos]);}
};

bool my_cmp(const my_pair& a, const my_pair& b)
{
return a._a < b._a;
}

int main(int argc, char* argv[])
{
long a[] = {3, 7, 5, 1, 23, 15, 88, 44, 11, 32, 33, 11, 18, 14, 16, 22,
3, 7, 5, 1, 23, 15, 88, 1, 11, 32, 16, 11, 18, 14, 16, 22, 55, 0};
long b[] = {3, 7, 5, 1, 23, 15, 88, 44, 11, 32, 33, 11, 18, 14, 16, 22, 3,
7, 5, 1, 23, 15, 88, 1, 11, 32, 16, 11, 18, 14, 16, 22, 55, 0};
long len = sizeof(a)/sizeof(*a);
it it<my_pair> end(a, b, len);
std::stable_sort(begin, end, my_cmp);
//std::sort(begin, end, my_cmp);
for (long i = 0; i < len; i++)
printf("a[%i]=%itb[%i]=%inr", i, a[i], i, b[i]);
return 0;
}

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

Edson Manoel · Guest

I'm not sure if this is the cause of your problem, but I think your
your Random Access Iterator is incomplete. It must be mutable and
assignable too.

Try using boost::zip_iterator or try debugging inside the stable_sort
algorithm!

Regards

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

Joel Eidsath · Guest

Is there a reason that you aren't using a map<int, int>?

Here is some code that will do everything your code does. I just kept
the array for input. You'll probably want to ditch it.

#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main(void){
int a[] = {3, 7, 5, 1, 23, 15, 88, 44, 11, 32, 33, 11, 18, 14, 16, 22,
3, 7, 5, 1, 23, 15, 88, 1, 11, 32, 16, 11, 18, 14, 16, 22, 55, 0};
int len = sizeof(a)/sizeof(*a);

map<int,int> m;
for (int i=0; i< len; ++i){
m[i] = a[i];
}

map for (mP = m.begin(); mP != m.end(); ++mP){
cout << (*mP).first << " " << (*mP).second << endl;
}
}

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

Joel Eidsath · Guest

That's the second time I've made that mistake this week: multimap
should be used, not map

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

dipa · Guest

I need 2 separate arrays for direct access.
They are very huge and I don't want to allocate extra memory for any
supporting vector, map, multimap, and etc.

Recently, I've found mistake in comparison function:
bool my_cmp(const my_pair& a, const my_pair& b)
{
return a._a < b._a;
it should be
return a._xa < b._xa;
}

VC - sort() and stable_sort() are OK.
GCC (3) - sort() is OK but stable_sort().

"Joel Eidsath"

John Potter · Guest

On 1 Sep 2005 05:13:43 -0400, "dipa" <kvartira (AT) hotmail (DOT) com> wrote:

dipa · Guest

John,
Thank you for very helpful suggestion.

John Potter · Guest

On 3 Sep 2005 14:51:40 -0400, "dipa" <kvartira (AT) hotmail (DOT) com> wrote:

Dmitry · Guest