Add a `sort` method to Dictionary

[aaronfranke]

Describe the project you are working on

A game with a lot of dynamic code.

Describe the problem or limitation you are having in your project

Currently, there is no way to sort a Dictionary to make the keys be in order:

func _ready() -> void:
    var dict = {
        "key4": "value4",
        "key2": "value2",
        "key1": "value1",
        "key3": "value3",
    }
    print(dict) # { "key4": "value4", "key2": "value2", "key1": "value1", "key3": "value3" }

I need the ability to do this so that I can have consistency between the in-memory data and what I store on MongoDB, which automatically sorts all Dictionaries I send to it. I also need it so that I can convert a Dictionary to a String and have identical contents result in identical strings.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

I propose adding a sort method so you can do this:

func _ready() -> void:
    var dict = {
        "key4": "value4",
        "key2": "value2",
        "key1": "value1",
        "key3": "value3",
    }
    dict.sort()
    print(dict) # { "key1": "value1", "key2": "value2", "key3": "value3", "key4": "value4" }

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

https://github.com/godotengine/godot/pull/77213 Add a sort method to Dictionary and HashMap and expose it.

If this enhancement will not be used often, can it be worked around with a few lines of script?

It can be worked around in GDScript, but not efficiently, and not in-place. I don't know how often it will be used.

Is there a reason why this should be core and not an add-on in the asset library?

It's a computation-heavy operation and very related to Dictionary, so it would be most optimal to put it in core.

[KoBeWi]

Actually the Dictionary is sorted automatically when it's serialized, so you can probably do something like dict = str_to_var(var_to_str(dict)).

[zf-moth]

Actually the Dictionary is sorted automatically when it's serialized, so you can probably do something like dict = str_to_var(var_to_str(dict)).

That doesn't sound very optimal tho. Plus array has sort function but dictionary doesn't?

[AThousandShips]

Agreed, but it's a workaround that exists

Plus array has sort function but dictionary doesn't?

They are pretty different data structures so one having it and another not having it isn't unusual, most structures like this doesn't, in fact most unordered associative structures dont

[jtnicholl]

Isn't the fact that Dictionary has an order at all considered to be just an implementation detail? I know it is in some languages. Could there be any negative consequences to making it a supported feature?

[aaronfranke]

@jtnicholl When printing a Dictionary, or saving to JSON, there has to be some kind of order.

[Malcolmnixon]

Many languages started with a single type of associative-container which (based on the authors preferences) was either sorted or unsorted; but most of them added the opposing type of container later in the language development:

Language	Container	Implementation	Sortability	Average Performance
C++	std::map	red-black tree	sorted	O(log n)
C++	std::unordered_map	hash map	unsorted	O(1)
C#	Dictionary	hash map	unsorted	O(1)
C#	SortedDictionary	binary tree	sorted	O(log n)
Java	HashMap	hash map	unsorted	O(1)
Java	TreeMap	red-black tree	sorted	O(n)
Python 3.6-	dictionary	Hash table	unsorted	O(1)
Python 3.7+	dictionary	dense/sparse array	sorted	O(1)

Allowing a dictionary to be sorted (or sortable) constrains implementations and may result in sacrificing performance. Python shows this isn't always the case; however the Python implementation is fairly complicated.

[aaronfranke]

@Malcolmnixon This method would not run automatically, only when you explicitly call it. So it doesn't sacrifice performance for existing use cases, it does not affect those.

[Malcolmnixon]

So the ability to support a sort() method on Dictionary is dependent on the dictionary supporting reordering. This is something we have today with HashMap and its open-addressing implementation, but once we add sort() we wouldn't be able to swap that implementation with std::map or std::unordered_map - something we probably wouldn't want to do anyway?

[AThousandShips]

Dictionary has and should preserve insertion ordering so a backing data structure that doesn't isn't an option anyway

[nanoquack]

Why not add a method keys_sorted() (and maybe keys_custom_sorted())? That should be implementable with any backing data structure, would not change the order in the Dictionary, but could be used to access the Dictionaries content ordered if required

[aaronfranke]

@nanoquack There is no difference between that and just getting .keys(), then sorting that.

I'm not trying to access individual parts of the Dictionary in a sorted way, I'm trying to serialize the entire thing sorted.

[CyberSkull]

How would this be different than calling the following?

for key in stuff.keys().sort()
    do_thing_with(stuff[key])

[aaronfranke]

@CyberSkull It would be the same as this, but faster, and in-place:

var sorted: Dictionary = {}
for key in stuff.keys().sort()
    sorted[key] = stuff[key]
stuff = sorted

[morphles]

What is this discussion even? :( Obviously we need sort-able hash map, and sort should be doable by using user supplied function. Now I need to do some manipulation of stuff and I'll have to add a layer of abstraction, where array will be dict indexes and sort array with function that references array. All very roundabout. Compared to say PHP just horrific.