C / C++ / MFC

12-Sep-06 4:21

Hi,

I am trying to apply the sort() algorithm on a vector of structs. I want the vector to be sorted according to one of the struct fields. I see two ways in which this could be done, and neither seems to work.

Here are the struct and the vector:

<br />
	struct item_calculation <br />
	{<br />
		int item_num;<br />
		float weight;<br />
		float contribution;<br />
		float prediction;<br />
	};<br />
<br />
               vector<item_calculation> found_items;

I want the vector "found_items" to be sorted by the field "prediction".

The first way to do the task is defining a comparison function and sending it do sort() as a parameter:

	bool less_than( item_calculation a, item_calculation b ) {<br />
		return a.prediction < b.prediction;<br />
	};              <br />
.<br />
.<br />
.<br />
	sort(found_items.begin(), found_items.end(), less_than);

This results with the errors: "error C3867: 'CCFEApp::less_than': function call missing argument list; use '&CCFEApp::less_than' to create a pointer to member."; "error C2780: 'void std::sort(_RanIt,_RanIt)' : expects 2 arguments - 3 provided"

when using "&CCFEApp::less_than" I get the error: "error C2914: 'std::sort' : cannot deduce template argument as function argument is ambiguous".

The second way to do the task is by overloading the "<" operator:

bool operator<(item_calculation a, item_calculation b) {<br />
    return a.prediction < b.prediction;<br />
};

gives: "error C2804: binary 'operator <' has too many parameters".

After changing to:

<br />
	bool operator<(item_calculation b) {<br />
		return prediction < b.prediction;<br />
	};

one gets: "error C2065: 'prediction' : undeclared identifier".

I would apreciate any help.

Thanks,
Avi.

P.S. I am working under Visual Studio 2005.

Rob Caldecott12-Sep-06 4:29

Rob Caldecott

12-Sep-06 4:29

I just checked some similar sort code that I use and the only difference is that my sort function takes two const reference params. Try changing your sort function:

bool less_than(const item_calculation& a, const item_calculation& b )
{
return a.prediction < b.prediction;
};

avimitrani12-Sep-06 5:26

12-Sep-06 5:26

I have already changed the definition adding the consts and references. this doesn't make a difference.

Avi.

Rob Caldecott12-Sep-06 5:32

Rob Caldecott

12-Sep-06 5:32

Avi,

Weird, as I just created a test console app (using VS2005) and it builds without errors:

#include "stdafx.h"
#include <vector>
#include <algorithm>

struct item_calculation
{
	int item_num;
	float weight;
	float contribution;
	float prediction;
};

bool less_than(const item_calculation& a, const item_calculation& b)
{
	return a.prediction < b.prediction;
}; 

int _tmain(int argc, _TCHAR* argv[])
{
	std::vector<item_calculation> items;
	// Add items to the vector here...
	std::sort(items.begin(), items.end(), less_than);
}

avimitrani12-Sep-06 6:00

12-Sep-06 6:00

Thanks for the effort, Robert.

This problem buggs me exactly because the code seems to me to be correct.

In my case all the declarations (struct, function) are made inside a class definition, and sort() is called from inside a member fonction. can this make any difference?

Zac Howland12-Sep-06 6:29

12-Sep-06 6:29

avimitrani wrote:
In my case all the declarations (struct, function) are made inside a class definition, and sort() is called from inside a member fonction. can this make any difference?

Yes. Move the overriden operator< outside of your app class and declare it as a friend to your app class.

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

using namespace std;

class MyClass
{
public:
        MyClass() { initMe(); }

        void sortMe() { sort(found_items.begin(), found_items.end()); }
        void showMe() { copy(found_items.begin(), found_items.end(), ostream_iterator<item_calculation>(cout, " ")); }
private:
        struct item_calculation
        {
                int item_num;
                float weight;
                float contribution;
                float prediction;

                item_calculation() : item_num(0), weight(0.0), contribution(0.0), prediction(0.0)
                {}

                item_calculation(int in, float w, float c, float p) : item_num(in), weight(w), contribution(c), prediction(p)
                {}

        };

        vector<item_calculation> found_items;

        void initMe()
        {
                for (int i = 10; i > 0; --i)
                {
                        float f = static_cast<float>(i);
                        item_calculation ic(i, f, f, f);
                        found_items.push_back(ic);
                }
        }

        friend bool operator< (const item_calculation& lhs, const item_calculation& rhs);
        friend ostream& operator<<(ostream& os, const item_calculation& ic);
};
bool operator< (const MyClass::item_calculation& lhs, const MyClass::item_calculation& rhs)
{
        return lhs.prediction < rhs.prediction;
}

ostream& operator<<(ostream& os, const MyClass::item_calculation& ic)
{
        os << ic.item_num;
        return os;
}

int main()
{
        MyClass me;
        me.showMe();
        cout << endl;
        me.sortMe();
        me.showMe();
}

If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week

Zac

avimitrani12-Sep-06 7:10

12-Sep-06 7:10

Thanks again, Zac

Your suggestion strikes me as the most correct way to do it.

I managed to compile the project by using a different solution:

struct item_calculation // To be used inside 'recommend'<br />
{<br />
    int item_num;<br />
    float weight;<br />
    float contribution;<br />
    float prediction;<br />
    bool operator<(const item_calculation &b) {<br />
        return prediction < b.prediction;<br />
    };<br />
};

This should work too, but I'll opt for the friend function option.

Many thanks,
Avi.

Zac Howland12-Sep-06 8:11

Re: Sorting a vector of a user defined type [modified]

12-Sep-06 8:11

The only problem you will run into is if the item_calculation struct is a private inner class, the opeartor< will be "private", so it won't be able to be used outside the outer class (that is, sort may have issues with it). That goes away if it is a public inner class, or if you override the operators outside the class.

There are other reasons to override binary operators outside the class they operate on, but that goes beyond the scope of this question.

If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week

Zac

Zac Howland12-Sep-06 4:30

12-Sep-06 4:30

Your code just needs to be modified slightly:

// struct definition
struct item_calculation
{
	int item_num;
	float weight;
	float contribution;
	float prediction;

	item_calculation() : item_num(0), weight(0.0), contribution(0.0), prediction(0.0)
	{}
};

// this is actually a better way of doing it
bool operator< (const item_calculatioin& lhs, const item_calculation& rhs)
{
	return lhs.prediction < rhs.prediction;
}

// sort call
sort(found_items.begin(), found_items.end());	// less<item_calculation> is the default predicate

-- modified at 10:49 Tuesday 12th September, 2006

If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week

Zac

avimitrani12-Sep-06 5:14

12-Sep-06 5:14

what is the meaning of the added lines:

item_calculation() : item_num(0), weight(0.0), contribution(0.0), prediction(0.0)	<br />
{}

Thanks,
Avi.

C^hris L^osinger12-Sep-06 5:16

C^hris L^osinger

12-Sep-06 5:16

it initializes those variables

image processing | blogging

avimitrani12-Sep-06 5:42

12-Sep-06 5:42

Why should they be initialized?

(this is the only difference between your code and mine)

Zac Howland12-Sep-06 5:40

12-Sep-06 5:40

In C++, class and struct are pretty much the same keyword (class defaults to private protection, while struct defaults to public -- that is pretty much the only major difference).

Thus, you can create constructors for structs just as you would a class. The code below creates a default constructor and initializes each variable to a value (in this case, all 0's).

avimitrani wrote:
item_calculation() : item_num(0), weight(0.0), contribution(0.0), prediction(0.0)
{}

It is almost the same as writing it this way:

item_calculation()
{
	item_num = 0;
	weight = 0.0;
	contribution = 0.0;
	prediction = 0.0;
}

except that the first case is more efficient because the members are created and initialzed at the same time.

If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week

Zac

avimitrani12-Sep-06 5:49

12-Sep-06 5:49

Yes, but why should initialization make a difference? Before I use sort() I loop over the vector, and fill thr struct fields.

Zac Howland12-Sep-06 6:17