Recurse in una funzione di modello dopo aver modificato il tipo

Question

Attualmente sto scrivendo la mia implementazione di unisci sort per esercitazione. Quando si uniscono le parti sinistra e destra dell'elenco, è opportuno creare un elenco temporaneo con solo il più piccolo dei due lati. Tuttavia, la logica cambia a seconda del lato che è stato copiato in un temp.

mia funzione ha la seguente firma:

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

ho avuto un'idea intelligente per controllare le lunghezze di [begin,middle) e [middle,end) all'inizio, e se la sinistra era più grande, convertire i iteratori per iteratori retromarcia e ricorsivamente chiama la funzione In questo modo:

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

Tuttavia, il compilatore dà un errore piuttosto spesso.

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

ho creato un little stand-alone application on ideone.com che riproduce l'errore.

MODIFICA: Per un mergesort, ho appena realizzato che questo non funzionerà perché la funzione di confronto deve essere invertita.

Answer 1

Il problema qui è che, si sta creando una nuova istanza della funzione di Merge ad ogni passo della ricorsione cioè prima volta che si crea un reverse_iterator da un randomaccess_iterator. Poi il compilatore crea un reverse_iterator dal reverse_iterator e così via .....

Come si deve aver notato durante la creazione di un reverse_iterator il tipo di modello della iteratore continua a changing..thus creando una nuova istanza della funzione templated .

In breve, l'utilizzo degli iteratori è sbagliato.

Questo potrebbe funzionare:

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

il problema è Merge<it> richiede Merge<std::reverse_iterator<it>>, che richiede Merge<std::reverse_iterator<std::reverse_iterator<it>>, che richiede Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<it>>> che richiede Merge<std::reverse_iterator<std::reverse_iterator<std::reverse_iterator<std::re‌​verse_iterator<it>>>>, che richiede ....

Quindi, ciò che si vuole è per ReverseIterator( di un iteratore già invertito per utilizzare l'iteratore originale. Quindi è necessario funzioni di aiuto per questo:

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

Prova di compilazione: http://coliru.stacked-crooked.com/a/741d73f889594e36