C++ 泛型

叁歲伎倆 2023-06-03 06:58 0阅读 0赞

# 泛型 #

Xun

C++标准算法库中的各种函数都有很强的适用性。比如其中的`std::sort`函数，它即可以对`std::vector`中的元素进行排序，也能对`std::deque`中的元素进行排序，对于数组中的元素，它也可以正常运行。同时，`std::sort`函数还可以接受一个函数指针（谓词），用来指定排序规则。在这篇文章中，我们将模拟标准库中的`std::sort`函数，写一个与其接口相同的排序函数。

这里排序的方法为归并排序，其主要思想是将两个已排序的短序列合并为一个更长的已排序序列。一般来说，子序列也是无序的，这就需要在函数中对两个短序列进行归并排序。若序列只有一个元素，则它肯定是有序的，递归结束。其动图演示如下：（动图来自互联网）

![1767250-20190831212202656-1428573319.gif][]

下面参考一下`std::sort`函数的接口。`std::sort`函数无返回值（或返回`void`），接收两个迭代器指示序列的开始位置和尾后位置，同时还有一个可选参数，用来指定排序规则，其默认使用`<`来进行比较。

于是我们排序函数的接口可能长成这样：

template<typename RandIter>
    void merge_sort
    (
        RandIter iterBeg, RandIter iterEnd, //开始与尾后迭代器
        TYPE comp = ...//排序规则
    )

这里的第一行代码说明下面的`RandIter`是一个类名，在函数调用时会将其替换为相应的类型，如`int*`，`std::vector<int>::iterator`等。`comp`是一个二元谓词，一旦`RandIter`确定，`comp`的类型也就随之确定了。比如`RandIter`是`std::deque<int>::iterator`，其核心数据成员是`int`类型，谓词就是为`bool (*comp) (int a, int b)`，即接收两个`int`型变量，返回`bool`型的一个函数指针。然而对于各种不同的迭代器类型，该如何确定其中的`TYPE`？

对于标准库中的各种顺序容器的迭代器类，都封装了一个`value_type`用来说明其指向序列中元素的类型，比如存储着double元素的`std::vector`的迭代器的`value_type`，即`std::vector<double>::iterator::value_type`其实就是`double`类型。所以，`comp`的类型`TYPE`可以写作`typename RandIter::value_type`。

但是，对于普通的数组，传入的迭代器是两个指针，而指针类型是没有`value_type`的！因此这样写的话是不能处理数组的。

在头文件`type_traits`中，标准库提供了很多的类型转换函数。对于类型`int*`，其解引用类型为`int`。对于更一般的类型`T`，若`U*`与`T`是相同的类型，则可以使用`type_traits`中的`std::remove_pointer<T>::type`来得到类型`U`。

同样的`romove_pointer`只能处理指针，而对于顺序容器就束手无策了。

C++中还提供了`auto`、`decltype`关键字来进行类型推断。在函数接口中，是不能使用`auto`的。于是，我们的希望就落在了`decltype`上。

我们需要的是`*iterBeg`的类型，但是`decltype`一个解引用会得到引用类型，所以我们仍需借助标准库头文件`type_traits`中的一个`remove_reference`函数来去除引用性质。于是，函数的接口如下：

类型名解决了，下面就是默认参数了。这里，我们将一个lambda表达式传入`comp`。

bool (*comp)(...) = [](typename std::remove_reference<decltype(*iterBeg)>::type a, typename std::remove_reference<decltype(*iterBeg)>::type b){return a < b;}

将整个接口写出来，是这样的：

我之前写这个函数的时候，参考了Visual Studio所采用的实现版本，发现它使用的是重载而不是默认参数来实现，其接口看起来要清爽不少：

template<typename RandIter>
    void merge_sort//这里使用 '<' 来排序
    (
        RandIter iterBeg, RandIter iterEnd //开始与尾后迭代器
    );
    
    template<typename RandIter, typename Pred>
    void merge_sort//这里使用 comp 来排序
    (
        RandIter iterBeg, RandIter iterEnd, //开始与尾后迭代器
        Pred comp//排序规则
    );

下面是函数的实现部分，与主题的关系不大，可以略过。

template<typename RandIter>
    void merge_sort
    (
        RandIter iterBeg, RandIter iterEnd, //开始与尾后迭代器
        bool (*comp)(typename std::remove_reference<decltype(*iterBeg)>::type, 
            typename std::remove_reference<decltype(*iterBeg)>::type) = []
            (typename std::remove_reference<decltype(*iterBeg)>::type a,
             typename std::remove_reference<decltype(*iterBeg)>::type b) ->bool
                {return a < b; }    
    )
    {
        //递归终止条件为子序列只有一个元素，一个元素一定是有序的
        //第二个判断条件是为了防止输入空序列
        if (iterBeg + 1 == iterEnd || iterBeg == iterEnd)
            return;
    
        RandIter iterMid = iterBeg + (iterEnd - iterBeg) / 2;//指向序列中间位置
        merge_sort(iterBeg, iterMid, comp);//递归
        merge_sort(iterMid, iterEnd, comp);//只有子序列有序才进行合并
        std::vector<std::remove_reference<decltype(*iterBeg)>::type>temp;//用来存储合并的有序序列
        temp.reserve(iterEnd - iterBeg);//保留空间用于存诸元素，防止空间扩张带来的额外花销
        auto it1 = iterBeg, it2 = iterMid;//分别指向两个子序列的开始位置
        while (it1 != iterMid || it2 != iterEnd)//还有元素没处理
        {
            if (it1 == iterMid)//序列1的元素已放完
                temp.emplace_back(*it2++);//只能放序列2的元素，后加的优先级高于解引用 （解引用与前加同级）
            else if (it2 == iterEnd)
                temp.emplace_back(*it1++);
            else
                temp.emplace_back(comp(*it1, *it2) ? *it1++ : *it2++);//按谓词规定的顺序放入
        }
    
        //将排好序的序列复制到原序列中的位置
        typename std::vector<std::remove_reference<decltype(*iterBeg)>::type>::iterator itTemp = temp.begin();//第一个typename说明iterator是一个类型名
        for (RandIter it2 = iterBeg; it2 != iterEnd; ++itTemp, ++it2)
            * it2 = *itTemp;
    }

归并排序不能原位操作，这里使用一个`vector`来存储临时数据。

完

转载于:https://www.cnblogs.com/xunxunxun/p/11440531.html

[1767250-20190831212202656-1428573319.gif]: /images/20230601/f57dd6db2fd84cc7b02d11dfbef921c5.png