Can std::min_element (and also std::sort and similar functions from <algorithm>) be used on types with only a partial order?
For example:
auto it = std::min_element(vec.cbegin(), vec.cend(), [](const node* a, const node* b) {
return a->precedes(*b);
});
Here node represents nodes in an DAG (directed acyclic graph), and a.precedes(b) tests it a is an ancestor of b. But if a and b are on different branches, it also returns false, and in that case a.precedes(b) == b.precedes(a) == false.
Per §25.4/3 (emphasis and foot-notes are mine):
For algorithms other than those described in 25.4.3* to work correctly, comp** has to induce a strict weak ordering on the values.
* 25.4.3 is the section for binary search algorithms.
** comp is the custom comparator.
Since std::sort is defined in 25.4.1 and std::min_element is in 25.4.7, then you only need a strict weak ordering on the values, i.e.:
The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:
(4.1) — comp(a, b) && comp(b, c) implies comp(a, c)
(4.2) — equiv(a, b) && equiv(b, c) implies equiv(a, c)
As far as I understand your relation, it does not match the equiv requirement since you may have two nodes where !comp(a, b) && !comp(b, a) but a != b. Typically, if you have a and c on one branch and b on another one, the above won't work because equiv(a, b) == equiv(b, c) == true but equiv(a, c) == false.