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