Sign in to follow this  
WindScar

Sorting vector of objects by given function

Recommended Posts

WindScar    144
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
jyk    2094
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
WindScar    144
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
cache_hit    614
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
mattd    1078
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[i].getheight() << "\n";
}

Share this post


Link to post
Share on other sites
WindScar    144
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
mattd    1078
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
WindScar    144
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
swiftcoder    18437
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
WindScar    144
I don't think so, it just seems more intuitive for me to call vec.sort() than sort(vec), and I actually'd preffer everything related to vector to be in the vector class, not free outside.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
I don't think so, it just seems more intuitive for me to call vec.sort() than sort(vec), and I actually'd preffer everything related to vector to be in the vector class, not free outside.
The approach you're taking here isn't really in keeping with the design philosophy of the C++ standard library or with what (I think) most C++ developers would consider to be 'best practices'. You can certainly do what you're describing, but it kind of seems like you're fighting the language here a little bit.

Anyway, you might give this article a read (it talks about some issues that are relevant to this discussion).

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by WindScar

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


These are best implemented as free functions:
template < class T > bool is_null(T * p) { return p == NULL: };
std::remove_if(v.begin(), v.end(), is_null);

template < class T, class A >
std::ostream & operator<<(std::ostream & os, vector<T,A> & v) {
//
}

// and the sort example with std::sort


In other words, instead of trying to reimplement the std::vector, use the one provided by STL, and define extra behavior in a wrapper class that contains vector as a member.

struct Points {
void sort() {
std::sort(v.begin(), v.end(), my_comparator());
}
void print(std::ostream & os) {
os << v;
}
void remove_null() {
v.erase(std::remove_if(v.begin(), v.end(), is_null), v.end());
}
private:
std::vector<Point> v;
};

Share this post


Link to post
Share on other sites
WindScar    144
Jyk, the article has interessing points but it's just about where to place the functions. Maybe it would be better to create just additional functions, but it's something to think about later. Anyway, simply moving the function to outside does actually solve the thread problem, thank you.
EDIT: can't yet believe it's workin, thank you very much *-*

Antheus, that's exactly what I did, actually.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this