Ordered Maps for Go 2 (Using Generics)
When you look at Go code, you will encounter Slices and Maps everywhere. Both data types are simple and have characteristics that make them pivotal for myriads of different algorithms, as well as for general use.
Slices allow you to iterate through their values in order since they store the data sequentially.
Maps, on the other hand, don’t necessarily store their data in order. However, they do provide really fast lookups: O(1) (at least for fixed-size maps).
Their usefulness is undeniable but…
what if we could combine both?
In this tutorial, we’ll be learning the bare bone basics of Generics in Go 2. This feature will be a game-changer. We’ll be harnessing the power of Generics to create an OrderedMap type.
An OrderedMap combines the power of both a slice and map!
You might be thinking that an OrderedMap is already possible today. Yes, but we’ll be making a statically-typed OrderedMap, which means that we get strong type checking from the compiler and linter.
Generics has been the most sought after feature for Go since inception.
The Go 2 playground has been available for a few months now. It’s available here so you can follow along.
The current Generics proposal is available here.
NOTE: The draft proposal is changing rapidly.
Step 1: A perfect OrderedMap
What would the perfect OrderedMap look like? I wrote down 5 characteristics that we will strive to implement.
- It should look like this:
map[KeyType]ValueType - It should retrieve a value like this:
val, exists := m["route"] - It should set a value for a unique key like this:
m["route"] = 66 - It should delete a key and its associated value like this:
delete(m, "route") - It should iterate like this:
for key, value := range m {}where the order is based on the order in which the key-value pair was inserted.
Unfortunately, Generics, as currently proposed, will not be able to perfectly match the syntax above. Only changes to the Go specs can. But we can get the next best thing.
It can be seen from #1 that the OrderedMap can contain only one arbitrary data type for the key and value. It could be string-int pairs or float64-interface{} pairs for example. That is what is meant by statically typed.
Under Go 1, the best we could do is implement an interface{}-interface{} ordered map, where we will need to type-assert the stored value before we can use it. We also lose type checking from the compiler.
Alternatively, we need to use a code-generator to duplicate code for different data type pairs under a different name. eg OrderedMapStringInt and OrderedMapFloat64Mixed.
Step 2: Let’s create our own struct
The OrderedMap requires an ordinary map to store the key-value pairs as well as an ordinary slice to store the order in which keys were inserted. That way when we need to iterate, we can loop through the internal slice to grab each key in order. Each key can then be used to extract its associated value from the internal map.
On the top section of the code snippet, we define our struct as if it was Go 1. We use K and V as placeholder data types.
We are essentially building a blueprint of how the struct should look like if we didn’t have generics, but instead had to manually create a separate struct for each data-type combination. Think of it as code-generation – but at compile time.
On the bottom section, we add extra [] after the struct and function name to inform the compiler exactly what data types can be substituted for the placeholders at compile-time.
The bottom section is the new generics version of the OrderedMap struct and constructor.
From now onwards, every time we refer to the OrderedMap type in our code, we must also specify the placeholders in square-brackets afterwards.
These data type placeholder variables are different from normal variables. Normal variables point to a location in memory at run-time. The placeholder variables exist at compile-time. They inform the compiler how to “generate” the actual struct from the generic blueprint struct that we defined. This is an important distinction that you have to understand to properly comprehend the compiler error messages that you will inevitably encounter as you learn and use generics.
Obviously, a map can’t just have any type of data for its key (K). The data type must support the = operator since the key must be unique. For this reason, we use the special built-in comparable constraint which instructs the compiler to reject any data type that doesn’t support equality.
We want the stored value (V) to be of any arbitrary data type. We leave it unconstrained by using the special built-in any constraint.
Step 3: Getter and Setter
The function’s arguments have a name and type as in Go 1. However, the type is now defined in terms of the generic placeholders used in the definition of the struct.
This allows the compiler to guarantee that the data type of the key and val argument in the function signature exactly match what will ultimately be stored in the internal slice and map of the defined OrderedMap struct.
Step 4: Delete
Delete is straight forward. We have to find the key in the slice and then remove that entry.
Step 5: Iterating
With the current Generics proposal, it’s not possible to get the native range syntax available to ordinary maps and slices. We’ll implement the next best thing.
The Iterator function returns an anonymous function which can be repeatedly called to provide the index, key and corresponding value. Both the index and key must be returned since an ordered map has to provide the best features of both a slice and map.
Let’s test it
In the example above, we’ve chosen to create an int-string map. Because it is statically typed, you can’t attempt to store a different data type for the key or value. The compiler or linter will immediately notify you of your mistake.
This protects your code from many run-time errors that weakly type languages (and Go 1 interface{}-interface{} maps) suffer from.
The full example and output can be found in the Go 2 playground: https://go2goplay.golang.org/p/Du_G8EyiiDB.
Extensions
- A standard slice and map allow you to set the capacity of the underlying memory at initialization. The constructor can be updated to accept an optional
capargument. - Currently, when you delete a key-value pair, you need to iterate over the
keysslice to find the index of the key you want to delete. You can use another map that associates the key to the index in thekeysslice. I’ll leave it to the reader to implement. - Implementing the
lenfunction is also left to the reader.
Note: Tugberk took up the challenge (in comments below) and wrote an amazing response here: http://www.tugberkugurlu.com/archive/implementing-ordered-map-in-go-2-0-by-using-generics-with-delete-operation-in-0-1-time-complexity
Conclusion
I provided a glimpse of its full power and elegance. If you’re like me, you’ll be salivating for Go 2's imminent release.
If you get the chance, you can thank @ianlancetaylor and @griesemer for their hard work and dedication in masterminding the current design proposal.
Go 2 is not expected to be released for at least 1 year. In the meantime, you can use ordered maps from my dataframe-go package: https://godoc.org/github.com/rocketlaunchr/dataframe-go#OrderedMapIntFloat64. You can also use https://github.com/elliotchance/orderedmap which uses container/list behind the scenes.
