Sorting Go Dictionaries

Introduction

Unlike other languages, in Go, dictionaries (maps) are unordered collections. In this lab, we will learn about sorting dictionaries and how to use them more flexibly.

Key Concepts:

• Sorting dictionaries
• Swapping keys and values in a dictionary
• Slices of dictionaries
• Dictionaries with slices as values
• Reference type characteristics of dictionaries

Skills Graph

Sorting Dictionaries

Create a map.go file in the ~/project directory:

touch ~/project/map.go

Write the following code into the map.go file:

package main

import (
    "fmt"
)

func main() {
    m := map[string]int{
        "Alice": 99,
        "Bob": 38,
        "Charlie": 84,
    }
    for key, value := range m {
        fmt.Println(key, value)
    }
    fmt.Println("\nInsert Data")
    m["David"] = 25
    for key, value := range m {
        fmt.Println(key, value)
    }
}

Run the program:

go run ~/project/map.go

The output of the program may look like this:

Charlie 84
Bob 38
Alice 99

Insert Data
David 25
Charlie 84
Bob 38
Alice 99

The output may vary since the order of the inserted data is not fixed.

You can try running the program multiple times and observe that the order of the inserted data may vary.

But sometimes we need to sort the dictionary after inserting data. How can we achieve that?

Since a map itself cannot be sorted, we can convert the map into a slice and then sort the slice.

Sort by Key

First, let's learn how to sort the dictionary by key.

Here are the steps:

• Convert the keys of the dictionary into a slice
• Sort the slice
• Retrieve the corresponding values using the dictionary's lookup method

Write the following code into the map.go file:

package main

import (
    "fmt"
    "sort"
)

func main() {
    // Initialize the dictionary
    m1 := map[int]string{
        3: "Bob",
        1: "Alice",
        2: "Charlie",
    }
    keys := make([]int, 0, len(m1)) // Initialize the slice with capacity
    for key := range m1 {
        // Convert the key to a slice
        keys = append(keys, key)
    }
    // Sort the key slice using the sort package
    sort.Ints(keys)
    for _, key := range keys {
        // The output is in order now
        fmt.Println(key, m1[key])
    }
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

1 Alice
2 Charlie
3 Bob

Through this approach, we have achieved sorting the dictionary based on the key.

Swapping Keys and Values in a Dictionary

Before we explain how to sort by value, let's learn how to swap the keys and values in a dictionary.

Swapping keys and values means interchanging the positions of keys and values in a dictionary, as shown in the figure below:

The implementation code is simple. Write the following code into the map.go file:

package main

import "fmt"

func main() {
    m := map[string]int{
        "Alice": 99,
        "Bob":     38,
        "Charlie":   84,
    }
    m2 := map[int]string{}
    for key, value := range m {
        m2[value] = key
    }
    fmt.Println(m2)
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[38:Bob 84:Charlie 99:Alice]

The essence of this code is to extract the keys and values from the original dictionary, and then reinsert them into the dictionary. It's simple and straightforward.

Sort by Value

Combining the logic of sorting the dictionary by key and swapping keys and values in a dictionary, we can sort the dictionary by value.

Write the following code into the map.go file:

package main

import (
    "fmt"
    "sort"
)

func main() {
    // Initialize the dictionary
    m1 := map[string]int{
        "Alice": 99,
        "Bob":     38,
        "Charlie":   84,
    }

    // Initialize the reversed dictionary
    m2 := map[int]string{}
    for key, value := range m1 {
        // Generate the reversed dictionary m2 by swapping the key-value pairs
        m2[value] = key
    }

    values := make([]int, 0) // Initialize the sorting slice
    for _, value := range m1 {
        // Convert the values of the original dictionary to a slice
        values = append(values, value)
    }
    // Sort the value slice using the sort package
    sort.Ints(values)

    for _, value := range values {
        // The output is in order now
        fmt.Println(m2[value], value)
    }
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

Bob 38
Charlie 84
Alice 99

Now we have sorted the dictionary based on its values.

Sorted by sort.Slice

If the version of Go is later than 1.7, we can use the sort.Slice function to quickly sort a map by key or value.

Here is an example:

package main

import (
    "fmt"
    "sort"
)

func main() {
    m1 := map[int]int{
        21: 99,
        12: 98,
        35: 17,
        24: 36,
    }

    type kv struct {
        Key   int
        Value int
    }

    var s1 []kv

    for k, v := range m1 {
        s1 = append(s1, kv{k, v})
    }

    sort.Slice(s1, func(i, j int) bool {
        return s1[i].Key < s1[j].Key
    })

    fmt.Println("Sorted in ascending order by key:")
    for _, pair := range s1 {
        fmt.Printf("%d, %d\n", pair.Key, pair.Value)
    }
}

Run the program:

go run ~/project/map.go

The output is as follows:

Sorted in ascending order by key:
12, 98
21, 99
24, 36
35, 17

In this program, we used a struct to store the key-value pairs from the map. We then sorted the slice of structs using the sort.Slice() function and an anonymous comparison function.

We can also use sort.Slice to sort the map in descending order by key or in ascending order by value.

Little Test

Create a map2.go file and modify the code from the previous section to sort the map in descending order based on the value.

Expected Output:

Run the program:

go run ~/project/map2.go

Sorted in descending order by value:
12, 98
21, 99
24, 36
35, 17

Requirements:

• The map2.go file should be placed in the ~/project directory.
• You must use the sort.Slice function.

Slices of Dictionaries

Just as we can use arrays or slices to store related data, we can also use slices where the elements are dictionaries.

Write the following code into the map.go file:

package main

import "fmt"

func main() {
    // Declare a slice of maps and initialize it using make
    var mapSlice = make([]map[string]string, 3)
    for index, value := range mapSlice {
        fmt.Printf("index:%d value:%v\n", index, value)
    }
    fmt.Println("Initialization")
    // Assign values to the first element of the slice
    mapSlice[0] = make(map[string]string, 10)
    mapSlice[0]["name"] = "labex"
    mapSlice[0]["password"] = "123456"
    mapSlice[0]["address"] = "Paris"
    for index, value := range mapSlice {
        fmt.Printf("index:%d value:%v\n", index, value)
    }
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

index:0 value:map[]
index:1 value:map[]
index:2 value:map[]
Initialization
index:0 value:map[address:Paris name:labex password 123456]
index:1 value:map[]
index:2 value:map[]

The code demonstrates the initialization of a slice of maps and the assignment of values to the first element of the slice.

Dictionaries with Slices as Values

We can also use dictionaries with slices as values to store more data in a dictionary.

Write the following code into the map.go file:

package main

import "fmt"

func main() {
    var sliceMap = make(map[string][]string, 3)
    key := "labex"
    value, ok := sliceMap[key]
    if !ok {
        value = make([]string, 0, 2)
    }
    value = append(value, "Paris", "Shanghai")
    sliceMap[key] = value
    fmt.Println(sliceMap)
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[labex:[Paris Shanghai]]

The code first declares a slice dictionary type and then initializes a normal dictionary. It then adds a slice as a value to the dictionary.

Reference Type Characteristics of Dictionaries

Arrays are value types, so assigning and passing them to functions changes the original array. In other words, we can modify the array itself by passing it to a function.

Write the following code into the map.go file:

package main

import "fmt"

func modifyMap(x map[string]int) {
    x["Bob"] = 100
}

func main() {
    a := map[string]int{
        "Alice": 99,
        "Bob":     38,
        "Charlie":   84,
    }
    // Because the map is passed by reference, the modification in modifyMap changes the original dictionary
    modifyMap(a)
    fmt.Println(a) // map[Alice:99 Bob:100 Charlie:84]
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[Alice:99 Bob:100 Charlie:84]

In the example, we demonstrated the reference transfer characteristic of a dictionary, where the reference is passed between functions, and the modifications in the referenced dictionary directly affect the original one.

Summary

In this lab, we have learned about advanced usage of maps in Go, including:

• Sorting maps by key or value
• Swapping keys and values in a map
• Using slices of maps
• Using maps with slices as values
• Reference type characteristics of maps