惯用Go中的set的最小值

Question

How do I write a function that returns the minimum value of a set in go? I am not just looking for a solution (I know I could just initialize the min value when iterating over the first element and then set a boolean variable that I initialized the min value) but rather an idiomatic solution. Since go doesn't have native sets, assume we have a map[Cell]bool.

Answer 1

Maps are the idiomatic way to implement sets in Go. Idiomatic code uses either bool or struct{} as the map's value type. The latter uses less storage, but requires a little more typing at the keyboard to use.

Assuming that the maximum value for a cell is maxCell, then this function will compute the min:

func min(m map[Cell]bool) Cell {
    min := maxCell
    for k := range m {
        if k < min {
            min = k
        }
    }
    return min
}

If Cell is a numeric type, then maxCell can be set to one of the math constants.

Any solution using a map will require a loop over the keys.

You can keep a heap in addition to the map to find a minimum. This will require more storage and code, but can be more efficient depending on the size of the set and how often the minimum function is called.