c++中vector自定义排序的问题

忘是亡心i 2022-04-12 08:22 333阅读 0赞

如果要自己定义STL容器的元素类最好满足STL容器对元素的要求  
    必须要求：  
     1、Copy构造函数  
     2、赋值=操作符  
     3、能够销毁对象的析构函数  
    另外：  
     1、可用的缺省构造函数，序列型容器必须，用于初始化元素  
     2、==操作符定义，用于判断相等  
     3、<操作符定义，关联型容器必须，用于缺省排序

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

以上内容取自帖子：[http://bbs.csdn.net/topics/40228627][http_bbs.csdn.net_topics_40228627]

另一篇参考地址：[http://blog.csdn.net/tigernana/article/details/7293758][http_blog.csdn.net_tigernana_article_details_7293758]

以下取自帖子：[http://blog.csdn.net/guang11cheng/article/details/7556697][http_blog.csdn.net_guang11cheng_article_details_7556697]

# 三种方式实现vector的自定义排序 #

## 方法1：重载运算符 ##

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

##   方法2：全局的比较函数 ##

##  ##

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

## 方法3：函数对象 ##

##  ##

#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;
     }
     
    
    /*
     结果如下：
     type: 1, id: 1
     type: 2, id: 2
     type: 2, id: 4
     type: 3, id: 3
     --
     type: 3, id: 3
     type: 2, id: 2
     type: 2, id: 4
     type: 1, id: 1
     可以看出vector的sort的稳定的。
     */

## 问题： ##

## 1，示例代码中只有>和<关系处理，==关系是如何推导出来的？ ##

## 2，排序时要移动元素，效率怎样？ ##

## 3，如果自定义结构定义在一个类的内部，使用函数对象进行排序，这个函数对象可以作为类的成员函数吗？ ##

## 4，在上面的例子中，vector中存放的都是结构（对象）本身，如果存放的是结构指针，该如何排序呢？此时只能通过全局的比较函数或者函数对象来做，且比较函数的参数要是指针类型的，如下： ##

（1）全局的比较函数

#include <vector>
     #include <algorithm>
     #include <functional>
     
    
    using namespace std;
     
    
    struct TItem
     {
         int m_i32Type;
         int m_i32ID;
     };
     
    
    bool CompLess(const TItem* pstItem1, const TItem* pstItem2)
     {
         return pstItem1->m_i32Type < pstItem2->m_i32Type;
     }
     
    
    bool CompGreater(const TItem* pstItem1, const TItem* pstItem2)
     {
         return pstItem1->m_i32Type > pstItem2->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;
     }

（2）函数对象

#include <vector>
     #include <algorithm>
     #include <functional>
     
    
    using namespace std;
     
    
    struct TItem
     {
         int m_i32Type;
         int m_i32ID;
     };
     
    
    class CompLess
     {
     public:
         bool operator ()(const TItem* pstItem1, const TItem* pstItem2)
         {
             return pstItem1->m_i32Type < pstItem2->m_i32Type;
         }
     };
     
    
    class CompGreater
     {
     public:
         bool operator ()(const TItem* pstItem1, const TItem* pstItem2)
         {
             return pstItem1->m_i32Type > pstItem2->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;
     }

推荐使用函数对象。

[http_bbs.csdn.net_topics_40228627]: http://bbs.csdn.net/topics/40228627
[http_blog.csdn.net_tigernana_article_details_7293758]: http://blog.csdn.net/tigernana/article/details/7293758
[http_blog.csdn.net_guang11cheng_article_details_7556697]: http://blog.csdn.net/guang11cheng/article/details/7556697