Recurse into a templated function after changing the type

Question

I am currently writing my own implementation of merge sort for practice. When merging the left and right parts of the list, it makes sense to create a temporary list with only the smaller of the two sides. However, the logic changes depending the side that was copied to a temp.

My function has the following signature:

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

I had a clever idea to check the lengths of [begin,middle) and [middle,end) at the beginning, and if the left was bigger, convert the iterators to reverse iterators and recursively call the function. Like this:

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)
    //...
}

However, the compiler gives a pretty thick error.

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

I've created a little stand-alone application on ideone.com that reproduces the error.

EDIT: For mergesort, I just realized that this wont work because the Compare function needs to be reversed.

Answer 1

The problem here is that, you are creating a new instantiation of the function Merge at every step of recursion i.e first time you create a reverse_iterator from a randomaccess_iterator. Then the compiler creates a reverse_iterator from the reverse_iterator and so on.....

As you must have noted while creating a reverse_iterator the template type of the iterator keeps on changing..thus creating a new instance of your templated function.

In short your use of the iterators is wrong.

This might work:

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;
}