Stl Ordering - Strict Weak Ordering

stl ordering - strict weak ordering

A partial order would not be sufficient to implement some algorithms, such as a sorting algorithm. Since a partially ordered set does not necessarily define a relationship between all elements of the set, how would you sort a list of two items that do not have an order relationship within the partial order?

Doesnt stl sort require a strict weak ordering to work?

You are right, std::sort requires the comparer to define a strict weak ordering.

Which means that std::less_equal should not be used with std::sort. It can still be used with a number of other standard algorithms though, which take a binary function and which do not have the strict weak ordering requirement.

Why does priority_queue in STL not follow strict weak ordering?

The problem is that the negation of your strict_weak_order (that uses >) is <= and that is not a strict weak order. A strict weak order R has to satisfy x R x == false for all x. However, R equal to <= yields (x <= x) == true.

You need to reverse the order of arguments (which corresponds to <) instead.

bool comparer_function(const int& val1 , const int& val2){
    return strict_weak_order_function(val2 , val1);
}

struct Compaper_functor{
    bool operator()(const int& val1 , const int& val2){
        return strict_weak_order_function(val2 , val1);
    }
};

Note however that a std::priority_queue has a std::less as default comparator, but that gives a max-heap (i.e. [5, 4, 3, 2, 1] output from the same input), so to get a min-heap (i.e. with output [1, 2, 3, 4, 5] from input [5, 4, 3, 2, 1]) you need to pass std::greater, see e.g. this:

#include <queue>
#include <iostream>

int main()
{
    auto const v  = std::vector<int> { 5, 4, 3, 2, 1 };

    // prints 5 through 1
    for (auto p = std::priority_queue<int> { v.begin(), v.end()  }; !p.empty(); p.pop())
        std::cout << p.top() << ',';
    std::cout << '\n';

    // prints 1 through 5
    for (auto p = std::priority_queue<int, std::vector<int>, std::greater<int>> { v.begin(), v.end()  }; !p.empty(); p.pop())
        std::cout << p.top() << ',';
    std::cout << '\n';
}

Live Example

Crash in std::sort - sorting without strict weak ordering

I'll just go off of the comment in your code and explain what's wrong with it (if anything), and how you would fix it.

// Sort the participants so that ones with more action points (mAp) go first.

Good so far

// When there is a tie, participants with the same disposition (mDisposition) as the initiator of the battle (mBattleInitiator) go first.

What if both participants have the same disposition as the initiator? Even if you can guarantee that no 2 elements will satisfy this condition, the sort algorithm is allowed to compare an element against itself. This test would return true in that case, violating one of the conditions of a strict-weak ordering, which is that an element must compare equal to itself (i.e. compare(a,a) must always be false).

Perhaps instead you want to say that if a has the same disposition as the initiator, and b does not, then a should be considered less than b. This can be encoded as:

return dispositionOfA == mBattleInitiator && dispsitionOfB != mBattleInitiator;

So your full test would look like this:

if (a.mAp > b.mAp)
    return true;
if (a.mAp < b.mAp)
    return false;

return a.mAiComponent->mDisposition == mBattleInitiator &&
       b.mAiComponent->mDisposition != mBattleInitiator;

strict weak ordering confusion

If it "doesn't make sense" for one Airport to come before another Airport then the use of std::set<Airport> doesn't make sense, either. This container leverages the order amount elements to locate objects in O(log(n)) operations (where n is the size of the container). If you can identify object by identity only, the best complexity you can achieve is O(n). You can use a combination of std::find() or std::find_if() and one of the sequence containers, e.g., std::vector<Airport> or std::deque<Airport>.

Since you don't need to define an order in terms of operator<(), it may be reasonable to just bring the Airports into some order for the purpose of locating them in a std::set<Airport> which is done by using a different comparison function object than std::less<Airport>. The attribute you currently have in your Airport object don't really look like suitable keys, though. In fact, they all look as if they would be mutable, i.e., you probably wouldn't want a std::set<Airport> anyway because you can't modify the elements in an std::set<T> (well, at least, you shouldn't; yes, I realize that you can play tricks with mutable but this is bound to break the order of the elements).

Based on this, I'd recommend to use a std::map<std:string, Airport>: the std::string is used to identify the airport, e.g., using the airport codes like "JFK" for the John F. Kennedy Airport in New York or "LHR" for London Heathrow. Conveniently, there is already a strict weak order defined on strings.

That said, to define a strict weak order on a set of objects O, you need to a binary relation r(x, y) such that the following conditions hold for elements x, y, and z from O:

• irreflexive: r(x, x) == false
• asymmetric: r(x, y) == true implies r(y, x) == false
• transitive: r(x, y) == true and r(y, z) == true implies r(x, z) == true
• incomparability: r(x, y) == false and r(y, x) == false and r(y, z) == false and r(z, y) == false implies r(x, z) == false and r(z, x) == false

The first three should be simple enough. The last one is a bit odd at first but actually not that hard either: The basic idea is that the relation doesn't entirely order element but groups them into equivalent classes. If you think of the relation r to be "smaller than" it just says that if neither x is smaller than y nor y is smaller than x, then x and y are equivalent. The incomparable elements are just equivalent.

The standard containers work with a strict weak order but, e.g., std::set<T> and std::map<K, V> keep just one version of equivalent keys. It is nice that this is sufficient but it is often simpler to just use a total order which is a strict weak order where for each pair of element x and y either r(x, y) == true or r(y, x) == true (but, due to the asymmetry not both).

Does greater operator satisfy strict weak ordering?

Does greater operator “>” satisfy strict weak ordering?

The mathematical strict greater than relation is a strict weak ordering.

As for the operator in C++ langauge: For all integers types: Yes. In general: No, but in most cases yes. Same applies to strict less than operator.

---

As for the confusing quote, "is less than" in that context intends to convey that means that the the end result of the sort operation is a non-decreasing sequence i.e. objects are "less" or equal to objects after them. If std::greater is used as comparison object, then greater values are "lesser" in order.

This may be confusing, but is not intended to exclude strict greater than operator.

---

what is the case where > doesn't satisfy strict weak ordering?

Some examples:

• Overloaded operators that don't satisfy the properties.
• > operator on pointers that do not point to the same array has unspecified result.
• > does not satisfy irreflexivity requirement for floating point types in IEEE-754 representation unless NaNs are excluded from the domain.

---

Related Topics