Jump to content
  • Advertisement
Sign in to follow this  
WindScar

Sorting vector of objects by given function

This topic is 3043 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I made my own vector class based on std::vector and I need a function to sorts it's objects by given function, so that call is possible:
myVector vec;
vec.push_back(Point(3,5));
vec.push_back(Point(4,6));
vec.push_back(Point(6,3));
vec.fsort(Point::getx);
So the vector is sorted by the value returned by Point::getx(). I've attempted to do it like this:
class myVector
{
   //stuff
   template <class U>
   void fsort(U (T::*func)())
   {
      //sorting algorythm
   }
}
And it works almost alright, though there are 2 problems: 1. I couldn't make it work using std::sort as I can't configure std::sort's callback to accept the function pointer, so I need to implement my own sort algorithm, and I couldn't find any good (the one I found is about 2.5x slower than std::sort). 2. When I initializate a myVector instance of a non-class type like int or double, the program doesn't compile:
Quote:
creating pointer to member function of non-class type `int'

Share this post


Link to post
Share on other sites
Advertisement
Does your myVector class inherit from std::vector?

Based on what you've posted at least, it seems to me that std::vector and std::sort() should be perfectly adequate for what you're wanting to do. Here's what the code might look like (not compiled or tested):
bool CompareX(const Point& p1, const Point& p2) { return p1.getx() < p2.getx(); }

// ...

std::vector<Point> points;

// ...

std::sort(points.begin(), points.end(), &CompareX);

Share this post


Link to post
Share on other sites
No, I don't want a function like "comparex", because that would require writing new "compare" functions everytime I store a new kind of object in the vector, or there's a new kind of variable I want to sort from. I just want the vector class totally independent from the type of object I want it to store. Passing the function pointer gives me that. Not CompareX, yes Compare(T::getx). Is that possible?

Share this post


Link to post
Share on other sites
Quote:
Original post by WindScar
No, I don't want a function like "comparex", because that would require writing new "compare" functions everytime I store a new kind of object in the vector, or there's a new kind of variable I want to sort from. I just want the vector class totally independent from the type of object I want it to store. Passing the function pointer gives me that. Not CompareX, yes Compare(T::getx). Is that possible?


Assuming your compare function is simple and does something like < sometimes, > other times, etc, you can just make it a template function:


template<class T>
bool is_less(const T& t1, const T& t2) { return t1 < t2; }



As long as t1 and t2 have the appropriate operator, it works. Anyway if you really want to use an arbitrary function pointer, you can use boost::bind


class Bar
{
};

class Foo
{
public:
bool do_compare(const Bar& b1, const Bar& b2) const
{
}
};

int main(int argc, char** argv)
{
std::vector<Bar> v;
Foo comparer;
std::sort(v.begin(), v.end(), boost::bind(&Foo::compare, &comparer, _1, _2));
}




If you're using either Visual Studio 2010 Release Candidate or GCC 4.5, you can use C++0x lambdas.


std::vector<Bar> v;
std::sort(v.begin(), v.end(),
[](const Bar& b1, const Bar& b2)
{
b1.x < b2.x;
}
);

Share this post


Link to post
Share on other sites
Forgoing boost et al., you can use a comparator object with std::sort:


#include <algorithm>
#include <cstdlib>
#include <iostream>

template <class T>
class myVector
{
template <class T, class U>
struct mappedCompare {
U (T::*func)() const;

mappedCompare(U (T::*func)() const)
: func(func) {}

bool operator()(const T& l, const T& r) const {
return (l.*func)() < (r.*func)();
}
};

public:

T data[10]; // hack for demo

template <class U>
void fsort(U (T::*func)() const)
{
std::sort(data, data + 10, mappedCompare<T, U>(func));
}
};

class widget { // hack for demo
int width, height;

public:

widget()
: width(std::rand() % 100), height(std::rand() % 100) {}

int getheight() const {
return height;
}
};

int main() { // hack for demo
myVector<widget> v;

v.fsort(&widget::getheight);

for(int i = 0; i < 10; ++i)
std::cout << i << ": " << v.data.getheight() << "\n";
}

Share this post


Link to post
Share on other sites
Yay! That's cool. But it still doesn't solve the second problem. If you create a myVector with a basic type, the compiler will give the error:

Quote:
error: creating pointer to member function of non-class type `int'

Share this post


Link to post
Share on other sites
Perhaps you should move mappedCompare out of myVector and just allow any comparator to be passed:


template <class U>
void fsort(U comparator)
{
std::sort(data, data + 10, comparator);
}

void fsort()
{
std::sort(data, data + 10);
}

// usage
myVector<widget> v;
v.fsort(mappedCompare<widget, int>(&widget::getheight));

myVector<int> v2;
v.fsort();



Btw, why are you rewriting std::vector? :)

Share this post


Link to post
Share on other sites
Well that'd work but that'd also be some ugly syntax to write, isn't there other workaround?

It's for adding some extra functions like that spetial sort, a null pointer remover, a operator<< overload ;
Heeeeelp!

Share this post


Link to post
Share on other sites
Quote:
Original post by WindScar
For adding some extra functions like that spetial sort, a null pointer remover, a operator<< overload ;
Heeeeelp!
All of these could be implemented as free functions taking a std::vector as a parameter, and indeed, this would be much more sensible.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!