c++ - 更改类型后递归到模板函数中

Question

我目前正在编写自己的合并排序实现以供练习。合并列表的左右部分时，创建一个只有两侧较小的临时列表是有意义的。但是，逻辑会根据复制到临时文件的一侧而变化。

我的函数具有以下签名:

template<class RandomIt, class Compare>
void Merge(RandomIt begin, RandomIt middle, RandomIt end, Compare Comp);

我灵机一动，在开始的时候检查了[begin,middle)和[middle,end)的长度，如果左边更大，就转换迭代器反转迭代器并递归调用函数。像这样:

template<class RandomIt, class Compare>
void Merge(RandomIt begin, RandomIt middle, RandomIt end, Compare Comp) {
    size_t leftLength = std::distance(begin, middle);
    size_t rightLength = std::distance(middle, end);

    if (leftLength > rightLength) {
        using ReverseIterator = std::reverse_iterator<RandomIt>;
        Merge(ReverseIterator(end), ReverseIterator(std::next(middle)), ReverseIterator(begin), Comp);
        return;
    }
    //Now [begin,middle) is guaranteed <= [middle,end)
    //...
}

但是，编译器给出了一个非常严重的错误。

fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)

我创建了一个 little stand-alone application on ideone.com重现错误。

编辑:对于归并排序，我刚刚意识到这行不通，因为需要反转比较函数。

Answer 1

这里的问题是，您在递归的每一步都创建了函数 Merge 的新实例，即第一次从 创建 reverse_iterator randomaccess_iterator。然后编译器从 reverse_iterator 中创建一个 reverse_iterator 等等......

正如您在创建 reverse_iterator 时所注意到的，迭代器的模板类型不断变化..因此创建了模板函数的新实例。

简而言之，您对迭代器的使用是错误的。

这可能有效:

template <class RandomIt, class RevIt>
void Test(RandomIt begin, RandomIt middle, RandomIt end, RevIt rit) {
        size_t leftLength = std::distance(begin, middle);
        size_t rightLength = std::distance(middle, end);
        if (leftLength > rightLength) {
                Test(RevIt(end), RevIt(middle), RevIt(begin), rit);
                return;
        }
}

template <typename RandomIt>
void Test(RandomIt begin, RandomIt middle, RandomIt end) {
  Test(begin, middle, end, std::reverse_iterator<RandomIt>());
}

int main() {
        std::vector<int> nums = { 2, 1, 123, 1, 23, 123, 123, 5234, 52, 3, 452, 3, 452, 5 };
        int middle;
        std::cin >> middle;
        Test(nums.begin(), nums.begin()+middle, nums.end());
        return 0;
}