0

C++如何利用模板对向量进行排序

嗨，伙计们，感谢您查看我的问题。

我有一个这样的 Templates.h 文件..

/* 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;
}

然后我上了这门课

Map2D

关于 Map2D..

class Map2D
{
protected:
int x;
int y;

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

在我的 main.cpp 中，我得到了 Map2D 的矢量类

vector<Map2D> map2d;

所以现在我需要按 X Ascending 对其进行排序.. 我如何利用模板文件对其 X Ascending 的向量进行排序.. 考虑到我稍后需要重载​​另一个 DESCENDING..

通常我会使用

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

并且 sortByX 将是一个由 it () 运算符重载的结构。

但现在的问题是，因为我得到了一个小于和大于的模板。我如何利用它通过 Templates.H 的模板通用函数通过升序对 X 进行排序，然后通过降序对另一个 X 进行排序。

更新：

我想我需要重载类 Map2D 运算符 > ， < 和 ==

但我的问题是如何在 MyTemplates.h 函数的帮助下重载它，例如 lesserThan 、greaterThan、equals

谢谢。

4

8 回答 8

6

为您的类或更简单的重载定义一个比较器operator<()（无论如何您都需要为模板工作）。

首先，修复您的模板：

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);
}

接下来，在你的类上定义一个 operator<()。

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));
    };
}

现在只需调用排序：

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

使用您的 lessThan 模板调用：

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

或您的大于模板：

std::sort(map2d.begin(), map2d.end(), greaterThan<Map2D>);
于 2012-11-16T08:41:52.083 回答
4

在 C++11 中，您可以编写一个 lambda 函数来执行此操作。

使用 boost，如果你想要一个“即时的一步”函子，它必须是这样的：

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

不确定这是否会完全有效。（第 2 次和第 3 次绑定会正确转换为占位符吗？）更容易编写一个非常通用的仿函数来组合您正在尝试做的事情，即从您的类中提取某些内容（转换）然后将其传递给谓词。

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> ) );

应该可以工作，并且您保持 Comparator 通用。

（不确定 boost 是否已经提供了类似的东西）。

于 2012-11-16T08:45:48.387 回答
4

您的代码存在一些问题：

  1. 类末尾缺少分号。
  2. 您的比较模板应该返回bool而不是T.

  3. 您错过了班级中的比较运算符：

    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 */ }

    或修复您的模板以仅operator<()用于所有比较（顺便说一句，这是一种常见的做法）。

当您在上面修复时，您只需使用这样的模板：

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

顺便说一句，您不需要自定义模板来以如此简单的方式对您的课程进行排序。重用 STL 中已有的内容：

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

您可以在功能标题中找到它们。您也不能operator==()用于排序，但它可能对C++11 中引入的无序容器有用。

编辑：如果您对 Map2D 类的排序算法是固定的（小于不随时间变化的），那么我建议您遵循我的答案。否则，如果现在您想按 X 排序并在几行后按 Y 排序，那么@MikeSeymour 答案可能更适合您的需求。

于 2012-11-16T08:48:58.830 回答
2

如果你在 C++11 中，你可以这样写：

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

否则你必须实现比较函子，即

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

接着

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

但实际上，使用 lessThan、greaterThan 并不是一个好样式，因为您可以直接比较 x。如果你想对 Map2D 进行一些特殊的比较，最好只为 Map2D 对象制作这些比较函数。

更新：您也可以只使用函数指针作为比较器，即：

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

接着

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

但是您可能会损失一些性能（请参阅下面的评论）。

于 2012-11-16T08:58:52.543 回答
1

你真的不能。您需要定义函子（函数或operator()适当重载的类）来执行您需要的特定对象成员比较，而您的函数模板不这样做。你需要类似的东西：

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());

在 C++11 中，lambda 可以为您节省一些输入：

std::sort(map2d.begin(),map2d.end(),[](Map2D const & a, Map2D const & b) {
        return a.get_X() < b.get_X();
    });
于 2012-11-16T08:43:32.697 回答
1

您首先需要重载运算符<，>并与您的模板==一起使用：Map2D

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
}

完成后，您只需使用它：

sort(map2d.begin(),map2d.end(),lessThan<Map2D>);
于 2012-11-16T08:45:08.450 回答
0 
sort(map2d.begin(),map2d.end(),lessThan<map2d>);

请注意，lessThan 是一个应该返回而不是类型的 T 值的谓词函数bool

一些额外的解释：

// 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();
}
于 2012-11-16T08:41:22.770 回答
0

一个好方法，我不认为它是最好的。您可以在类中重载运算符 (<) & (!=)。如果您只想对 X 进行排序。并且仅sort(map2d.begin(), map2d.end())用于升序。和sort(map2d.rbegin(), map2d.rend())下降..这解决了你的问题。

或者：您可以创建 2 个函数来比较 1 与 x 相关和与 Y 相关的其他函数。如：

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);

对于 Y 来说也是如此。不确定是否map2d.rbegin()会按顺序进行排序，或者您也必须自己进行。

于 2012-11-16T08:43:07.900 回答