Linked Questions

Popular Questions

Unclear on the use of RandomAccessIterators

Asked by At

I am working on a generic mergesort algorithm and for the same, I am using the random access iterator. However, when I am trying to compile the code. I am getting an merge.h:21:51: error: to refer to a type member of a template parameter, use ‘typename RandomAccessIterator::value_type’. I don't understand why is the compiler suggesting me to use the typename keyword before the RandomAccessIterator.

#ifndef MERGESORT_H
#define MERGESORT_H

#include <iostream>
#include <vector>
#include <utility>

template < class RandomAccessIterator, class Compare >
void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp){

size_t n = last - first ;

if (n<=1)
    return ;

size_t m = n/2 ;

mergesort(first, first+m, comp);
mergesort(first+m, last, comp);

std::vector< RandomAccessIterator::value_type > v(last-first);
RandomAccessIterator itResult = v.begin();

RandomAccessIterator itLower = first; 
RandomAccessIterator itUpper = first + m;

while(itLower != first+m && itUpper != last)
    *(itResult++) = comp(*itLower, *itUpper) ? *(itLower++):*(itUpper++);

if(itUpper == last)
    std::move(itLower, first+m, itResult) ;
else
    std::move(itUpper, first+m, itResult) ;

std::move(v.begin(), v.end(), first); 
}

template < class RandomAccessIterator >
void mergesort(RandomAccessIterator first, RandomAccessIterator last){
    mergesort(first, last, []( RandomAccessIterator::value_type const& a, RandomAccessIterator::value_type const& b){ return a < b; });
}

#endif

What would be the correct way to use the RandomAccessIterator in this program and are there any good sources where I can learn about the RandomAccessIterators?

Related Questions