Talk:cpp/algorithm/set difference

The description of comp is not correct. It should be:

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:

 bool cmp(const Type &a, const Type &b);

The signature does not need to have const &, but the function object must not modify the objects passed to it. The type Type must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type.

No, what makes you believe that the types of the two parameters of the compare predicate must be identical? --Cubbi (talk) 06:07, 22 May 2015 (PDT)

I think what @Opium wants to point out is that we shouldn't say "The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively. ". The possible implementation uses both comp(*first1, *first2) and comp(*first2, *first1), thus the value type of InputIt1 needs to be convertible to both Type1 and Type2, and so does that of InputIt2. --D41D8CD98F (talk) 06:38, 22 May 2015 (PDT)

Ah, good point. Yes (libc++, stdlibc++, and visual studio all do that)... then this applies to more than set_difference, several other algorithms have to apply Compare both ways. --Cubbi (talk) 06:55, 22 May 2015 (PDT)

Or perhaps, to make this less of an original research, we could interpret 25.4[alg.sorting] as requiring that Compare must be callable both ways always? It makes a requirement about !comp(a, b) && !comp(b, a), which implies that both must be valid expressions. --Cubbi (talk) 07:18, 22 May 2015 (PDT)

Looks good to me. --D41D8CD98F (talk) 08:50, 22 May 2015 (PDT)

The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2.

Not necessarily. They could be completely unrelated types. As long as cmp(const Type1&, const Type2&) and cmp(const Type2&, const Type1&) are valid, cmp works fine. Example: http://stackoverflow.com/a/15579928

I belive this is a defect in c++ standard. Why should cmp be called in two different ways, if the standard makes sure they are always called in correct order, we don't need two overloads. There is no reason to call cmp in reverse order.

Balki (talk) 11:19, 11 June 2015 (PDT)

great example about cmp with two operator()'s! Looks like that wording needs to be tweaked once again. (the standard does show cmp being called in two ways, quoted above, it just doesn't bother to single out the algorithms that only ever require one way, such as std::sort or std::lower_bound) --Cubbi (talk) 11:28, 11 June 2015 (PDT)

fun fact: STL2.0 (aka Ranges TS) will forbid this example as it will require a common type between two value_types to exist and be admissible as both lhs and rhs of the comparator.. but this note still has to be edited. --Cubbi (talk) 10:45, 24 July 2015 (PDT)

Yet another case of a user confused by how cppreference explains comparators.. --Cubbi (talk) 14:15, 28 August 2015 (PDT)

[edit] Use back_inserter for vector

From the example:

std::inserter(diff, diff.begin())

I think this is invalid, because diff.begin() will be invalidated after the first insert. For vector its better to use back_inserter like in the second part of the example.

std::insert_iterator correctly updates its internal iterator according to the result of internal calls to .insert() (see insert_iterator::operator=), so iterator invalidation isn't an issue --Ybab321 (talk) 03:34, 7 March 2022 (PST)