纯C++11标准写类topk算法(不稳定排序)类模板

/*
 * topk_base.h
 *
 *  Created on: 2015年10月22日
 *      Author: guyadong
 */

#ifndef CMIMPL_TOPK_BASE_H_
#define CMIMPL_TOPK_BASE_H_
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <memory>
#include <minmax.h>
#include <functional>
#include <type_traits>
#include "utility.h"
using namespace std;
namespace gyd{
/* 计算比较函数的返回值类型 */
template<typename N>
struct compare_result{
    using type=typename std::conditional    <std::is_arithmetic<N>::value,decltype(declval<N>()-declval<N>()),int>::type;
};

/* 计算比较器对象(Callable Object)的类型 */
template<typename N>
struct compartor{
    using type=std::function<typename gdface::compare_result<N>::type(N,N)const noexcept>;
};
/* 定义比较器类型,并根据N,CMP,DEC选择合适的比较器类型
 * dec为降序,inc为升序
  */
template <typename N,typename compartor<N>::type *CMP,bool DEC>
struct comparator{
    /* 缺省的算术比较器,只适用于arithmetic类型 */
    struct arithmetic{
        struct dec{
            typename compare_result<N>::type inline value(N n1,N n2) const noexcept{return n1-n2;};
        };
        struct inc{
            typename compare_result<N>::type inline value(N n1,N n2) const noexcept{return n2-n1;};
        };
    };
    /* 使用CMP提供的自定义比较器  */
    struct other{
        struct dec{
            static_assert(nullptr != CMP,"nullptr==CMP");
            const typename compartor<N>::type&_comparator = *CMP;
            typename compare_result<N>::type inline value (N n1,N n2)const noexcept {return _comparator(n1-n2);};
        };
        struct inc{
            static_assert(nullptr != CMP, "nullptr==CMP");
            const typename compartor<N>::type&_comparator = *CMP;
            typename compare_result<N>::type inline value (N n1,N n2)const noexcept {return _comparator(n2-n1);};
        };
    };
    using type=typename std::conditional<
            nullptr!=CMP,
            typename std::conditional<DEC,typename other::dec,typename other::inc>::type,
            typename std::conditional<DEC,typename arithmetic::dec,typename arithmetic::inc>::type
            >::type;
};
template <typename T,typename N,typename compartor<N>::type *CMP=nullptr,bool DEC=true,typename Enable=void>
class topk_base;//通例

/*
 * topk排序(不稳定排序)类模板,
 * 对象内部有一个容量为m_capacity的排序缓冲区m_sort(初始化时生成),
 * 用insert方法每次加入一个要排序的对象T,当T的排序值N大于阀值时，将T按排序值插入m_sort(始终是一个有序数组)
 * T为要排序的对象类型,
 * N为排序依据的值类型,
 * CMP为比较器函数对象(Callable Object)指针
 * DEC为排序类型，true为降序,
 * N为数字/算术(arithmetic)类型时,CMP可以为nullptr,否则必须提供CMP,
 * 非算术类型的CMP函数返回值为int,函数签名int(N n1,N n2),
 * 如果希望n1要排在n2前面,则返回>0的整数,n1==n2,返回0,否则小0;
 * 特例: 禁止N为bool类型,比较值为bool类型无意义
 * + 操作符 将两个对象合并排序成新对象
 * += 操作符将参数对象合并到当前对象
 */
template <typename T,typename N,typename compartor<N>::type *CMP,bool DEC>
class topk_base<T,N,CMP,DEC,typename std::enable_if<!is_same<N,bool>::value>::type>{
    //静态断言:N为非算术类型时,CMP不能为nullptr
    static_assert(std::is_arithmetic<N>::value||nullptr!=CMP,"FUN must not be nullptr while N is not arithmetic");
public:
    using SIZE_TYPE =size_t;
protected:
private:
    /* 初始阀值 */
    const N m_threshold;
    /* 排序缓冲区容量 */
    const SIZE_TYPE m_capacity;
protected:
    /* 排序节点 */
    struct _CompareNode{
        const T* t;
        N  n;
    };
    /* 排序缓冲区 */
    unique_ptr<_CompareNode[]> m_sort;
    /* 缓冲区中已经排序元素个数,初始为零 */
    SIZE_TYPE m_size=0;
    /* 当前阀值指针,初始值指向m_threshold */
    const N *mp_threshold=&m_threshold;
public:
    using M_SIZE_TYPE=decltype(m_size);
private:
    /* 计算比较器类型 */
    using _CMP_TYPE=typename comparator<N,CMP,DEC>::type;
    /* 比较器对象 _compatator.value(n1,n2)返回值>0则n1排在n2前面 */
    _CMP_TYPE _compatator;
    /* 二分法获取新排序节点node在排序缓冲区的排序位置(循环) */
    auto rank(const _CompareNode &node, SIZE_TYPE from, SIZE_TYPE size)const noexcept->decltype(from){
        auto start=from;
        auto len=size;
        decltype(len>>1) mid;
        typename compare_result<N>::type cmp_res;
        do{
            if(len>1){
                mid=len >> 1;
                cmp_res=_compatator.value(node.n, m_sort[start+mid].n);
                if(cmp_res>0){
                    len-=mid;// 前半部搜索
                }else   if(cmp_res<0){
                    start+=++mid,len-=mid; // 后半部搜索
                }else
                    return start+mid;
            }else if(len==1){
                return _compatator.value(node.n,m_sort[start].n)>=0?start:start+1;
            }else
                return start;
        }while(true);
    }
    /* 更新当前阀值指针 */
    void inline update_threshold()noexcept{
        if(m_size==m_capacity){
            mp_threshold=&m_sort[m_size - 1].n;//当排序缓冲区满的时候,用最后一个节点的值更新当前阀值指针
        }
    }
    /* 断言两个对象类型相同 */
    static void inline assert_same_type(const topk_base &t1,const topk_base &t2)noexcept {
        assert(t1.m_capacity==t2.m_capacity&&t1.m_threshold==t2.m_threshold);
    }
public:
    /* 构造函数 maxRows必须>0 */
    topk_base(SIZE_TYPE maxRows,N threshold) noexcept:
        m_capacity(maxRows),
        m_threshold(threshold),
        m_sort(make_unique<_CompareNode[]>(maxRows)){
        assert(m_capacity>0);
    }
    /* 复制构造函数 */
/*  topk_base(const topk_base& v):
            m_capacity(v.m_capacity),
            m_threshold(v.m_threshold),
            m_sort(make_unique<_CompareNode[]>(v.m_capacity)),
            m_size(v.m_size){
        memcpy(m_sort.get(),v.m_sort.get(),sizeof(_CompareNode)*m_size);//只复制有效数据
    };*/
    /* 移动构造函数 */
    topk_base(topk_base&& rv)noexcept:
            m_capacity(rv.m_capacity),
            m_threshold(rv.m_threshold),
            m_size(rv.m_size){
        std::swap(m_sort,rv.m_sort);
    }
    /* 移动拷贝函数 */
    topk_base& operator=(topk_base&& rv) {
        if(m_capacity!=rv.m_capacity||m_threshold!=rv.m_threshold)
            throw logic_error("m_capacity==rv.m_capacity OR m_threshold==rv.m_threshold");
        m_size=rv.m_size;
        m_sort=std::move(rv.m_sort);
        return *this;
    };

    virtual ~topk_base()=default;

    /* 将obj加入topk,如果cmpValue小于当前阀值,则返回false */
    bool insert(const T& obj,const N cmpValue)noexcept {
        auto c=_compatator.value(cmpValue,*mp_threshold);
        // 大于阀值才进一步执行比较排序，小于阀值则返回
        if(c<0||(c==0&&m_size==m_capacity))
            return false;
        _CompareNode node{std::addressof<const T>(obj),cmpValue};
        //将排序节node点加入排序缓冲区
        auto offset = rank(node, 0, m_size);
        auto sort=m_sort.get();
        // 在offset位置插入节点,offset(含)之后的数据向后移一位
        memmove(sort + offset + 1, sort + offset,
                sizeof(_CompareNode) * (m_size < m_capacity ? m_size++ - offset : m_capacity - offset-1));
        sort[offset] = node;
        update_threshold();
        return true;
    }

    M_SIZE_TYPE size()const noexcept{return m_size;}
    /* 导出排序结果 */
    virtual M_SIZE_TYPE result(T * out)const noexcept{
        assert(nullptr!=out);
        for(M_SIZE_TYPE i=0;i<m_size;i++)out[i]=*m_sort[i].t;
        return m_size;
    }
    /* 将from中排序的数据合并到当前对象中
     * buf_in为排序用的临时对象,可以为nullptr,如果不为nullptr,类型必须与当前对象相同
     * 返回当前对象引用
     */
    topk_base& merge(const topk_base &from,topk_base * buf_in=nullptr) noexcept{
        if(from.m_size==0)
            return *this;
        else {
            if(nullptr==buf_in){
                topk_base buf(m_capacity,this->m_threshold);
                merge_to(from,buf);
                *this=std::move(buf);
            }else{
                merge_to(from,*buf_in);
                *this=std::move(*buf_in);
            }
        }
        return *this;
    }
    /* 将当前对象和from合并排序到目标对象to
     * 返回to引用
     */
    topk_base& merge_to(const topk_base &from,topk_base &to) noexcept{
        assert_same_type(from,*this);
        assert_same_type(from,to);
        assert(to.m_size==0);
        auto buf = to.m_sort.get();
        typename std::remove_const<decltype(m_capacity)>::type idx = 0;
        M_SIZE_TYPE idx_this = 0, idx_from = 0;
        decltype(rank(m_sort[0],0,0)) offset_this,offset_from;
        while ( idx < m_capacity&&idx_this < m_size&&idx_from < from.m_size&&idx_from < from.m_size) {
            offset_this=rank(from.m_sort[idx_from],idx_this,m_size-idx_this);
            if(offset_this==idx_this){
                offset_from = from.rank(m_sort[idx_this], idx_from + 1, from.m_size - idx_from - 1);
                auto copy_size=min(this->m_capacity-idx,offset_from-idx_from);
                memcpy(buf+idx,from.m_sort.get()+idx_from,copy_size);
                idx+=copy_size;
                idx_from += copy_size;
                if (idx < m_capacity) {
                    buf[idx++] = m_sort[idx_this++];
                }
            }else{
                auto copy_size=min(this->m_capacity-idx,offset_this-idx_this);
                memcpy(buf+idx,m_sort.get()+idx_this,copy_size);
                idx+=copy_size;
                idx_this += copy_size;
                if (idx < m_capacity) {
                    buf[idx++] = from.m_sort[idx_from++];
                }
            }
        }
        if (idx < m_capacity) {
            if (idx_from < from.m_size)
                memcpy(buf + idx, from.m_sort.get() + idx_from, sizeof(_CompareNode) * min(m_capacity-idx, from.m_size - idx_from));
            else if (idx_this < this->m_size)
                memcpy(buf + idx, m_sort.get()         + idx_this,   sizeof(_CompareNode) * min(m_capacity-idx, this->m_size - idx_this));
        }
        to.m_size = min(to.m_capacity, from.m_size + m_size);
        to.update_threshold();
        return to;
    }
    /* += 操作符 将参数对象合并到当前对象 */
    topk_base&  operator+=(const topk_base &from) noexcept{
        return merge(from);
    }
    /* + 操作符 将两个对象合并排序成新对象 */
    topk_base  operator+(const topk_base &from) noexcept{
        topk_base res(this->m_capacity,this->m_threshold);
        return std::move(merge_to(from,res));//转为右值引用以调用移动构造函数
    }
};/* topk_base */
}/* namespace gyd*/

#endif /* CMIMPL_TOPK_BASE_H_ */
//以上代码在gcc5/vs2015下编译通过

topk_base(SIZE_TYPE maxRows,N threshold) noexcept:
        m_capacity(maxRows),
        m_threshold(threshold),
        m_sort(make_unique<_CompareNode[]>(maxRows)){
        assert(m_capacity>0);
    }

using M_SIZE_TYPE=decltype(m_size);
M_SIZE_TYPE size()const noexcept{return m_size;}//根据m_size的类型推导size方法的返回值类型

        auto buf = to.m_sort.get();
        typename std::remove_const<decltype(m_capacity)>::type idx = 0;//根据m_capacity的类型推导idx的类型
        M_SIZE_TYPE idx_this = 0, idx_from = 0;//根据m_size的类型推导idx_this，idx_from的类型
        decltype(rank(m_sort[0],0,0)) offset_this,offset_from;//根据rank方法的返回类型定义offset_this，offset_from的类型

    topk_base<code_bean,float>top(200, 0.75f);
    //迭代器循环调用insert，将当前对象*itor和临时计算出来的排序依据值(FCUtils::compare(itor->code, code))加入top
    for (auto itor = begin(); !itor.end(); ++itor) {
        top.insert(*itor, FCUtils::compare(itor->code, code));
    }
    //循环结束,top对象就是排序结果。可以调用 size()获取排序结果数目，然后调用 result方法获取排序结果。

    topk_base<code_bean,float> tb1(200,0.5f);//创建一个对象
    topk_base<code_bean,float> tb2(200,0.5f);
    tb1.merge(tb2);//合并tb1到tb1
    topk_base<code_bean,float> tb3=tb1+tb2;//tb1,tb2合并到tb3