Occasionally we want to sort a list of elements or maintain a set of elements with comparator that involves accessing another list.

A popular use case is rather than sorting a list of N objects, we create a list of indexes [0, 1, 2, …, N-1] and sort this list instead.

Another use case is in Dijkstra’s algorithm, we want to maintain a set of unvisited node indexes ordered by their distance to the starting node.

My solution is:
* Have the comparator store a pointer to the distance list, and
* Construct the set of unvisited nodes to use the comparator by using the constructor set<T, Comp>(comp);

The following code illustrates this idea in details:

struct NodeComparator {
  vector<int>* distance;

  NodeComparator() {}
  NodeComparator(vector<int>* distance_) : distance(distance_) {}

  bool operator() (const int& a, const int& b) const {
    if ((*distance)[a] < (*distance)[b]) return true;
    if ((*distance)[a] > (*distance)[b]) return false;
    return a < b;
  }
};

class ShortestPath {
private:
    int n, start;
    vector<int> distance_;
    set<int, NodeComparator> unvisited_node_set_;
public:
    void Execute() {
        // Initialize distance_.
        distance_.resize(n, INF);
        distance_[start] = 0;

        // Construct unvisited_node_set_ with NodeComparator.
        unvisited_node_set_ = set<int, NodeComparator>(NodeComparator(&distance_));*

        // ...
    }

    // ...
};

Practice problems:
1. https://codeforces.com/problemset/problem/20/C: Dijkstra’s algorithm.
2. https://leetcode.com/problems/maximum-frequency-stack/description/: Order stack elements by frequency, then how close they are to the top of the stack.