Deleting and inspecting elements while iterating over object

General Usage
1

I know that deleting elements and iterating over an object at the same time is against good programming practices (regardless, whether we use Julia or other language). I learnt my lesson the hard way. Regardless, I am really interested in understanding what actually happened (underneath?). Let me start with two minimal examples. First one works as expected:

some_array = OrderedSet{}()
for i in 1:4
    push!(some_array, i)
end
for (i, o) in enumerate(some_array)
    delete!(some_array, o)
    println(o)
end
println(some_array)

No funny behaviour observed here. All the elements get deleted.
Then I make a small “meaningless” change:

some_array = OrderedSet{}()
for i in 1:4
    push!(some_array, i)
end
for (i, o) in enumerate(some_array)
    delete!(some_array, o)
    for j in some_array
        nothing
    end
    println(o)
end
println(some_array)

Now, for some reason every second element gets omitted as if the algorithm lost track of the next one, while keeping track of the element id it should point to. Can someone explain what exactly happened here and why? Thanks in advance!

Also, I wonder if there are some good practices you could suggest in similar situations. Obviously my true code was much more complex, but general suggestions are welcome. In my case moving to a “while” loop solved the problem.

2

This sounds like a good case for using Base.filter or Base.filter!, e.g. (equivalently):

filter!(isodd, some_array)

filter!(o -> o % 2 != 0, some_array)

filter!(some_array) do o
    o % 2 != 0
end
3

It’s generally infeasible for iteration adjust for mutation, so it’s generally undefined behavior. The observed difference can be inspected here if you display the internals to dodge the iteration of the OrderedSet itself:

julia> begin
       some_array = OrderedSet{}()
       for i in 1:4
           push!(some_array, i)
       end
       for (i, o) in enumerate(some_array)
           delete!(some_array, o)
           println(o, " ", some_array.dict.keys)
           end
       println(some_array)
       end
1 Any[#undef, 2, 3, 4]
2 Any[#undef, #undef, 3, 4]
3 Any[#undef, #undef, #undef, 4]
4 Any[#undef, #undef, #undef, #undef]
OrderedSet{Any}()

julia> begin
       some_array = OrderedSet{}()
       for i in 1:4
           push!(some_array, i)
       end
       for (i, o) in enumerate(some_array)
           delete!(some_array, o)
           println(o, " ", some_array, " ", some_array.dict.keys)
           end
       println(some_array)
       end
1 OrderedSet{Any}(Any[2, 3, 4]) Any[#undef, 2, 3, 4]
3 OrderedSet{Any}(Any[2, 4]) Any[2, #undef, 4]
OrderedSet{Any}(Any[2, 4])

delete! evidently does not bother to shift remaining elements into uninitialized memory, likely because such actions can occur in hot loops (just not ones that iterate over the ordered dict or set directly). I’m still not sure when exactly the shift occurs, but it evidently needs to when you start another iteration or print it. Again, this is internal behavior, so don’t rely on it staying this way, and you wouldn’t have to if you avoid undefined behavior.

2 Likes
4

Hey Mike, in my case deleting was just a part of a more complex task (and did not even occur every time), but maybe the third block could actually help in some future stuff. Thanks!

5

Thanks for the insight!

6

In that case, it wouldn’t be the absolute fastest code, but you could also use deleteat! to do something like

ids_to_delete = Int[]

for (i, o) in enumerate(some_array)
    # ...

    if # meets criteria for deletion
        push!(ids_to_delete, i)
    end
end

deleteat!(some_array, ids_to_delete)