STL中自定义排序的使用

我不是女神ヾ 2022-04-11 05:50 228阅读 0赞

参考  
\[url\]http://blog.csdn.net/aastoneaa/article/details/8471722\[/url\]  
\[url\]http://blog.csdn.net/guang11cheng/article/details/7556697\[/url\]  
\[url\]http://blog.csdn.net/hzyong\_c/article/details/7791415\[/url\]  
\[color=red\]\[b\]\[size=large\]  
强烈推荐文章  
\[url\]http://blog.csdn.net/bz201/article/details/543001\[/url\]\[/size\]\[/b\]\[/color\]  
  
\[b\]如果要自己定义STL容器的元素类最好满足STL容器对元素的要求\[/b\]  
\[color=red\]\[b\]必须要求：\[/b\]\[/color\]  
\[quote\]1、Copy构造函数  
2、赋值=操作符  
3、能够销毁对象的析构函数\[/quote\]  
\[color=red\]\[b\]另外：\[/b\]\[/color\]  
\[quote\] 1、可用的缺省构造函数，序列型容器必须，用于初始化元素  
2、==操作符定义，用于判断相等  
3、<操作符定义，关联型容器必须，用于缺省排序\[/quote\]  
  
你可在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 );

\[b\] sort函数有以下特征：\[/b\]  
\[color=red\]1. 要求输入一个范围\[first, last)  
2. 随机迭代器，能用此算法的容器是支持随机访问的容器：vector, deque, string。  
3.第一个版本使用operator<进行比较，默认升序排序，第二个版本使用comp做比较.  
关于参数comp，comp带两个同类型的参数，如果第一个参数排在第二个参数前面，返回true，否则返回false\[/color\]  
它可以是函数指针，也可以是函数对象。函数指针好理解，何谓函数对象？  
函数对象（Function Object），是重载了operator()函数的类（或结构体）实例化出来的对象，使用起来像函数，又叫仿函数。  
  
STL本身提供了几个比较函数,下面这些都是仿函数：  
\[quote\] less(小于)  
greater(大于)  
equal\_to(等于)  
not\_equal\_to(不相等)  
less\_equal(小于等于)  
greater\_equal(大于等于)\[/quote\]  
  
当容器元素为内建类型时可以使用，注意使用的格式，要加模版参数（由于是模板类）和后面的()，如下：

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

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

// 利用函数对象实现升降排序
    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中的数据类型为自定义结构体类型时，我们该怎样实现升序与降序排列呢？  
\[b\]对运算符号进行重载\[/b\]

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

\[b\]全局的比较函数\[/b\]

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

\[b\]函数对象\[/b\]

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