what's different between pass vector iterators and deque iterators in following code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
namespace sort {
    template <typename Itr>
    using type = typename std::iterator_traits<Itr>::value_type;
    template <typename T>
    using viterator = typename std::vector<T>::iterator;

    template <typename Itr, typename Comp = std::less<type<Itr>>>
    void merge(Itr beg, Itr mid, Itr end,
               viterator<type<Itr>> vbeg, viterator<type<Itr>> vend, Comp comp = {}) {
        auto beg1 = beg;
        auto beg2 = mid;
        while (beg1 != mid && beg2 != end)
            *vbeg++ = std::move(comp(*beg1, *beg2)? *beg1++: *beg2++);
        while (beg1 != mid)
            *vbeg++ = std::move(*beg1++);
        while (beg2 != end)
            *vbeg++ = std::move(*beg2++);
        while (end != beg) {
            *--end = std::move(*--vend);
        }
    }

    template <typename Itr, typename Comp = std::less<type<Itr>>>
    void merge_sort(Itr beg, Itr end,
                    viterator<type<Itr>> vbeg, viterator<type<Itr>> vend, Comp comp = {}) {
        if (1< std::distance(beg, end)) {
            auto mid = beg;
            std::advance(mid, std::distance(beg, end)/2);
            auto vmid = vbeg;
            std::advance(vmid, std::distance(vbeg, vend)/2);
            
            merge_sort(beg, mid, vbeg, vmid, comp);
            merge_sort(mid, end, vmid, vend, comp);
            merge(beg, mid, end, vbeg, vend, comp);
            // if i prefixed sort:: to merge, it would work. but why?
            // i don't include algorithm header. i compile it at Xcode 
        }
    }

    template <typename Itr, typename Comp = std::less<type<Itr>>>
    void merge_sort(Itr beg, Itr end, Comp comp = {}) {
        std::vector<type<Itr>> v(end - beg);
        
        merge_sort(beg, end, v.begin(), v.end(), comp);
    }
}

if i pass vector iterators to merge_sort, such as merge_sort(v.begin, v.end), the compiler says "call to 'merge' is ambiguous" at line 33, but if pass deque iterators, it will be success. I want to know why this would happen?
thanks for reading, I need you help, please!
Last edited on
Do you have using namespace std; anywhere. It looks like it picks up std::merge from <algorithm>
no, i don't even include algorithm header
but i listen to your advice, prefix sort:: to merge, and then it works.
i am confused, why this would happen?
i don't even include algorithm header
It might be included by other headers. It is using namespace std; which would be a problem. SO if you have it, get rid of it.

Actually, when I think about it, it is probably ADL at work here. So just prefix merge with its namespace, as you did.

When you have vector iterators passed, all five iterators are of the same type and compiler does not know which version std::merge or sort::merge is a better match, as both versions are perfect match (no conversions needed for any argument). So, it gives you an ambiguity error.
If you use deque iterators, then you will have three deque iterators and two vector ones. And because of argument order in std::merge, it is not a perfect match in this case. So sort::merge is chosen
thank you very much
Topic archived. No new replies allowed.