6 Replies - 960 Views - Last Post: 12 July 2010 - 09:38 AM Rate Topic: -----

#1 machoolah   User is offline

  • D.I.C Head

Reputation: -6
  • View blog
  • Posts: 87
  • Joined: 17-May 09

sorting an array of user-defined class based on the value of a member

Posted 11 July 2010 - 10:19 AM

Hello everyone,
I have a class in my code. I use an array of the said class in my code. (So obviously each row of the array contains an instance of the class). I wonder if that is at all possible to sort the rows of the array based on the values of a member of the class for each row?

I know I can use two phase constructors or an extra array that keeps the values of the said member. But I prefer, if at all possible, use the snippet I have come up with, which happens to have an error. If you can spot the error with the following code, or know that it is not possible to do the sorting this way, please let me know. Any help is highly appreciated.

Thanks!
#include < iostream>

using namespace std;

class cTest{
public:
	int ele[10];
	int size;
};

cTest C[5];

int main (){
	C[0].size = 10;
	C[1].size = 3;
	C[2].size = 103;
	C[3].size = 31;
	C[4].size = 23;  
	cTest *tmp;
	for (int i = 0; i < 4; i++){
		for (int j = 1 ; j < 5; j++){
			if (C[i].size < C[j].size){
				tmp = &C[i];
				C[i] = C[j];
				C[i]=*tmp;
			}
		}
	}
	return 0;
}




Is This A Good Question/Topic? 0
  • +

Replies To: sorting an array of user-defined class based on the value of a member

#2 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1460
  • View blog
  • Posts: 4,726
  • Joined: 20-March 10

Re: sorting an array of user-defined class based on the value of a member

Posted 11 July 2010 - 10:31 AM

you have a space where there shouldnt be one in
#include <iostream>


Was This Post Helpful? 0
  • +
  • -

#3 sarmanu   User is offline

  • D.I.C Lover
  • member icon

Reputation: 967
  • View blog
  • Posts: 2,362
  • Joined: 04-December 09

Re: sorting an array of user-defined class based on the value of a member

Posted 11 July 2010 - 10:40 AM

It won't work. Why do you want to deal with pointers?
tmp = &C[i];
C[i] = C[j];


basically tmp points to C[i], then you modify C[i] so automatically you modify the pointer, therefore tmp points to C[j] always. Your sort is also wrong, as the second loop should start from i + 1:
for (int j = i + 1 ; j < 5; j++){


Using a non-pointer approach, this would work:
#include < iostream>

using namespace std;

class cTest{
public:
	int ele[10];
	int size;
};

cTest C[5];

int main (){
	C[0].size = 10;
	C[1].size = 3;
	C[2].size = 103;
	C[3].size = 31;
	C[4].size = 23;  
	cTest tmp;
	for (int i = 0; i < 4; i++){
		for (int j = i + 1 ; j < 5; j++){
			if (C[i].size > C[j].size){
				tmp = C[i];
				C[i] = C[j];
				C[j] = tmp;
			}
		}
	}

	for (int i = 0; i < 5; i++)
		cout << C[i].size << " ";

	return 0;
}


But you have some bad practices here: C is global. There is no need for it to be global. You also use raw arrays. Better use std::vector. The easiest way to do this would be to call std::sort on a vector (works with raw arrays too) of cTest. Not that you have to overload operator < if you want to use std::sort in this way:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class cTest
{
private:
	int ele[10];
	int size;
public:
	cTest(const int size)
	{
		this->size = size;
	}

	int getSize() const
	{
		return size;
	}

	bool operator<(const cTest &t) const
	{
		return size < t.size;
	}
};

int main ()
{
	std::vector<cTest> C;
	C.push_back(cTest(10));
	C.push_back(cTest(3));
	C.push_back(cTest(103));
	C.push_back(cTest(31));
	C.push_back(cTest(23));

	std::sort(C.begin(), C.end());
	for (size_t i = 0; i < C.size(); i++)
		std::cout << C[i].getSize() << " ";

	return 0;
}


Was This Post Helpful? 1
  • +
  • -

#4 Bench   User is offline

  • D.I.C Lover
  • member icon

Reputation: 944
  • View blog
  • Posts: 2,464
  • Joined: 20-August 07

Re: sorting an array of user-defined class based on the value of a member

Posted 11 July 2010 - 10:48 AM

Your swap algorithm is not taking a copy of the element its swapping, instead its merely pointing-to the element at C[i]; which means you're effectively losing that data.

The cleanest way to do this is to define your own comparison predicate, then you can pass it to std::sort, and not worry about having to reinvent your own swap/sort algorithms.

#include <iostream>
#include <algorithm>
#include <vector>

struct test
{
    int size;
};

//test comparison predicate
bool test_less(const test& lhs, const test& rhs)
{
    return lhs.size < rhs.size;
}

//Used by for_each to display the data
void display(const test& obj)
{
    std::cout << obj.size << ' ';
}

int main()
{
    const int length = 5;
    test blah[length] = { {10}, {3}, {103}, {31}, {23} };
    std::vector<test> foo(blah, blah+length);

    std::for_each(foo.begin(), foo.end(), display);
    std::cout << "\n\n";

    std::sort(foo.begin(), foo.end(), test_less);

    std::for_each(foo.begin(), foo.end(), display);
    std::cout << "\n\n";
} 

This post has been edited by Bench: 11 July 2010 - 10:51 AM

Was This Post Helpful? 1
  • +
  • -

#5 machoolah   User is offline

  • D.I.C Head

Reputation: -6
  • View blog
  • Posts: 87
  • Joined: 17-May 09

Re: sorting an array of user-defined class based on the value of a member

Posted 12 July 2010 - 07:23 AM

View Postsarmanu, on 11 July 2010 - 09:40 AM, said:

It won't work. Why do you want to deal with pointers?
tmp = &C[i];
C[i] = C[j];


basically tmp points to C[i], then you modify C[i] so automatically you modify the pointer, therefore tmp points to C[j] always. Your sort is also wrong, as the second loop should start from i + 1:
for (int j = i + 1 ; j < 5; j++){


Using a non-pointer approach, this would work:
#include < iostream>

using namespace std;

class cTest{
public:
	int ele[10];
	int size;
};

cTest C[5];

int main (){
	C[0].size = 10;
	C[1].size = 3;
	C[2].size = 103;
	C[3].size = 31;
	C[4].size = 23;  
	cTest tmp;
	for (int i = 0; i < 4; i++){
		for (int j = i + 1 ; j < 5; j++){
			if (C[i].size > C[j].size){
				tmp = C[i];
				C[i] = C[j];
				C[j] = tmp;
			}
		}
	}

	for (int i = 0; i < 5; i++)
		cout << C[i].size << " ";

	return 0;
}


But you have some bad practices here: C is global. There is no need for it to be global. You also use raw arrays. Better use std::vector. The easiest way to do this would be to call std::sort on a vector (works with raw arrays too) of cTest. Not that you have to overload operator < if you want to use std::sort in this way:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class cTest
{
private:
	int ele[10];
	int size;
public:
	cTest(const int size)
	{
		this->size = size;
	}

	int getSize() const
	{
		return size;
	}

	bool operator<(const cTest &t) const
	{
		return size < t.size;
	}
};

int main ()
{
	std::vector<cTest> C;
	C.push_back(cTest(10));
	C.push_back(cTest(3));
	C.push_back(cTest(103));
	C.push_back(cTest(31));
	C.push_back(cTest(23));

	std::sort(C.begin(), C.end());
	for (size_t i = 0; i < C.size(); i++)
		std::cout << C[i].getSize() << " ";

	return 0;
}



Thanks, I appreciate your help, I totally forgot about vectors, and thanks for pointing out the issue I had with the pointers. Vectors couldn't help me much because when I implemented the vector version, the computational time of my algorithm soared 11 times! I am developing a mathematical algorithm and computational time is not something I would want to sacrifice for a beautifully written piece of code. (Thus the global variable C). But looking at your response and obviously the time you took to explain everything, I can't help saying how much I am grateful to you.
Was This Post Helpful? -1
  • +
  • -

#6 machoolah   User is offline

  • D.I.C Head

Reputation: -6
  • View blog
  • Posts: 87
  • Joined: 17-May 09

Re: sorting an array of user-defined class based on the value of a member

Posted 12 July 2010 - 07:40 AM

View PostBench, on 11 July 2010 - 09:48 AM, said:

Your swap algorithm is not taking a copy of the element its swapping, instead its merely pointing-to the element at C[i]; which means you're effectively losing that data.

The cleanest way to do this is to define your own comparison predicate, then you can pass it to std::sort, and not worry about having to reinvent your own swap/sort algorithms.

#include <iostream>
#include <algorithm>
#include <vector>

struct test
{
    int size;
};

//test comparison predicate
bool test_less(const test& lhs, const test& rhs)
{
    return lhs.size < rhs.size;
}

//Used by for_each to display the data
void display(const test& obj)
{
    std::cout << obj.size << ' ';
}

int main()
{
    const int length = 5;
    test blah[length] = { {10}, {3}, {103}, {31}, {23} };
    std::vector<test> foo(blah, blah+length);

    std::for_each(foo.begin(), foo.end(), display);
    std::cout << "\n\n";

    std::sort(foo.begin(), foo.end(), test_less);

    std::for_each(foo.begin(), foo.end(), display);
    std::cout << "\n\n";
} 


Thanks for your help. It's really pleasing to see people like you are still around to spend time and help others who're in need. I actually decided to punt on the sorting part of my code for now because the benefits apparently are not worth the time it takes.
Was This Post Helpful? 0
  • +
  • -

#7 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: sorting an array of user-defined class based on the value of a member

Posted 12 July 2010 - 09:38 AM

View Postmachoolah, on 12 July 2010 - 09:40 AM, said:

I actually decided to punt on the sorting part of my code for now because the benefits apparently are not worth the time it takes.



I really don't understand this. Sorting is simple in C++. HEre is a list of object sorted in two ways: by "year" and by "length of the name":
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>

using namespace std;

struct MyStruct {
    string name;
    int year;
};

bool compare_by_year(const MyStruct& first, const MyStruct& second) {
    return first.year < second.year;
}

bool compare_by_name_length(const MyStruct& first, const MyStruct& second) {
    return first.name.length() < second.name.length();
}


int main() {
    MyStruct data[] = {
        { "Fra Angelico", 1387 },
        { "Michelangelo Merisi da Caravaggio", 1571 },
        { "Tiziano Vecellio", 1477 },
        { "Leonardo da Vinci", 1452 },
        { "Donato di Niccolo di Betto Bardi", 1386 },
    };
    size_t data_size = sizeof(data)/sizeof(*data);

    cout << "\n --- Data unordered ---- " << endl;
    for(int i = 0; i < data_size; ++i) {
        cout << setw(35) << left << data[i].name << ": " << data[i].year << endl;
    }
    
    sort(data, data + data_size, compare_by_year);

    cout << "\n --- Data by year ---- " << endl;
    sort(data, data + data_size, compare_by_year);
    for(int i = 0; i < data_size; ++i) {
        cout << setw(35) << left << data[i].name << ": " << data[i].year << endl;
    }


    cout << "\n --- Data by name length ---- " << endl;
    sort(data, data + data_size, compare_by_name_length);
    for(int i = 0; i < data_size; ++i) {
        cout << setw(35) << left << data[i].name << ": " << data[i].year << endl;
    }


    return 0;
}


What is hard about that? You create a "predicate" (a function that returns true or false) function or functor to tell if one item is "in front of" the other. You give std::sort() an iterator for the beginning and end of the collection, and the predicate and away you go. Simple. What is "not worth the time it takes" you don't have 3mins to write the code to sort your data?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1