sorting side by side

[Noah Roberts]

I know there must be a way to do this using stl functions and not
reinventing the sort loops and such but I need to sort several arrays
side by side using one as the "key". Interested in ideas here...

Two directions I can think of would be to create some sort of iterator
or to create an object to wrap the value and index of the key array and
then place these in a vector and sort it. Creating an iterator seems
like maybe too complex but would probably be the more efficient
way...maybe it could be generalized enough to use again sometime. It
would certainly teach me more about iterators as I have never built my
own; always use what is there already. The other would be easier,
maybe.

I'm very open to suggestion here.

 

[Daniel T.]

I know there must be a way to do this using stl functions and not
reinventing the sort loops and such but I need to sort several arrays
side by side using one as the "key". Interested in ideas here...

Two directions I can think of would be to create some sort of iterator
or to create an object to wrap the value and index of the key array and
then place these in a vector and sort it. Creating an iterator seems
like maybe too complex but would probably be the more efficient
way...maybe it could be generalized enough to use again sometime. It
would certainly teach me more about iterators as I have never built my
own; always use what is there already. The other would be easier,
maybe.

I'm very open to suggestion here.

Create a class that contains one of each element from each array, they
are obviously dependent. Make a container of these objects and sort it.

 

[Cy Edmunds]

I know there must be a way to do this using stl functions and not
reinventing the sort loops and such but I need to sort several arrays
side by side using one as the "key". Interested in ideas here...

Two directions I can think of would be to create some sort of iterator
or to create an object to wrap the value and index of the key array and
then place these in a vector and sort it. Creating an iterator seems
like maybe too complex but would probably be the more efficient
way...maybe it could be generalized enough to use again sometime. It
would certainly teach me more about iterators as I have never built my
own; always use what is there already. The other would be easier,
maybe.

I'm very open to suggestion here.

One way is to make a std::vector<int> (call it "index") the same length as
the arrays and sort it so that some_array[index[j]] is in the proper order.
Then the other arrays can be accessed in order using the same trick. If you
need to actually reorder all the arrays that becomes trivial once you have
the index array.

BTW it may be a symptom of a design problem if you have a bunch of parallel
arrays. Why not refactor into a single array of objects? Of course I know
that sometimes there are preconditions of the job which prevent this.

Cy

 

[Noah Roberts]

I know there must be a way to do this using stl functions and not
reinventing the sort loops and such but I need to sort several arrays
side by side using one as the "key". Interested in ideas here...

Two directions I can think of would be to create some sort of iterator
or to create an object to wrap the value and index of the key array and
then place these in a vector and sort it. Creating an iterator seems
like maybe too complex but would probably be the more efficient
way...maybe it could be generalized enough to use again sometime. It
would certainly teach me more about iterators as I have never built my
own; always use what is there already. The other would be easier,
maybe.

I'm very open to suggestion here.

One way is to make a std::vector<int> (call it "index") the same length as
the arrays and sort it so that some_array[index[j]] is in the proper order.
Then the other arrays can be accessed in order using the same trick. If you
need to actually reorder all the arrays that becomes trivial once you have
the index array.

I was thinking this wouldn't work because there would be no way to tie
the int with the subject but by providing a comp function this should
work. Simpler than the wrapper.

BTW it may be a symptom of a design problem if you have a bunch of parallel
arrays. Why not refactor into a single array of objects? Of course I know
that sometimes there are preconditions of the job which prevent this.

Yes, there rather are. They are public members of a class and accessed
all over the damn place. It's still tempting to fix it though.

 

[Andrey Tarasevich]

...
One way is to make a std::vector<int> (call it "index") the same length as
the arrays and sort it so that some_array[index[j]] is in the proper order.
Then the other arrays can be accessed in order using the same trick. If you
need to actually reorder all the arrays that becomes trivial once you have
the index array.

I was thinking this wouldn't work because there would be no way to tie
the int with the subject but by providing a comp function this should
work. Simpler than the wrapper.

Instead of an 'int' array you can sort a 'std::vector<T*>' array, where
'T' is the element type in the index array. This solves the tying issue
in the most straightforward way.

Once the pointer vector is sorted, it is easy to rearrange all the
arrays. (Note, that you can easily convert a 'T*' pointer into the array
index using address arithmetics).

 

[Andrey Tarasevich]

...
BTW it may be a symptom of a design problem if you have a bunch of parallel
arrays. Why not refactor into a single array of objects? Of course I know
that sometimes there are preconditions of the job which prevent this.
...

It is not necessarily a design problem at all. When related data from
the same design level ends up in parallel arrays - that would most
likely indicate a problem. However, when different arrays belong to
completely different levels of design (i.e. when the data in the
additional arrays has absolutely no meaning in the context where the
original array is introduced), it is not a problem. Quite the opposite,
in that case putting it all in the same array would be a design error.
It is the later design error that is seen quite often in actual code.
Like, for example, a 'Tree_Node' class in a binary tree library, which
contains a 'mikes_file_mode_bitfield' and 'jeffs_pointer_to_the_io_pipe'
just because somewhere at more specific level of design Mike or Jeff
wanted to associate these pieces of data with the tree nodes and decided
that it would be nice to "have it in the same array".

 

[Daniel T.]

It is not necessarily a design problem at all. When related data from
the same design level ends up in parallel arrays - that would most
likely indicate a problem. However, when different arrays belong to
completely different levels of design (i.e. when the data in the
additional arrays has absolutely no meaning in the context where the
original array is introduced), it is not a problem.

Unfortunately, the condition of the question precludes that as a
possibility. The two arrays are intimately related and therefore must
both have meaning in the same context, or the problem of having to keep
them in the same order wouldn't have come up.

Quite the opposite,
in that case putting it all in the same array would be a design error.
It is the later design error that is seen quite often in actual code.
Like, for example, a 'Tree_Node' class in a binary tree library, which
contains a 'mikes_file_mode_bitfield' and 'jeffs_pointer_to_the_io_pipe'
just because somewhere at more specific level of design Mike or Jeff
wanted to associate these pieces of data with the tree nodes and decided
that it would be nice to "have it in the same array".

There is a dramatic difference between "wouldn't it be nice if they were
in the same array" and "They must be 'side by side' in order for the
system to work."

 

[Robbie Hatley]

I know there must be a way to do this using stl functions and not
reinventing the sort loops and such but I need to sort several arrays
side by side using one as the "key". Interested in ideas here...

Two directions I can think of would be to create some sort of iterator
or to create an object to wrap the value and index of the key array and
then place these in a vector and sort it. Creating an iterator seems
like maybe too complex but would probably be the more efficient
way...maybe it could be generalized enough to use again sometime. It
would certainly teach me more about iterators as I have never built my
own; always use what is there already. The other would be easier,
maybe.

If you have two equal-sized arrays, one of keys and the other of
values, with the keys "linked" to the values conceptually, then
you're doing it all wrong. You're trying to re-define std::map.
Why not use a real std::map instead? It does all the sorting for
you, automatically. Each time you insert a new entry, it gets
added to the map in sorted position.

Research std::map and std:air for more info.

Some sample code (pretested, working) to give you the idea:

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

using std::cout;
using std::endl;
using std::string;
using std::map;
using std:air;
using std::make_pair;

class MyClass
{
public:
MyClass() : msg("") {}
MyClass(string const & Msg) : msg(Msg) {}
string msg;
};

int main()
{
typedef unsigned long int user_id;

map<user_id, MyClass> fizzbin;

MyClass Bob ("Bob");
MyClass Tom ("Tom");
MyClass Sam ("Sam");
MyClass Fred ("Fred");

fizzbin.insert(make_pair(37307, Bob));
fizzbin.insert(make_pair(82219, Tom));
fizzbin.insert(make_pair(73884, Sam));
fizzbin.insert(make_pair(21984, Fred));

// At this point, all entries are automatically sorted
// in order of user id. Lookup is blazingly fast because
// it's implemented using binary-tree technology:

// Look-up and print name of user with id# 73884:
cout << fizzbin[73884].msg << endl;
}


--
Cheers,
Robbie Hatley
East Tustin, CA, USA
lone wolf intj at pac bell dot net
(put "[usenet]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/