0

C++ How to Sort Vector making use of Template

Hi Guys, thanks for looking at my question.

I got a Templates.h file that goes this way..

/* Template Less Than */

template<typename T>
bool lessThan(T a,T b)
{
return a<b;
}

/* Template greater Than */

template<typename T>
bool greaterThan(T a,T b)
{
return a>b;
}

/* Template Equals */

template<typename T>
bool equals(T a,T b)
{
return a==b;
}

Then i got this class

Map2D

About Map2D..

class Map2D
{
protected:
int x;
int y;

public:
Map2D();
Map2D(int,int);
int getX();
int getY();
};

At my main.cpp i got a vector class of Map2D

vector<Map2D> map2d;

So now i need to sort it by X Ascending.. how do i make use of the template file to do a sort on the vector of it X Ascending.. Consider i will need overload another for DESCENDING later..

Normally i will use 

sort(map2d.begin(),map2d.end(),sortByX);

and sortByX will be a struct with overload by it () operator.

But the question now is since i got a template that is lesser than and greater than.. how can i make use of it to sort X by ascending and then another X by descending with the template generic function of Templates.H .

Updates:

I think i need to overload the class Map2D operator > , < and ==

but my question is how do i overload it with the help of MyTemplates.h function such as lesserThan , greaterThan, equals

Thanks.

iammilind
  • 68,093
  • 33
  • 169
  • 336
user1578897
  • 179
  • 2
  • 7
  • 16
  • I'm sorry, do you imply that you want to do it in compile-time? Or you just want to use your templated functions in runtime? – SingerOfTheFall Nov 16 '12 at 08:40
  • @SingerOfTheFall want to create a function that can make use of the greaterThan lesserThan to sort by int x in ascending and descending mode – user1578897 Nov 16 '12 at 08:41
  • Your class is missing a semicolon at the end – Mateusz Pusz Nov 16 '12 at 08:42
  • 1
    You may wish to know that your lessThan template is, for all intents and purposes, **identical** to std::less. What are you reinventing the wheel for? (and you still need an `operator<()` for your Map2D class to make this work as-written. – WhozCraig Nov 16 '12 at 08:43
  • lessThan should return bool, by the way. – CashCow Nov 16 '12 at 08:52
  • possible duplicate of [How to use std::sort with a vector of structures and compare function?](http://stackoverflow.com/questions/328955/how-to-use-stdsort-with-a-vector-of-structures-and-compare-function) – WhozCraig Nov 16 '12 at 08:54
  • 1
    Contrary to apparently wide opinions, you do NOT need to overload `operator >()` and `operator ==()` to perform `greaterThan and `equals if your templates are coded correctly and `operator <()` follows strict ordering as it should. – WhozCraig Nov 16 '12 at 09:03
  • I could edit this to make it a better question that highlights the main point but that would be pre-empting what I think the questioner is asking. – CashCow Nov 16 '12 at 10:06
  • @CashCow how to edit to make my question better. – user1578897 Nov 16 '12 at 12:37
  • If you were to state that wanted a predicate that you could where you could specify calling getX() out of your objects and then comparing them with a predicate (your less is an example, but the concept is you can specify the predicate). Assuming you have such a predicate, how can you construct the "lambda" expression in C++03 (with boost libraries if necessary). e.g. my first "attempt" in my answer shows what you are trying to do. – CashCow Nov 16 '12 at 13:36

8 Answers8

6

Define a comparator for your class or simpler, a operator<() overload (which you need to do anyway for your templates to work).

First, fix your templates:

template<typename T>
bool lessThan(const T& a, const T& b)
{
    return a<b;
}

template<typename T>
bool greaterThan(const T& a, const T& b)
{
    return b<a;
}

template<typename T>
bool equals(const T& a, const T& b)
{
    return !(a<b || b<a);
}

Next, define an operator<() on your class.

class Map2D
{
protected:
    int x;
    int y;

public:
    Map2D();
    Map2D(int,int);
    int getX();
    int getY();

    // this sample sorts on X dominantly, and Y if X is the same
    bool operator <(const Map2D& obj) const
    {
        return (x < obj.x || (x == obj.x && y < obj.y));
    };
}

Now just invoke sort:

std::sort(map2d.begin(), map2d.end());

Invoke using your lessThan template as such:

std::sort(map2d.begin(), map2d.end(), lessThan<Map2D>);

Or your greaterThan template:

std::sort(map2d.begin(), map2d.end(), greaterThan<Map2D>);
WhozCraig
  • 65,258
  • 11
  • 75
  • 141
4

In C++11 you could write a lambda function to do it.

Using boost, if you want a "one-step on the fly" functor it would have to be something like:

bind( less<int>, bind(&Map2D::getX(),_1), bind(&Map2D::getX(),_2) )
// or your lessThan<int> which already exists in C++ as less<int>

Not sure if that will work exactly. (Will the 2nd and 3rd binds convert properly to placeholders?) Easier to write a very generic functor that combines what you are trying to do, i.e. extract something from your class (a transformation) then pass that into the predicate.

template< typename Trans, typename Pred >
struct Comparator
{
    Comparator( Trans t , Pred p ) : trans( t ), pred ( p )
    {
    }

    template< typename T >
    bool operator()( T const& t1, T const& t2 ) const
    {
         return pred( trans(t1), trans(t2) );
    }
private:
    Trans trans;
    Pred pred;
};


template< typename Trans, typename Pred >
Comparator< Trans, Pred > makeComparator( Trans t, Pred p )
{
     return Comparator( t, p );
}

// then in your code

std::sort( map2d.begin(), map2d.end(), 
    makeComparator( boost::bind( &Map2D::getX(), _1 ), lessThan<int> ) );

should work and you've kept Comparator generic.

(Not sure if boost already offers something like this).

CashCow
  • 30,981
  • 5
  • 61
  • 92
4

There are a few issues with your code:

  1. Class is missing semicolon at the end.
  2. Your comparison templates should return bool instead of a T.

  3. You miss comparison operators inside your class:

    bool operator<(const Map2D &m) const {return /* some code here */ }
bool operator>(const Map2D &m) const {return /* some code here */ }
bool operator==(const Map2D &m) const {return /* some code here */ }

    or fix your templates to only use operator<() for all the comparisons (which is a common practice BTW).

When you fix above you just use your templates like that:

sort(map2d.begin(),map2d.end(), lessThan<Map2D>);
sort(map2d.begin(),map2d.end(), greaterThan<Map2D>);

BTW, you do not need custom templates to sort your class in such an easy way. Reuse what is already in STL:

sort(map2d.begin(),map2d.end()); // less
sort(map2d.begin(),map2d.end(), std::greater<Map2D>());

You can find those in functional header. You also cannot use operator==() for sorting but it may be useful for unordered containers introduced in C++11.

EDIT: If your sorting algorithms for Map2D class are fixed (what is lessThan does not change with time) than I suggest following my answer. Otherwise if now you want to sort by X and after a few lines by Y than @MikeSeymour answer may be better suited to your needs.

Mateusz Pusz
  • 1,363
  • 1
  • 9
  • 16
2

If you are in C++11, you can write something like this:

std::sort(map2d.begin(), map2d.end(), [](const Map2D& a, const Map2D& b) {
    return lessThan(a.getX(), b.getX()); } ); // accending
std::sort(map2d.begin(), map2d.end(), [](const Map2D& a, const Map2D& b) {
    return greaterThan(a.getX(), b.getX()); }); // decending

Otherwise you have to implement compare functor, i.e

struct compare
{
    bool operator () (const Map2D& a, const Map2D& b)
    {
        return lessThan(a.getX(), b.getX());
    }
};

and then

std::sort(map2d.begin(), map2d.end(), compare());

But really it isn't a good style to have lessThan, greaterThan, since you can compare x directly. And if you want some special comparison for Map2D maybe it is better to make these compare functions only for Map2D objects.

Upd: you can also use just function pointer as your comparator, i.e:

bool compare(const Map2D& a, const Map2D& b)
{
    return lessThan(a.getX(), b.getX());
}

and then

std::sort(m.begin(), m.end(), compare);

But you may loss some performance (see comments below).

DikobrAz
  • 3,557
  • 4
  • 35
  • 53
  • That looks like an overkill for such a simple task. – Mateusz Pusz Nov 16 '12 at 09:26
  • @MateuszPusz: What do you mean? This is exactly how to provide a custom comparator to `std::sort`. – Mike Seymour Nov 16 '12 at 09:32
  • @MikeSeymour Indeed such a comparator will work with provided implementation. However in my opinion it is not a good practice to unhide all class implementation via getters in order to provide all data to some external function to do the comparison. I think that operator<() should be preferred in all cases. Unless you cannot change the class interface of course... – Mateusz Pusz Nov 16 '12 at 09:38
  • @MateuszPusz: There are many possible ways to define an ordering on 2D points; if you did (arbitrarily) choose to overload `operator<` to order by `x`, then you'd still need a custom comparator like this to sort by `y`. – Mike Seymour Nov 16 '12 at 09:41
  • @MikeSeymour OK, I cannot disagree with that :-) – Mateusz Pusz Nov 16 '12 at 09:42
  • hi, what if i want to be using the same function compare, but able to compare by y too. can this do the same job? – user1578897 Nov 16 '12 at 13:02
  • I agree that this is a good answer and +1 for actually writing out the lambda that I had hinted at in my answer. There is no actual need to make compare a class here, you could make it a function. One tends to use a class when it holds an extra member somewhere. And operator() could be const. – CashCow Nov 16 '12 at 13:40
  • @CashCow: One also tends to use a class so that the function can be resolved from the template parameter at compile time, making it potentially more efficient to call. A function will decay to a pointer, and may well only be resolvable at run time. Or at least, I tend to, and so does the C++ library with classes like `std::less`. – Mike Seymour Nov 16 '12 at 15:12
  • @user1578897: I recommend you to implement compare_by_x and compare_by_y functors similarly to compare functor above (or to use lambdas). You can simply implement them as functions, see CashCow and MikeSeymour comments. – DikobrAz Nov 17 '12 at 11:08
  • @MikeSeymour std::less derives from std::binary_function, not because it is used polymorphically (operator() is not virtual) but because this allows meta-programs to derive the parameter and return types. In actual fact if you create your own functor for this you should also derive from std::binary_function, in the same way that if you make your own iterators they should derive from std::iterator. Of course a novice is likely to make the mistake of accepting a std::binary_function and trying to call operator() on it and wonder why they get compiler errors. – CashCow Nov 19 '12 at 09:52
1

You can't really. You'll need to define functors (either functions, or classes that overload operator() appropriately) to do the particular object-member comparisons you need, and your function templates don't do that. You need something like:

struct compare_x_less {
    // NOTE: you'll need to declare `get_X() const` for this to work.
    // You should do that anyway.
    bool operator()(Map2D const & a, Map2D const & b) {
        return a.get_X() < b.get_X();
    }
};

// and similarly for `compare_x_greater` and any other comparisons you need

std::sort(map2d.begin(),map2d.end(),compare_x_less());

In C++11, lambdas can save you a bit of typing:

std::sort(map2d.begin(),map2d.end(),[](Map2D const & a, Map2D const & b) {
        return a.get_X() < b.get_X();
    });
Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • If i overload the class Map2D with the function, will i be able to sort with those generic function. – user1578897 Nov 16 '12 at 08:45
  • @user1578897: You mean if you overload `operator<` and `operator>` for `Map2D`? Yes; but you'd have to choose one arbitrary ordering (e.g. by `x` or by `y`). That may or may not make sense, depending on how else you intend to use these 2D points. – Mike Seymour Nov 16 '12 at 08:51
  • You can use not only functors and lambdas here but also plain comparison functions as long as internal state is not needed to do the operation. – Mateusz Pusz Nov 16 '12 at 09:25
  • @MateuszPusz: Indeed, any functor will do. I gave an example using a function class because that's what I always use; it's easier to inline than a function pointer, since the function itself can be deduced from the template parameter. – Mike Seymour Nov 16 '12 at 09:27
  • @Mike Seymour I also think that functors are easier to use but it does not mean you cannot use plain functions what you probably meant by your first sentence in an answer. – Mateusz Pusz Nov 16 '12 at 09:33
  • @MateuszPusz: Yes, by "functor" I meant anything callable like a function, which includes a (pointer to) a plain function. Sorry if that wasn't clear enough. – Mike Seymour Nov 16 '12 at 09:35
1

You first need to overload operators <, > and == to use Map2D with your templates: 

class Map2D
{
protected:
   int x;
   int y;
public:
   Map2D();
   Map2D(int,int);
   int getX();
   int getY();
   bool operator<(const Map2D& other)const //less then
   {
      return x < other.x;
   }
   //other operators is same manner
}

After you have done you just use it:

sort(map2d.begin(),map2d.end(),lessThan<Map2D>);
Denis Ermolin
  • 5,530
  • 6
  • 27
  • 44
0
sort(map2d.begin(),map2d.end(),lessThan<map2d>);

Be aware that lessThan is a prediacte function that should return instead of T value of type bool

Some additional explanation:

// usage
    /* Some moments to mention: if you omit third argument, default argument less<T> will be used,
    which is enough for built-in types, also you can use predicates already defined in STL:
    greater<T>, less<T> or you can provide your own predicate */
    sort(map2d.begin(),map2d.end(),lessThan<map2d>);

// header file, where we define predicats which we shall provide as argument to algorithm sort

// predicate expected by function sort has to obey the following rules:
// 1. return bool 2. accept 2 parameters

/*2 variants of predicat*/

// 1) operator< is overloaded for class T, so we can use it to compare instances of that class
template<typename T>
bool lessThan(T a,T b)
{
return a < b;
}

/* 2) operator< not overloaded, when we have to get values of class members by which we are going to compare them
this could be done in various ways, for ex. by means of getters();*/

template<typename T>
bool lessThan(T a,T b)
{
return a.getValueOfMember() < b.getValueOfMember();
}
spin_eight
  • 3,925
  • 10
  • 39
  • 61
0

A good way, I don't think it's the best. You can overload the operator (<) & (!=) in the class. If you only want to sort for X. And just use sort(map2d.begin(), map2d.end()) for ascending. and sort(map2d.rbegin(), map2d.rend()) for descending .. And that solves your problem.

OR: You can make 2 functions to compare 1 relevant to x & the other relevant to Y. As:

int cmpx(const void* A, const void *B){
    Map2D a = *(Map2D *)A;
    Map2D b = *(Map2D *)B;
    if(a.x < b.x) return -1;
    if(a.x == b.x) return 0;
    return 1;
}
// And use
qsort(map2d.begin(), (int)map2d.size(), sizeof(Map2D), cmpx);

And so for Y. Not sure if map2d.rbegin() will sort this descedingly or you'll have to do it on your own as well.

Mahmoud Aladdin
  • 536
  • 1
  • 3
  • 13
  • I think your answer is about what i looking for. overloading the class itself. But how do i overload so i can send in X or Y to compare in the class itself with the Template Function. – user1578897 Nov 16 '12 at 08:44
  • How reverse iterators that besically provide the same data but in a different order are meant to sort the container in descending order and why operator!=() is needed? – Mateusz Pusz Nov 16 '12 at 09:22