Is `push!` implemented correctly?

[torfjelde]

I just recently discovered that push! is implemented for Dict and it states the following in the docstring:

Because of this I sort of (maybe naively) expected push!(::OrderedDict, ::Pair) to always insert entries at the end, but this doesn't seem to be the case:

julia> using OrderedCollections

julia> d = OrderedDict(:x => 1)
OrderedDict{Symbol, Int64} with 1 entry:
  :x => 1

julia> push!(d, :y => 2)
OrderedDict{Symbol, Int64} with 2 entries:
  :x => 1
  :y => 2

julia> push!(d, :x => 3)  # Expected `:x => 3` to be after `:y => 2` here
OrderedDict{Symbol, Int64} with 2 entries:
  :x => 3
  :y => 2

Is this intentional?

[timholy]

Presumably this is only an issue with pre-existing keys. To me, it's not entirely obvious what the right answer is. Anyone else have any thoughts?

For reference, Python now guarantees that their dicts are ordered and here's what they do:

>>> d = {'x':1, 'y':2}
>>> d.
d.clear(       d.fromkeys(    d.items(       d.pop(         d.setdefault(  d.values(
d.copy(        d.get(         d.keys(        d.popitem(     d.update(
>>> d['x'] = 3
>>> d
{'x': 3, 'y': 2}

They don't have the analog of push!, but in Julia push!(d, k => v) is (currently) equivalent to d[k] = v.

[torfjelde]

Presumably this is only an issue with pre-existing keys. To me, it's not entirely obvious what the right answer is. Anyone else have any thoughts?

Exactly; I'm also not certain what's "correct" here.

I was somewhat surprised to find that push! was even implemented for AbstractDict, as I usually associate push! with the action of "pushing onto a stack", i.e. not making that much sense in the case of containers without ordering 🤷

[timholy]

It's basically to support adding k/v pairs without needing to destructure the pair. But if your mental model of push! is "to the end" then it's indeed confusing.

On balance I lean towards thinking the current behavior is consistent, but it would be fine to leave this open and see if anyone else chimes in.

[fingolfin]

I agree the current behavior is consistent. Insertion order is preserved. Using push! as above to update an existing key is not an insertion, it's an update. OK perhaps that is an overly legalistic point of view, but there is also no real good alternative.

If someone really needs to update the order, they'll have to first delete the key and then re-insert it.

[timholy]

If someone has a concrete proposal for how to make this clearer, let's get that out explicitly. Otherwise I propose we close this issue.

[fingolfin]

We don't provide a docstring for push!, so the only place to make this clearer would be the manual. One could add do the (very short) section https://juliacollections.github.io/OrderedCollections.jl/dev/#OrderedDicts a list of remarks about behavior.

That could then explain this push! question and also explain how == works (see #82) and maybe a few other points.