sortvector-向量排序的利器

一、sortvector概述

sortvector是C++ STL庫中的一個功能強大的向量排序工具，它可以便捷地對向量中的元素進行排序。sortvector源碼作為一個header文件附在本文末尾

sortvector通過實現快速排序演算法，可以快速對向量內的元素進行排序。它幾乎適用於所有的數據類型，包括整數、浮點數、字元串等等。而且，它並不要求輸入向量必須是連續的內存空間。

二、sortvector的使用

sortvector的使用非常簡單，首先，我們需要包含sortvector頭文件，使用方式如下：

#include "sortvector.h"

然後，我們需要定義一個sortvector對象，並向其中添加元素，示例代碼如下：

#include "sortvector.h"
#include <iostream>
using namespace std;

int main()
{
    sortvector v; //定義一個保存整型的向量v
    v.push_back(11);
    v.push_back(8);
    v.push_back(5);
    v.push_back(9);
    v.push_back(16);
    v.push_back(2);
    v.push_back(3);
    v.push_back(10);

    v.sort(); //調用sort函數進行排序

    for(int i=0; i<v.size(); i++)
    {
        cout<<v[i]<<" "; //輸出排序後的向量
    }

    return 0;
}

上述代碼中，我們定義了一個sortvector對象v，並向其中添加了8個整數元素，然後使用sort函數對該向量進行排序，最後輸出排序後的向量中的元素。

三、sortvector的優劣性分析

1、優點：

（1）快速排序演算法的實現，排序速度非常快；

（2）支持幾乎所有的數據類型；

（3）並不要求輸入的向量必須是連續的內存空間。

2、缺點：

（1）sortvector類中沒有提供排序演算法的選擇，只能使用快速排序演算法；

（2）只有一個sort函數，如果用戶需要自定義排序方法，需要自己添加新的sort函數；

（3）sortvector使用時需要引入頭文件，增加了代碼量。

四、sortvector的拓展應用

1、自定義排序方法

sortvector的sort函數只支持快速排序演算法，如果用戶需要使用其他排序演算法，可以自己添加新的sort函數。例如，對於字元串的排序，我們可以使用歸併排序演算法：

template <typename T>
void sortvector<T>::sort(function<bool(T,T)> cmp)
{
    mergesort(0,vec.size()-1,cmp);
}

template <typename T>
void sortvector<T>::mergesort(int begin, int end, function<bool(T,T)> cmp)
{
    if(end <= begin) return;

    int mid = (begin+end)/2;
    mergesort(begin, mid, cmp);
    mergesort(mid+1, end, cmp);

    int i = begin, j = mid+1;
    while(i<j && j<=end)
    {
        if(cmp(vec[i],vec[j]))
        {
            vec.insert(vec.begin()+i,vec[j]);
            vec.erase(vec.begin()+j+1);
            j++;
        }
        i++;
    }
}

在該實現中，我們使用了函數指針作為參數，傳入自定義的排序方法cmp。並且，實現了歸併排序演算法，將排序方法作為參數傳入了sort函數中。

2、支持仿函數、Lambda表達式等排序方法

sortvector支持使用仿函數、Lambda表達式等方式實現排序方法。例如，我們可以通過仿函數對象實現字元串按照長度進行排序：

struct cmpstrbylength
{
    bool operator()(const string& a, const string& b) const
    {
        return a.length()<b.length();
    }
};

int main()
{
    sortvector<string> v; //定義一個保存字元串的向量v
    v.push_back("abcd");
    v.push_back("a");
    v.push_back("defg");
    v.push_back("aaaaaa");
    v.push_back("bcd");
    v.sort(cmpstrbylength()); //使用仿函數對象進行排序
    for(int i=0; i<v.size(); i++) cout<<v[i]<<" ";
    return 0;
}

上述代碼中，我們定義了一個名為cmpstrbylength的仿函數對象，其中實現了字元串按照長度進行排序的方法，然後在sort函數中使用該仿函數對象進行排序。

3、支持reverse_iterators逆向迭代器

sortvector類中還支持reverse_iterators逆向迭代器，這可以對向量進行反向遍歷。例如：

for(auto it=v.rbegin(); it!=v.rend(); it++)
{
    cout<<*it<<" ";
}

該代碼會反向輸出v中的元素。

五、sortvector源碼

#ifndef SORTVECTOR_H_INCLUDED
#define SORTVECTOR_H_INCLUDED

#include <vector>
#include <functional>

using namespace std;

template <typename T>
class sortvector
{
public:
    sortvector() {}
    virtual ~sortvector() {}

    void push_back(const T& val) { vec.push_back(val); }

    void sort();

    template <class Compare>
    void sort(Compare cmp);

    T& operator[](int index) { return vec[index]; }
    int size() { return vec.size(); }

    typedef typename vector<T>::iterator iterator;
    typedef typename vector<T>::reverse_iterator reverse_iterator;

    iterator begin() { return vec.begin(); }
    iterator end() { return vec.end(); }
    reverse_iterator rbegin() { return vec.rbegin(); }
    reverse_iterator rend() { return vec.rend(); }

private:
    vector<T> vec;

    void quicksort(int begin, int end);
    int partition(int begin, int end);
};

template <typename T>
void sortvector<T>::sort()
{
    quicksort(0, vec.size()-1);
}

template <typename T>
void sortvector<T>::quicksort(int begin, int end)
{
    if(end <= begin) return;

    int pindex = partition(begin, end);
    quicksort(begin, pindex-1);
    quicksort(pindex+1, end);
}

template <typename T>
int sortvector<T>::partition(int begin, int end)
{
    T pivot = vec[end];
    int pindex = begin;
    for(int i=begin; i<end; i++)
    {
        if(vec[i] < pivot)
        {
            swap(vec[i], vec[pindex]);
            pindex++;
        }
    }
    swap(vec[pindex], vec[end]);
    return pindex;
}

template <typename T>
template <class Compare>
void sortvector<T>::sort(Compare cmp)
{
    sort(vec.begin(), vec.end(), cmp);
}

#endif // SORTVECTOR_H_INCLUDED