# Taking \`push!\` and \`pop!\` seriously

**URL:** <https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326>\
**Category:** Internals & Design\
**Tags:** proposal\
**Created:** [February 7, 2020, 9:53pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326 "2020-02-07T21:53:27Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![kevin.squire](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kevin.squire/32/62_2.png) [@kevin.squire](https://discourse.julialang.org/u/kevin.squire)\
**Post date:** [February 7, 2020, 9:53pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/1 "2020-02-07T21:53:27Z")

</div>

TL;DR: currently, `push!` and `pop!` conflate two different meanings (adding/removing elements to unordered/sorted collections vs. adding elements to the end of `Vector`s, `Stack`s, `Deque`s, etc). These meanings should be split into different functions in Julia 2.0.

# Background

[`DataStructures.jl`](https://juliacollections.github.io/DataStructures.jl/latest/) implements a number of data structures, including `Stack`, `Queue`, `Deque`, and `CircularDeque`, which are meant to be more performant implementations of stacks and queues (and deques) than just using `Vector`s.

`Stack`, `Deque`, and `CircularDeque` all use the same functions as base (`push!`, `pop!`, `pushfirst!`, and `popfirst!`). `Queue` has never been moved over to that interface, and still uses `enqueue!` and `dequeue!`

We’re having a [discussion in `DataStructures.jl`](https://github.com/JuliaCollections/DataStructures.jl/issues/296) around moving `Queue` to the standard interface.

Currently, we have the following:

| Data structure | `push!` | `pop!` | `pushfirst!` | `popfirst!` | `enqueue!` | `dequeue!` |
| --- | --- | --- | --- | --- | --- | --- |
| 
## Base
 | | | | | | |
| Vector | ✔ | ✔ | ✔ | ✔ | | |
| Set | ✔ | ✔ | | | | |
| Dict | ✔ | ✔ | | | | |
| 
## DataStructures.jl
 | | | | | | |
| Stack | ✔ | ✔ | | | | |
| Deque | ✔ | ✔ | ✔ | ✔ | | |
| CircularQueue | ✔ | ✔ | ✔ | ✔ | | |
| OrderedDict, OrderedSet | ✔ | ✔ | ◯ | ◯ | | |
| SortedDict, SortedSet | ✔ | ✔ | | | | |
| ─────────── | ───── | ───── | ───── | ───── | ───── | ───── |
| Queue, PriorityQueue (current) | | | | | ✔ | ✔ |
| Queue, PriorityQueue (DS proposal A) | ✔ | ✔ | | | | |
| Queue, PriorityQueue (DS proposal B) | | ✔ | ✔ | | | |

✔= implemented  
◯ = not implemented, but could/should be  
────────────────────────────────────────

From this, we can see that `push!` and `pop!` have two different meanings.

1. For unordered and sorted collections, they simply mean to add or remove elements from the collection.
2. For every other collection listed, they (necessarily) mean to add or remove elements from the end of the collection, and they carry their traditional meaning.

There are two proposals for the `Queue` interface

“DS Proposal A” above suggests that `Queue` should be treated like `Set`, `Dict`, and `SortedDict/SortedSet`, (and perhaps `Stack`), since there’s only one way to add things to the collection.

“DS Proposal B” above suggests that `Queue` should be treated like a `Vector`, `Deque`, `CircularDeque`, (and perhaps `OrderedDict`, `OrderedSet`, and `Stack`), since there’s a distinction as to whether things are added to the front or back of the collection.

Both are valid perspectives, and this suggests that the fact that `push!` and `pop!` are used for adding/removing elements from unordered and sorted collections should be revisited.

# Proposal 1

For Julia 2.0, `pop!` and `push!` should be deprecated for `Dict`s, `Set`s (and `SortedDict/SortedSet`s), and a separate function for adding/removing elements into unordered or sorted collections should be implemented. Possibilities include:

- `push!(s::Set, elem)` ⇒
  - `add!(s, elem) # this was the name in Julia 0.1! `
  - `insert!(s, elem)`

- `pop!(s::Set, elem)` ⇒ `remove!(s, elem)`

For `delete!`, see item #1 under **Notes**.

# Proposal 2

Switch to [GitHub - andyferris/Dictionaries.jl: An alternative interface for dictionaries in Julia, for improved productivity and performance](https://github.com/andyferris/Dictionaries.jl) as the main dictionary interface. This would be a much larger discussion, but has the benefit here that `push!` and `pop!` would not be defined on unordered collections.

# Notes

1. `delete!(s, elem)` already exists; it returns the updated collection, as opposed to `pop!` (currently), which returns the removed element:

```julia
julia> s = Set([1,2,3])
Set([2, 3, 1])

julia> pop!(s)
2

julia> pop!(s,3)
3

julia> delete!(s, 1)
Set(Int64[])

```

# References

Original discussion/PR where `push!` and `pop!` were originally defined on `Dict` and `Set`:

- [JuliaLang/julia/#3405](https://github.com/JuliaLang/julia/issues/3405)
- [JuliaLang/julia/#3439](https://github.com/JuliaLang/julia/pull/3439)

–  
Kevin

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 8, 2020, 9:13am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/2 "2020-02-08T09:13:42Z")

</div>

Thanks for the detailed writeup and bringing up this issue.

I think that

1. just adding an element to a collection is a _without being concerned about the “location”_ (eg unordered collections) is a valid use case, for which we have `push!`.

2. Types for which it makes sense could support the following contract:

3. `pop!` reverses `push!`, `popfirst!` reverses `pushfirst!`, etc. Each only needs to be defined when the corresponding method is defined. The contract is

4. **Dictionaries and other collections which use indexing by keys should be handled by a separate interface** , possibly [GitHub - andyferris/Dictionaries.jl: An alternative interface for dictionaries in Julia, for improved productivity and performance](https://github.com/andyferris/Dictionaries.jl).

From a practical perspective, my understanding is that 2.0 is not on the immediate horizon, so maybe packages are the best way to explore this design space.

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [February 8, 2020, 10:22am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/3 "2020-02-08T10:22:51Z")

</div>

@Tamas_Papp: but for un-ordered collections `pop!` cannot be the inverse of `push!` unless you keep track of the insertion order (which makes it an ordered collection). Example:

```julia
s::Set
push!(s, an_item)
pop!(s) # to return an_item the Set s would need to keep track of insertion order, which would thus be an OrderedSet

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 8, 2020, 12:54pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/4 "2020-02-08T12:54:24Z")

</div>

Excellent point, I edited the suggestion above.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [February 8, 2020, 4:00pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/5 "2020-02-08T16:00:46Z")

</div>

It may look strange at first, but may be it would make sense to have `pop!` for un-ordered collection, just it should have no promises of what element is returned? Something like this

```julia
function pop!(s::Set)
    el = first(s)
    delete!(s, el)
    el
end

s = Set([1, 2])
push!(s, 3) # s == Set([1, 2, 3])
pop!(s) # 2; s == Set([1, 3])

```

I am trying to imagine scenario, when it can be useful. Definitely it should be something, when order of element processing is irrelevant. May be for example multi thread application? One may have set of unique objects, which should be processed in different threads, but order in which they’ll be processed does not matter. Of course one can collect `Vector` of some objects and at some point he could apply `unique` function to them, or he can have a `Set` which should be `collect` later, but it looks unnecessary if you may just `pop!` from the `Set`.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 8, 2020, 4:29pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/6 "2020-02-08T16:29:11Z")

</div>

> [@Skoffer](#):
>
> One may have set of unique objects, which should be processed in different threads, but order in which they’ll be processed does not matter.

We have iteration for this.

I don’t think that destructively consuming an unordered collection is a very common scenario.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [February 8, 2020, 5:21pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/7 "2020-02-08T17:21:48Z")

</div>

> [@Tamas\_Papp](#):
>
> > [@Skoffer](#):
> >
> > One may have set of unique objects, which should be processed in different threads, but order in which they’ll be processed does not matter.
> 
> We have iteration for this.

You could not `pop` same element in two different threads. How would you like to implement it with iteration?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 9, 2020, 7:56am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/8 "2020-02-09T07:56:56Z")

</div>

Note that `pop!` for `Set` (which is a `Dict`) is not thread safe at the moment, and [it unlikely to ever be](https://discourse.julialang.org/t/can-dicts-be-threadsafe/27172/6). If I wanted to consume an unordered collection by threads, I would just design an appropriate data structure for this (with locks etc).

In any case, I think that this use case (mutation of unordered containers by multiple threads) is a red herring, and just distracts from the main API.

Personally, I would prefer a clean, simple API, with some clear contracts, even if it does not support all possible combinations one can think of — in fact, I would consider _not_ supporting some methods an advantage when it cannot be done in a consistent way.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 9, 2020, 8:13am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/9 "2020-02-09T08:13:14Z")

</div>

Does it make sense to add `popany!`/`pushany!` to make it clear that you don’t care from/to where the element is popped/added? In this scenario, we’d deprecate `pop!`/`push!` for unordered containers to enforce at-the-end semantics.

Alternatively, `pop!`/`push!` can keep the current maybe-anywhere semantics and we can add `poplast!`/`pushlast!` for strict at-the-end semantics.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [February 9, 2020, 8:17am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/10 "2020-02-09T08:17:07Z")

</div>

Thanks for interesting link about thread safety in Julia! 🙂

In that case what about something like

```julia
pop_r!(c::Container, s::Semafor) # see strtok_r in C for motivation in name

```

?

IMO it still has place in discussion about general containers API.

> [@Tamas\_Papp](#):
>
> I would consider _not_ supporting some methods an advantage when it cannot be done in a consistent way.

I fully agree. Just have to add that missing function which could be implemented is inconsistency too!

`pop!(s:Set)` from my POV has same logic as is in getting **first** element from `for i in set`.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [February 9, 2020, 8:24am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/11 "2020-02-09T08:24:40Z")

</div>

I vote for alternative because it is backward compatible.

---

<div class="post-metadata">

**Author:** ![kevin.squire](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kevin.squire/32/62_2.png) [@kevin.squire](https://discourse.julialang.org/u/kevin.squire)\
**Post date:** [February 12, 2020, 11:19pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/12 "2020-02-12T23:19:19Z")

</div>

Thank you to everyone for the replies! I like Tamas’s proposal. I think there are just a few corner cases that need to be answered.

> [@Tamas\_Papp](#):
>
> Types for which it makes sense could support the following contract:
> 
> ```julia
> pushfirst!(collection, item)
> collection[firstindex(collection)] == item
> 
> ```
> 
> and similarly for `pushlast!` / `lastindex` .

I rather like the explicit addition of `pushlast!` and `poplast!`. This should be non-breaking (it’s just adding functionality), so if accepted, it could go in to a 1.x version of Julia.

The main question being debated in the `DataStructures.jl` issue I referenced is what to do with `Queue`. If we follow Tamas’s proposal, then we should definitely implement `pushfirst!` and `poplast!`.

However, should we also implement

- `push!` (as an alias for `pushfirst!`) and
- `pop!` (as an alias for `poplast!`)?

This slightly conflicts with the suggestion that

> [@Tamas\_Papp](#):
>
> `pop!` reverses `push!` , `popfirst!` reverses `pushfirst!` , etc

since for a `Queue`, they don’t exactly reverse one another.

My inclination is that implementing `push!` and `pop!` for `Queue`s is fine, and to just clarify the “reverses” wording here.

If there aren’t any more comments, I’ll move this to an issue in Julia at some point.

Cheers!  
Kevin

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 13, 2020, 7:45am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/13 "2020-02-13T07:45:26Z")

</div>

For `Queue`, I would suggest a `pushfirst!` and `poplast!`, both without an “inverse”.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [February 13, 2020, 8:02am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/14 "2020-02-13T08:02:51Z")

</div>

`Queue` has only one way in and one way out, so `push!` and `pop!` make sense to me.  
Otherwise we end up making the code less generic.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 13, 2020, 9:52am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/15 "2020-02-13T09:52:32Z")

</div>

`Channel` defines `push!` and `popfirst!` but not `pop!` or `pushfirst!`. So, it is strange to define `push!`/`pushfirst!` when `popfirst!`/`pop!` does not work, if you want to make your API close to `Base`.

But if you add `poplast!`/`pushlast!` to the generic collection API, I think it makes sense for `push!` and `pop!` to be callable for any type that defines `*first!` or `*last!`. They become location agnostic API where the target collection can chose its favorite location.

`push!` is useful for defining generic “`collect`”

```julia
for x in input
    push!(sink, f(x))
end

```

and `pop!` is useful for defining generic “iterator”

```julia
while !isempty(source)
    f(pop!(source))
end

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 13, 2020, 11:15am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/16 "2020-02-13T11:15:34Z")

</div>

> [@tkf](#):
>
> become location agnostic API where the target collection can chose its favorite location.
> 
> `push!` is useful for defining generic “ `collect` ”

I think that to maintain current semantics for ordered collections, this requires that `push!` inserts last, so it cannot choose an arbitrary location.

> [@dpsanders](#):
>
> Otherwise we end up making the code less generic.

I usually think of code being generic in relation to an API. There are various trade-offs here about what that API specifies (does insertion happen at a particular location or order? does `pop!` deliver a particular element, or any one will do?), but I am not sure it is common to have a use case where eg FIFO and LIFO collections would otherwise be interchangeable.

Maybe traits traits that describe various assumptions would make sense? But perhaps that’s just overcomplicating it.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [February 13, 2020, 3:45pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/17 "2020-02-13T15:45:42Z")

</div>

> [@Tamas\_Papp](#):
>
> I am not sure it is common to have a use case where eg FIFO and LIFO collections would otherwise be interchangeable.

As far as I understand, a common use case is choosing breadth-first search or depth-first search when exploring a tree, e.g. in a branch-and-bound algorithm for global optimization.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 14, 2020, 12:16am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/18 "2020-02-14T00:16:36Z")

</div>

> [@Tamas\_Papp](#):
>
> I think that to maintain current semantics for ordered collections, this requires that `push!` inserts last, so it cannot choose an arbitrary location.

That’s why I suggested to add `pushany!` and `popany!` in my first comment. I think either `pushany!`/`popany!` _or_ `pushlast!`/`poplast!` are required if we want the “anywhere” API. Those two choices both have pros and cons and I think both of them are reasonable.

---

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [February 14, 2020, 9:18am UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/19 "2020-02-14T09:18:26Z")

</div>

Catching up here… 🙂 Great discussion!

Just another thought - the word “pop” implies taking something off the top, and so it feels like dealing with a stack. Shall we consider “pull”?

---

<div class="post-metadata">

**Author:** ![jonas-schulze](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jonas-schulze/32/9228_2.png) [@jonas-schulze](https://discourse.julialang.org/u/jonas-schulze)\
**Post date:** [November 5, 2021, 6:13pm UTC](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/20 "2021-11-05T18:13:49Z")

</div>

I fully agree with properties 1, 2 and 4. Regarding 3, I think we have a “language problem” here. In many ways (e.g. for `Vector`), `push!` and `pop!` are used to refer to a stack, i.e. a [LIFO](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) data collection. Therefore it makes sense to have `popfirst!` monkeypatch [FIFO](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)) access onto a stack. `pushfirst!` works with a similar effect, but to me starts to feel kind of redundant.

In other ways (e.g. for `AbstractChannel`), `push!` and `pop!` refer to some fuzzy or “natural” way to add and retrieve objects from a collection. I think it’s worth considering to use different names for this, e.g. `put!`/`take!`, and use a language closer to (some) textbooks for FIFO access:

- `push!` and `pop!`: LIFO
- `enqueue!` and `dequeue!`: FIFO
- `put!` and `take!`: priority queue, heap, etc

Then, individual data structures can default to `put!(stack, x) = push!(stack, x)` or `put!(queue, x) = enqueue!(queue, x)` etc. Applications that require a certain access pattern can then use the proper language. Combinations like `push!`+`dequeue!` would (rightfully so) look odd.

This differs from the `pushany!`/`popany!` suggested by @tkf in that instead of “no contract” `put!`/`take!` would fulfil the “natural contract”, if it exists. If there is no “natural contract”, they should not be defined.

`push*!` and `pop*!` (`* = first|last`) would not exist. However, the fuzzy `put!` and `take!` could be extended to `put*!` and `take*!` for ordered collections, thus fulfilling a new version of property 2.  
(Edit: this way, should this be considered, it would be possible to change this even in v1.x by letting `pop*!` and `push*!` keep their “legacy” meaning.)

A big downside of this is that we would have to decide what to do with `Vector`. [As mentioned](https://github.com/JuliaCollections/DataStructures.jl/issues/296#issuecomment-427717239) by @dpsanders, it is effectively a collection supporting both FIFO and LIFO, so I would argue that it should have no (fuzzy) `put!` and `take!`. So far, so good. However, the current `pushfirst!` would then be `enqueue!`, which loses its tight connection to `push!`. The benefit of this is that it forces users to think more carefully about the access pattern and less about the data layout of the data structures they use. Making the operations efficient that a user needs, should be the job of the data structure (Edit: e.g. a `Vector` as an efficient [deque](https://en.wikipedia.org/wiki/Double-ended_queue)).