Powtarzanie w szablonowej funkcji po zmianie typu

Question

Obecnie piszę własną implementację sortowania scalania do praktyki. Podczas łączenia lewej i prawej części listy sensowne jest utworzenie tymczasowej listy z mniejszą z dwóch stron. Logika zmienia się jednak w zależności od strony, która została skopiowana do temp.

Moja funkcja ma następujący podpis:

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

miałem sprytny pomysł, aby sprawdzić długości [begin,middle) i [middle,end) na początku, a jeśli lewy był większy, konwertować iteratory odwrócić iteratory i rekurencyjnie zadzwoń do funkcji. W ten sposób:

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

Jednak kompilator daje dość gruby błąd.

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

Utworzyłem little stand-alone application on ideone.com że reprodukuje błąd.

EDYCJA: Dla mergesort, właśnie zdałem sobie sprawę, że to nie zadziała, ponieważ funkcja Porównaj musi zostać odwrócona.

Answer 1

Problem polega na tym, że na każdym etapie rekursji tworzysz nową instancję funkcji Merge, tj. Po raz pierwszy tworzysz reverse_iterator z randomaccess_iterator. Następnie kompilator tworzy reverse_iterator z reverse_iterator i tak dalej .....

Jak należy zauważyli podczas tworzenia reverse_iterator rodzaju szablon iteracyjnej ciągle changing..thus tworząc nową instancję swojej matrycy funkcji .

Podsumowując, użycie iteratorów jest nieprawidłowe.

Może to działa:

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

problem jest Merge<it> wymaga Merge<std::reverse_iterator<it>>, który wymaga Merge<std::reverse_iterator<std::reverse_iterator<it>>, który wymaga Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<it>>> która wymaga Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<std::re‌​verse_iterator<it>>>>, który wymaga ....

Więc co chcesz dla ReverseIterator( z już odwróconego iteratora, aby użyć oryginalnego iteratora. Więc trzeba pomocnicze funkcje, które:

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

Dowód kompilacji: http://coliru.stacked-crooked.com/a/741d73f889594e36