I am passing two exactly same iterators to a function, but one of them becomes 'long'

Question

 vector<int> Merge(const vector<int>& lhs, const vector<int>& rhs) {
    int n = lhs.size() + rhs.size();
    vector<int> result(n);
    for(int i = 0, j = 0, k = 0; k < n; ++k) {
        if(lhs[i] < rhs[j]) {
            result[k] = lhs[i];
            ++i;
        }
        else {
            result[k] = rhs[j];
            ++j;
        }
    }
    return result;
}

template<class RandomIt>
vector<int> merge_sort(RandomIt begin, RandomIt end) {
    if(end - begin <= 1) {
        return vector<int>(begin, end);
    }
    else{
        vector<int> lhs = merge_sort(begin, (end - begin) / 2);
        vector<int> rhs = merge_sort((end - begin) / 2, end);
        return Merge(lhs, rhs);
    }
}

I am writing merge sort algorithm in C++, but getting this error. Please, help me figure out what I am doing wrong. I think the problem is one of my iterators is becoming 'long', as shown in third error, but i can't find where does this exactly happening.

Line 26: Char 31: error: no matching member function for call to 'merge_sort'
        vector<int> lhs = merge_sort(begin, (end - begin) / 2);
                          ^~~~~~~~~~
Line 33: Char 16: note: in instantiation of function template specialization 'Solution::merge_sort<__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int>>>>' requested here
        return merge_sort(nums.begin(), nums.end());
               ^
Line 21: Char 17: note: candidate template ignored: deduced conflicting types for parameter 'RandomIt' ('__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int>>>' vs. 'long')
    vector<int> merge_sort(RandomIt begin, RandomIt end) {
            ^

Substracting iterators, `end - begin` in your example, doesn't return an iterator, but rather how far apart they are. Try `begin + ((end - begin) / 2)` instead — Kaldrr, Feb 09 '22 at 09:36
Compare your merge sort to [the one you see here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). See the difference? The one at the link passes iterators, not distances. You should use the distance to figure out what iterator to pass -- you shouldn't pass the actual distance. — PaulMcKenzie, Feb 09 '22 at 09:36
Aside: consider defining your merge like [`std::inplace_merge`](https://en.cppreference.com/w/cpp/algorithm/inplace_merge), so you aren't copying your data so much — Caleth, Feb 09 '22 at 10:07

I am passing two exactly same iterators to a function, but one of them becomes 'long'

0 Answers0