浅谈 C++ 模板 & 泛化 (妈妈再也不用担心我不会用 std::sort 了)

基础复习

先上个对 int 类型数组的插入排序:

void insertionSort_01(int* seq, int firstIndex, int lastIndex) {
    for (int j = firstIndex + 1; j = firstIndex && key 
  • 提出问题: 如果想排 double 类型数组怎么办?

可以重载一个 double 版本:

void insertionSort_01_b(double* seq, int firstIndex, int lastIndex) {
    ...
}

当然, 更好的方式是利用 C++ 的模板泛化元素类型:

template
void insertionSort_02(ElemType* seq, int firstIndex, int lastIndex) {
    ...
}

步入正题

接着提出两个问题:

  • 1 是否一定要求升序排列
  • 2 ElemType 对象是否一定能使用 operator

为解决问题 1, 我们可以额外写个降序排列版本:

template
void insertionSort_02_b(ElemType* seq, int firstIndex, int lastIndex) {
    for (...) {
        ...
        // Change {} when comparing {key} and {seq[i]}:
        while (i >= firstIndex && key > seq[i]) {
            ...
        }
        ...
    }
}

对于问题 2, 我们举个例子.
现有:

struct MyStruct
{
    int aa;
    int bb;
};

MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} };

要求对 arr_MyStruct 中的元素以 MyStruct::aa 排序.
对于 C++ 新手来说, 这是一个比较难解决的问题, 也是问题 2 聚焦的关键.

对问题 1 的处理中, 我们将 "比较" 这个谓语 (predicate)operator 替换为 opeartor>;
这给了我们一些提示: 是否可以像我们用模板来泛化元素类型那样泛化谓语?

提出概念: 函数对象 (function object)
定义类 bad_greater:

// Omit the definition of class .
struct bad_greater {
    // {operator()} should be defined as a const method,
    // in order to make it available to  instances.
    bool operator()(const MyStruct& left, const MyStruct& right) const { return left.aa > right.aa; }
};

bad_greater 所创建的实例为函数对象, 可以参考以下使用案例:

// Omit the definition of class .
MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} };
bad_greater compare;
std::cout 

bad_greater 之所以 bad, 是因为其唯独提供对类 MyStruct 实例的比较.
定义一个模板类 good_less 并对 MyStruct 偏特化以解决这个问题:

// Omit the definition of class .
template
struct good_less
{
    bool operator()(const T& left, const T& right) const { return left 
struct good_less
{
    bool operator()(const MyStruct& left, const MyStruct& right) const { return left.aa 

有了函数对象, 我们可以泛化算法中的谓语:

template
void insertionSort_03(ElemType* seq, int firstIndex, int lastIndex, const _Pred& compare) {
    for (...) {
        ...
        while (... && compare(key, seq[i])) {
            ...;
        }
        ...
    }
}

调用函数 insertionSort_03() 时, 我们要注意, 编译器能直接根据传入参数推断模板的实例化类型; 因此无需提供额外的模板类参数:

// Omit the definition of class .
// Omit the definition of class .
// Omit the definition of class .

MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} };
// Ascending order:
insertionSort_03(arr_MyStruct, 0, 3, good_less());
// Descending order:
insertionSort_03(arr_MyStruct, 0, 3, good_greater());

// Also works for array with orther types:
double arr_double[4] = { 1,9.1,0.9,-3.1 };
insertionSort_03(arr_MyStruct, 0, 3, good_greater());

std::sort() 的升降序排序

std::sort() 和我们的 insertionSort_03() 一样泛化的谓语, 而且 STL 还提供了类 std::greaterstd::less 等用于定义函数对象.
升降序的使用方法参考以下代码:

#include 
#include 

double arr_double[4] = { 1,9.1,0.9,-3.1 };
// Ascending order:
std::sort(arr_double, arr_double + 4);
// Ascending order:
std::sort(arr_double, arr_double + 4, std::less());
// Descending order:
std::sort(arr_double, arr_double + 4, std::greater()));

你可能会问: 为什么第一个例子不用和之前说的一样, 传入一个函数对象?
这没什么高深的, 在 C++14 之前, 其实只是额外提供了一个只有两个参数的函数重载而已.
给个差不多的伪代码出来:

std::sort(seq_begin, seq_end){
    std::sort(seq_begin, seq_end, std::less());
}

C++14 之后在谓语类和 std::sort() 的定义上用了点小 trick, 下面给点启发性的例子 (如果不感兴趣, 你可以跳过这段):

template
struct less
{
    template
    bool operator()(const T& a, const T& b) const { return a >
void sort(..., const _Pred& compare = {}) {
    ...
}

说简单点, 就是 less 给了一个默认模板实例化类型 void; 而真正进行比较的 operator() 又是一个模板. 调用 sort 时, 不用考虑第三个参数 (函数对像) 具体是什么类型, 反正 operator() 在比较时会自行实例化.
可以参考以下使用案例:

// Under C++ 14 (or later) standard.
#include 
#include 

double arr_double[4] = { 1,9.1,0.9,-3.1 };
std::sort(arr_double, arr_double + 4); // std::less
std::sort(arr_double, arr_double + 4, std::less()); // std::less
std::sort(arr_double, arr_double + 4, std::less()); // std::less

int arr_int[4] = { 1,3,4,0 };
std::sort(arr_double, arr_double + 4, std::less()); // std::less

std::sort() 排序其他类型数组

如果看懂了前面的内容, 想必你也能够猜出来怎么实现这个问题了.
注意, std::less 之类的谓语类型说到底就是结构体, 和我们上面实现的 good_less 没啥区别.
假设我们还是要排序上文提到的 MyStruct 数组:

// Omit the definition of class .
// Omit the definition of class .
// Omit the definition of class .
#include 

MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} };
// Ascending order:
std::sort(arr_MyStruct, arr_MyStruct + 4, good_less());
// Descending order:
std::sort(arr_MyStruct, arr_MyStruct + 4, good_greater());

统一指针和迭代器

作为一个 STL 使用者, 难免会遇到指针与迭代器不统一的问题. 例如以下例子:

// Use pointer:
int arr_int[] = ...;
std::sort(arr_int, ...);

// Use iterator:
std::vector arr_vector = ...;
std::sort(arr_vector.begin(), ...);

解决方式之一是统一泛化指针类型和迭代器类型, 这里把它们都当作类 _RandIt .
我们还是以最开始的 insertionSort 为例, 给出示范代码.
需要注意的是, 通过迭代器和指针获取元素类型 (用来定义 key )时, decltype 会保留解引用 (dereference) 后留下的引用 & (也就是说 decltype(arr_int[0]) 得到的类型不是 int 而是 int& ); 因此需要调用 std::remove_reference 来删除类型中的引用.

using index = long long;

template>
void insertionSort(_RandIt seq, index firstIndex, index lastIndex, const _Pr& comp = {}) {
    for (index j = firstIndex + 1; j ::type key = seq[j];
        index i = j - 1;
        while (i >= firstIndex && comp(key, seq[i])) {
            seq[i + 1] = seq[i];
            --i;
        }
        seq[i + 1] = key;
    }
}

再给个归并排序的代码吧! 就说到这里 (计组完全没学, 寄).

using index = long long;

template
void merge(_RandIt seq, index subAFirst, index subALast, index subBLast,
    auto MAX, auto MIN, const _Pr& comp) {
    auto END = comp(MIN, MAX) ? MAX : MIN;

    size_t sizeSubA = subALast - subAFirst + 2;
    size_t sizeSubB = subBLast - subALast + 1;

    auto subA = new typename std::remove_reference::type[sizeSubA];
    std::copy(seq + subAFirst, seq + subALast + 1, subA);
    subA[sizeSubA - 1] = END;

    auto subB = new typename std::remove_reference::type[sizeSubB];
    std::copy(seq + subALast + 1, seq + subBLast + 1, subB);
    subB[sizeSubB - 1] = END;

    // Merge two subsequences to origin {seq[subAFirst : subBLast]}:
    for (index k = subAFirst, i = 0, j = 0; k = sizeSubA || j >= sizeSubB) return;
        // Merge:
        if (comp(subA[i], subB[j])) {
            seq[k] = subA[i]; ++i;
        } else {
            seq[k] = subB[j]; ++j;
        }
    }

    delete[] subA;
    delete[] subB;
}

template>
void mergeSort(_RandIt seq, index firstIndex, index lastIndex,
    auto MAX, auto MIN, const _Pr& comp = {}) {
    if (firstIndex >= lastIndex) return;
    index mid = (firstIndex + lastIndex) / 2;
    mergeSort(seq, firstIndex, mid, MAX, MIN, comp);
    mergeSort(seq, mid + 1, lastIndex, MAX, MIN, comp);
    merge(seq, firstIndex, mid, lastIndex, MAX, MIN, comp);
}

文章来源于互联网:浅谈 C++ 模板 & 泛化 (妈妈再也不用担心我不会用 std::sort 了)

THE END
分享
二维码