Talk:cpp/algorithm/merge

I have some difficulties understanding the requirements for the comparator comp. On the page, it says

"The signature of the comparison function should be equivalent to the following:"

bool cmp(const Type1 &a, const Type2 &b)

but in the code example (and actually in my mingw gcc sources) it is used as

if(comp(*first2, *first1))

Thinking of a case where Type1!=Type2, these lines are conflicting. This should probably be corrected, but I do not know which one is the right one. In my working draft of the C++11 standard (2012-01-16), no requirement for the order of arguments is given, so maybe this is even implementation-dependent and there is no correct answer. --141.30.83.52 00:06, 7 November 2014 (PST)

Interesting observation. [alg.merge] actually puts three separate requirements on comp: that the first input range is sorted with respect to comp, that the second input range is sorted with respect to comp, and that, as a post-condition, the resulting range is sorted with respect to comp ("sorted with respect to comp" is defined earlier in [alg.sorting] and involves calling comp with two dereferenced iterators). So it needs to be able to take two arguments convertible from InputIt1's value type, as well as two arguments convertible from InputIt2's value type, as well as two arguments convertible from OutputIt's value type (although I feel that last one is slightly overspecified).. now how to express it in the wiki? Same applies to several other algorithms that work on two sorted ranges, like std::set_union, looks like this needs a new template. --Cubbi (talk) 06:30, 7 November 2014 (PST)

Thinking about it a little more, it is kind of obvious that Type1 and Type2 need to be convertible into each other, otherwise saving the result to the output range would not work. Maybe one could just have comp take two arguments of type Type and ask for InputIt1, InputIt2 and OutputIt to be implicitly convertible to Type. --141.30.83.52 23:42, 11 November 2014 (PST)

distance arguments seems to be reversed

The complexity for newest functions seems reversed:

2,4) O(std::distance(last1, first1) + std::distance(last2, first2))

I think it should be:

2,4) O(std::distance(first1, last1) + std::distance(first2, last2)) 24.225.200.38 10:28, 24 June 2017 (PDT) Philippe M

yes indeed, fixed, thanks. --Cubbi (talk) 11:17, 24 June 2017 (PDT)