STL中自定义排序的使用

参考
http://blog.csdn.net/aastoneaa/article/details/8471722
http://blog.csdn.net/guang11cheng/article/details/7556697
http://blog.csdn.net/hzyong_c/article/details/7791415

强烈推荐文章
http://blog.csdn.net/bz201/article/details/543001

    如果要自己定义STL容器的元素类最好满足STL容器对元素的要求
    必须要求：
    

引用

1、Copy构造函数
     2、赋值=操作符
     3、能够销毁对象的析构函数

    另外：
   

引用

1、可用的缺省构造函数，序列型容器必须，用于初始化元素
     2、==操作符定义，用于判断相等
     3、<操作符定义，关联型容器必须，用于缺省排序

    你可在struct內加入 operator < ,就可以使struct有排序能力.因為而你的pcd struct內沒有指針,所以不須要有copy constructor和copy assignment, 編譯器會為你提供的, 你不須要自己做的.當你要排序時只要寫 sort( obj.begin(), obj.end() )就可.

   下面是std::sort函数，有两个版本：

template <class RandomAccessIterator>
void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

   sort函数有以下特征：
    1. 要求输入一个范围[first, last)
    2. 随机迭代器，能用此算法的容器是支持随机访问的容器：vector, deque, string。
    3.第一个版本使用operator<进行比较，默认升序排序，第二个版本使用comp做比较.
关于参数comp，comp带两个同类型的参数，如果第一个参数排在第二个参数前面，返回true，否则返回false
     它可以是函数指针，也可以是函数对象。函数指针好理解，何谓函数对象？
函数对象（Function Object），是重载了operator()函数的类（或结构体）实例化出来的对象，使用起来像函数，又叫仿函数。

    STL本身提供了几个比较函数,下面这些都是仿函数：

引用

    less(小于)
    greater(大于)
    equal_to(等于)
    not_equal_to(不相等)
    less_equal(小于等于)
    greater_equal(大于等于)

    当容器元素为内建类型时可以使用，注意使用的格式，要加模版参数（由于是模板类）和后面的()，如下：

sort(vec.begin(), vec.end(), less<int>());

    下面看看这3种方法的实现：

// 排序元素，比较的对象
struct Person
{
  Person(int id, const string& name, int age): id_(id), name_(name), age_(age)
  {}
  
  int id_;
  string name_;
  int age_;
};

// 方式1：重载operator<用于排序时的比较(写在函数体内)
bool operator< (const Person& rt)
{
  return this->id_ < rt.id_;
}

// 排序函数写法，默认调用operator<
sort(members.begin(), members.end());

// 方式2：写比较函数
bool CompAge(const Person& pl, const Person& pr)
{
  return pl.age_ < pr.age_;
}

// 排序时传入比较函数指针
sort(members.begin(), members.end(), CompAge);

// 方式3：仿函数
struct CompName
{
  bool operator()(const Person& pl, const Person& pr)
  {
    return pl.name_ < pr.name_;
  }
};

// 排序时传入函数对象
sort(members.begin(), members.end(), CompName());

    用函数对象代替函数指针的优点：
    1. 函数对象可以存储中间结果在数据成员中，而函数想要存中间结果须要设全局变量或静态变量，这个是我们不想要的。
    2. 在函数对象中编译器可以实现内联调用，从而提升性能。


    下面看一个函数对象的扩展应用

// 利用函数对象实现升降排序
struct CompNameEx{
  CompNameEx(bool asce) : asce_(asce)
  {}
  bool operator()(const Person& pl, const Person& pr)
  {
    return asce_ ? pl.name_ < pr.name_ : pr.name_ < pl.name_;<span style="white-space:pre">	</span>// 《Eff STL》条款21: 永远让比较函数对相等的值返回false
  }
private:
  bool asce_;
};
// 使用仿函数排序(升降序)
sort(members.begin(), members.end(), CompNameEx(false));

    C++中当 vector 中的数据类型为基本类型时我们调用std::sort函数很容易实现 vector中数据成员的升序和降序排序，然而当vector中的数据类型为自定义结构体类型时，我们该怎样实现升序与降序排列呢？
对运算符号进行重载

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct TItem
{
    int m_i32Type;
    int m_i32ID;

    bool operator <(const TItem& rhs) const // 升序排序时必须写的函数
    {
        return m_i32Type < rhs.m_i32Type;
    }
    bool operator >(const TItem& rhs) const // 降序排序时必须写的函数
    {
        return m_i32Type > rhs.m_i32Type;
    }
};

int main()
{
    vector<TItem> stItemVec;

    TItem stItem1;
    stItem1.m_i32Type = 1;
    stItem1.m_i32ID = 1;

    TItem stItem2;
    stItem2.m_i32Type = 2;
    stItem2.m_i32ID = 2;

    TItem stItem3;
    stItem3.m_i32Type = 3;
    stItem3.m_i32ID = 3;

    TItem stItem4;
    stItem4.m_i32Type = 2;
    stItem4.m_i32ID = 4;

    stItemVec.push_back(stItem1);
    stItemVec.push_back(stItem2);
    stItemVec.push_back(stItem3);
    stItemVec.push_back(stItem4);

    // 升序排序
    sort(stItemVec.begin(), stItemVec.end(), less<TItem>()); 
    // 或者sort(ctn.begin(), ctn.end());   默认情况为升序

    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);

    printf("--\n");

    // 降序排序
    sort(stItemVec.begin(), stItemVec.end(), greater<TItem>());

    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);

    return 0;
}

全局的比较函数

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct TItem
{
    int m_i32Type;
    int m_i32ID;
};

bool lessmark(const TItem& stItem1, const TItem& stItem2)
{
    return stItem1.m_i32Type < stItem2.m_i32Type;
}

bool greatermark(const TItem& stItem1, const TItem& stItem2)
{
    return stItem1.m_i32Type > stItem2.m_i32Type;
}

int main()
{
    vector<TItem> stItemVec;

    TItem stItem1;
    stItem1.m_i32Type = 1;
    stItem1.m_i32ID = 1;

    TItem stItem2;
    stItem2.m_i32Type = 2;
    stItem2.m_i32ID = 2;

    TItem stItem3;
    stItem3.m_i32Type = 3;
    stItem3.m_i32ID = 3;

    TItem stItem4;
    stItem4.m_i32Type = 2;
    stItem4.m_i32ID = 4;

    stItemVec.push_back(stItem1);
    stItemVec.push_back(stItem2);
    stItemVec.push_back(stItem3);
    stItemVec.push_back(stItem4);

    sort(stItemVec.begin(), stItemVec.end(), lessmark); //升序排序

    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);


    printf("--\n");

    sort(stItemVec.begin(), stItemVec.end(), greatermark); //降序排序


    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);


    return 0;
}

函数对象

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct TItem
{
    int m_i32Type;
    int m_i32ID;
};

class CompLess
{
public:
    bool operator ()(const TItem& stItem1, const TItem& stItem2)
    {
        return stItem1.m_i32Type < stItem2.m_i32Type;
    }
};

class CompGreater
{
public:
    bool operator ()(const TItem& stItem1, const TItem& stItem2)
    {
        return stItem1.m_i32Type > stItem2.m_i32Type;
    }
};

int main()
{
    vector<TItem> stItemVec;

    TItem stItem1;
    stItem1.m_i32Type = 1;
    stItem1.m_i32ID = 1;

    TItem stItem2;
    stItem2.m_i32Type = 2;
    stItem2.m_i32ID = 2;

    TItem stItem3;
    stItem3.m_i32Type = 3;
    stItem3.m_i32ID = 3;

    TItem stItem4;
    stItem4.m_i32Type = 2;
    stItem4.m_i32ID = 4;

    stItemVec.push_back(stItem1);
    stItemVec.push_back(stItem2);
    stItemVec.push_back(stItem3);
    stItemVec.push_back(stItem4);

    sort(stItemVec.begin(), stItemVec.end(), CompLess()); //升序排序

    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);

    printf("--\n");

    sort(stItemVec.begin(), stItemVec.end(), CompGreater()); //降序排序

    for (size_t i = 0; i < stItemVec.size(); i++)
        printf("type: %d, id: %d\n", stItemVec[i].m_i32Type,stItemVec[i].m_i32ID);

    return 0;
}