Lexicographical order

---

# Lexicographical order

Wai-Shing Luk

2018-09-12 📅

---

What is Lexicographical order
-----------------------------

-   Given two partially ordered sets $A$ and $B$
-   The lexicographical order on the Cartesian product $A \times B$ is
    defined as:
    -   $(a,b) \le (a',b')$ iff $a < a'$ or ($a = a'$ and $b \le b'$).

---

How
-------

-   `std::tuple<>` and `std::make_turple()`
-   `std::valarray<>` for vector space

---

Properties
----------

-   Preserve order (min, max, sorting)
-   Work with many algorithms in standard library:
    -   `std::max_element()`
    -   `std::sort()`
-   Triangle inequality
    -   Dijkstra's algorithm
-   Convexity
-   duality
-   orthogonality

---

Applications
------------

-   break tie
    -   leftmost point
    -   plane sweeping
-   multiobjective optimization

---

📚 Example
-----------

```cpp
template <typename T>
struct Point { T _x, _y; };

template<typename T>
ostream& operator<<(ostream& os, const Point<T>& p) {
    os << '(' << p._x << ", " << p._y << ')';
    return os;
}

template <typename Tp>
inline auto Leftmost(const std::vector<Tp>& P) {
    return std::min_element(std::begin(P), std::end(P),
        [](auto& p1, auto& p2){ // c++14
            return tie(p1._x, p1._y) < tie(p2._x, p2._y); });
}
```

---

📚 Example (cont'd)
----------------

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;

int main()
{
    std::vector<Point<int>> Poly = {
        {3, 4}, {5, -2}, {2, 10}, {8, 7}, {5, -9}
    };

std::cout << *Leftmost(Poly) << std::endl;
}
```

---

# Q&A 🎤