Replace template function after type change

Question

I am currently writing my own merge sort implementation for practice. When combining the left and right parts of the list, it makes sense to create a temporary list only from the smaller side. However, the logic changes depending on which copy was copied to a temporary one.

My function has the following signature:

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

I had a smart idea to check the lengths of [begin,middle) and [middle,end) at the beginning, and if there was more left, convert iterators to inverse iterators and call the function recursively. 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 rather thick error.

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

I created a small standalone application on ideone.com that reproduces the error.

EDIT: for mergesort, I just realized that this does not work, because the Compare function has to be canceled.

Answer 1

The problem is that you create a new creation of the Merge function at each stage of the recursion. The first time you create reverse_iterator from randomaccess_iterator . Then the compiler creates reverse_iterator from reverse_iterator , etc ...

As you must have noted when creating reverse_iterator , the type of the iterator template continues to change ... creating a new instance of your template function.

In short, using 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; } 

Answer 2

Merge<it> problem requires Merge<std::reverse_iterator<it>> , which requires Merge<std::reverse_iterator<std::reverse_iterator<it>> , which requires Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<it>>> , which requires Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<std::re‌​verse_iterator<it>>>> , which requires ....

So, you want to use the ReverseIterator( already inverted iterator to use the original iterator. For this, you need some helper functions:

 template <class RandomIt> RandomIt ReverseIt(std::reverse_iterator<RandomIt> it) { return it.base(); } template <class RandomIt> std::reverse_iterator<RandomIt> ReverseIt(RandomIt it) { return std::reverse_iterator<RandomIt>(it); } template<class RandomIt, class Compare=std::less<typename std::iterator_traits<RandomIt>::value_type>> 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) { Merge(ReverseIt(end), ReverseIt(std::next(middle)), ReverseIt(begin), Comp); return; } //Now [begin,middle) is guaranteed <= [middle,end) //... } 

Proof of compilation: http://coliru.stacked-crooked.com/a/741d73f889594e36