[Godzilla]

How can I sort two Lists or Vectors in conjunction with each other?

For instance, given the following code making two lists, "1, 2, 3, 4, 5" and "20, 9, 24, 25, 16":

list<int> index;
list<int> values;
for(int i=1; i<=5; i++) index.push_back(i);
int arr[5] = {20, 9, 24, 25, 16};
for(int i=0; i<5; i++) values.push_back(arr[i]);
for(list<int>::iterator iter=index.begin(), iter2=values.begin(); iter!=index.end(); iter++, iter2++) cout << "Index: " << *iter << " Values: " << *iter2 << endl;

Which outputs:

Index: 1 Values: 20
Index: 2 Values: 9
Index: 3 Values: 24
Index: 4 Values: 25
Index: 5 Values: 16

How can I sort the list 'values' in descending order, and concurrently sort the list 'index'? Such that Values becomes 25, 24, 20, 16, 9, and 'index' becomes 4, 3, 1, 5, 2.

I think I could do something like this using multimaps, using the values as keys and the indexes as map values. However I believe those sort every element automatically by key, and I have a large amount of elements to insert, and only need to sort a fraction of them - thus, sorting every element would be a waste of sorting time. I'm thinking in terms of partial_sort() instead.

And since I don't need random access, only sequential, I figure two lists is the way to go; but I don't know how to sort them together. If someone has any other ideas, feel free to share.

This post has been edited by Godzilla: 03 June 2008 - 05:57 PM

[perfectly.insane]

Godzilla, on 3 Jun, 2008 - 05:55 PM, said:

And since I don't need random access, only sequential, I figure two lists is the way to go; but I don't know how to sort them together. If someone has any other ideas, feel free to share.

You might not, but the sort algorithm does. Well, at least as implemented by std::sort, std::stable_sort, and std::partial_sort. As you'll notice in the definitions of these functions, the template type parameter is RandomAccessIterator, so you'll need a vector or plain array if you want to use these functions. Sorting a list in place would be expensive, and it seems that heap-sort would be the only viable method of sorting a list efficiently (at least, without converting to a vector first, as the items have to be put in a new data structure anyway for this sort).

The easiest way to sort this would be to define a class or struct with the two items that you want, and then defining the compare operators on them. I.e.

struct SomeType
{
    int key;
    int value;
    bool operator>(const SomeType& rhs) { return key > rhs.key; }
    bool operator>=(const SomeType& rhs) { .... }
    .
    .
};

std::vector<SomeType> v;
// Add some
std::sort(v.begin(), v.end());

You can also call std::sort and friends with a comparison function as a third argument:

int comparison_function(const SomeType& a, const SomeType& b )
{
    return (a.key == b.key) ? 0 : ((a.key > b.key) ? 1 : -1);
}

std::vector<SomeType> v;
std::sort(v.begin(), v.end(), comparison_function);

This post has been edited by perfectly.insane: 03 June 2008 - 06:59 PM

[Godzilla]

Thank you, the struct is a good idea.

I'm having some problems with the coding though. In the following code:

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

struct SomeType {  
	int key;
	int value;
	bool operator>(const SomeType& rhs) { return key > rhs.key; }
	bool operator>=(const SomeType& rhs) { return key >= rhs.key; }
	bool operator<(const SomeType& rhs) { return key < rhs.key; }
	bool operator<=(const SomeType& rhs) { return key <= rhs.key; }
};

int comparison_function(const SomeType& a, const SomeType& b ){  
	return (a.key == b.key) ? 0 : ((a.key > b.key) ? 1 : -1);  
}  

int main() {
	vector<SomeType> v;
	int size = 10;
	for(int i=0; i<size; i++){
		SomeType s;
		s.key = i+1;
		s.value = rand() % size;
		v.push_back(s);
	}
	for(int i=0; i<size; i++) cout << "Key: " << v.at(i).key << " Value: " << v.at(i).value << endl;
	sort(v.begin(), v.end());
//	sort(v.begin(), v.end(), comparison_function);
	for(int i=0; i<size; i++) cout << "Sorted Key: " << v.at(i).key << " Value: " << v.at(i).value << endl;
}

If I simply do "sort(v.begin(), v.end());" instead of using the comparison_function, I get a bunch of "error: passing `const SomeType' as `this' argument of `bool SomeType::operator<(const SomeType&)' discards qualifiers" errors.

Also when sorting by the comparison_function, I'm not sure what exactly sort is doing - sort seems to sort by the 'key' in descending order, regardless of what comparison function or the struct operators are. Replacing all the 'key's with 'value's in the comparison function and operators has no effect on the ordering. Even always returning 1 or always returing -1 in the comparison function give the same ordering.

What is needed for sort to work without a comparison function, and why isn't the comparison function working?

Edit: and another issue is that if the size of the vector is 17 or larger, I get a Segmentation Fault when running the compiled program.

This post has been edited by Godzilla: 03 June 2008 - 08:59 PM

[perfectly.insane]

Godzilla, on 3 Jun, 2008 - 08:56 PM, said:

If I simply do "sort(v.begin(), v.end());" instead of using the comparison_function, I get a bunch of "error: passing `const SomeType' as `this' argument of `bool SomeType::operator<(const SomeType&)' discards qualifiers" errors.

This means that whatever is calling the operator functions (whatever one is doing the comparison) is performing them on a constant argument. It cannot call the operator functions on a constant argument the way it is written... i.e.:

void func(const SomeType& c1, const SomeType& c2)
{
     if(c1 > c2) // Illegal as c1 is const
     { ... }
}

To fix this, make the functions const:

bool operator>(const SomeType& rhs) const { .... }

Quote

Also when sorting by the comparison_function, I'm not sure what exactly sort is doing - sort seems to sort by the 'key' in descending order, regardless of what comparison function or the struct operators are. Replacing all the 'key's with 'value's in the comparison function and operators has no effect on the ordering. Even always returning 1 or always returing -1 in the comparison function give the same ordering.

After looking that function back up, I believe I'm incorrect on the prototype of the comparison function. It should return a bool, and should return true if a > b.

[Godzilla]

Thank you very much, those changes worked great

One strange new problem I encountered was when I tried to add a member variable to the struct that would allow easy control over which field was used to sort, 'key' or 'value':

struct SomeType {  
	int key;
	int value;
	int sort_field;
	SomeType(){sort_field = value;}
	bool operator>(const SomeType& rhs) const { return sort_field > rhs.sort_field; }
	bool operator>=(const SomeType& rhs) const { return sort_field >= rhs.sort_field; }
	bool operator<(const SomeType& rhs) const { return sort_field < rhs.sort_field; }
	bool operator<=(const SomeType& rhs) const { return sort_field <= rhs.sort_field; }
};

For a simple "sort(v.begin(), v.end());" this gave the strange ordering (of keys) of 2, 3, 4, ..., 10, 1. I thought maybe it was treating it like a string or something, so I added a cast to (int) but that didn't change anything.

And it gave an even stranger ordering when sort_field was equal to value:

Sorted Key: 1 Value: 3
Sorted Key: 9 Value: 9
Sorted Key: 2 Value: 6
Sorted Key: 6 Value: 5
Sorted Key: 5 Value: 3
Sorted Key: 7 Value: 6
Sorted Key: 3 Value: 7
Sorted Key: 8 Value: 2
Sorted Key: 4 Value: 5
Sorted Key: 10 Value: 1

This ordering makes no sense at all. But I did some debugging with cout and sort_field seems to be assigned properly, and the 'operator<' function (the only function which seems to be called by sort) seems to give the right return.

What could be going wrong here?

[perfectly.insane]

How is sort_field being updated with each change to each SomeType? Anyway, this is an example where using the second way of doing this (providing an external comparison function) would make more sense. If you want to control this within the struct itself, you could create a static boolean that specifies the sort order...

bool st_isgreater_key(const SomeType& a, const SomeType& B ) { return a.key > b.key; }
bool st_isgreater_value(const SomeType& a, const SomeType& B ) { return a.value > b.value; }

This post has been edited by perfectly.insane: 05 June 2008 - 03:10 AM

[Godzilla]

It isn't being updated, but I don't need to edit the struct values. I don't understand why it gives the odd sorting order though.

Anyway that was just an extra thing I was trying, and was curious why it wouldn't work.

[perfectly.insane]

But value isn't being initialized to anything.. so if value contains garbage, so will sort_field? The constructor that is shown is not actually accepting a parameter to initialize value.

[Godzilla]

But I debugged with putting cout << sort_field << " " << rhs.sort_field << endl; in the operator functions, and the values seem to be being passed properly; no garbage present. And the sorting for sort_field = key is pretty much correct, except for 1 strangely at the bottom.

It's not important at all, as I'm not going to use sort_field anyway, I was just confused.