This bisect to 68498c6, or #19153, though haven't looked into why.

So the issue here is that #19153 replaced _AxesStack with its base class cbook.Stack. The former saves the order of when the Axes were added, while the latter does not. The problem is that adding an Axes makes it 'current', so Figure.colorbar sets the original Axes current again, but this is determined by the top of the stack. Since the original order is no longer saved, this messes up the output list from Figure.axes.

To fix this (which I assume we do, since changing order changes draw order, which could do strange things), we either need to restore _AxesStack, or store current Axes separately.

The stack can bubble entries to the top, which is what Figure.sca does to track the current Axes.

Sorry I erased my dumb comment.

Was it necessary to remove _axesstack? Or just a nice simplification?

Would have to ask @lpsinger to confirm, but I suspect it was removed because a) it was the private side of a deprecated-in-3.2 class, and b) it seemed to mostly be about tracking Axes keys at the time.

We just didn't realize that tracking order was an important thing there, as it seems there were no tests that caught that.

Yes, @QuLogic, that's correct.

I'm not quite following your explanation of the bug, probably because I need more coffee! Is the issue that plt.colorbar() is bubbling itself and making itself the current axes?

From a very quick guess, it may be possible to fix this by having a single module-wide private incrementing counter, assign indices to a private attribute (ax._index) on axes when they are being added to a figure, and then sort by _index in Figure.get_axes?

I am confused. Why do we need to store the index in addition to the axes stack?

Oh, I understand now. Originally, the indices were stored in the stack. According to the old docstring:

    """
    Specialization of `.Stack`, to handle all tracking of `~.axes.Axes` in a
    `.Figure`.

    This stack stores ``key, (ind, axes)`` pairs, where:

    * **key** is a hash of the args and kwargs used in generating the Axes.
    * **ind** is a serial index tracking the order in which axes were added.

    AxesStack is a callable; calling it returns the current axes.
    The `current_key_axes` method returns the current key and associated axes.
    """

Why do we need to store the axes in a stack, at all? Why not just store them in a list, and keep track of the current axes as a member variable? The stack keeps track of the history of what the current axes was, but is that history ever actually needed? If we switched to storing the axes as a list, then that would automatically preserve the order in which they were added.

I think that currently the sole usefulness of the stack is when using the pyplot interface, so that when you remove() the current (per gca()) axes, gca() then refers to the previously set current axes.
I would say this is a rather rare case, and we could consider documenting that if the current axes is remove()d, then gca() will instead point to the last added axes (i.e. fig.axes[-1]). Still, it may need a deprecation period... (which can be done by restoring the stack and, in delaxes(), check whether the new current axes would be different in either case.)

Got it... should I resurrect the original implementation of storing the indices and axes in the stack? Maybe a simpler implementation would be store a stack and a list on the Figure.

I don't have a strong preference here (... for now :)).

Yes, the colorbar has nothing to do with it, other than that it calls sca. It's all due to the 'current' Axes tracking:

>>> import matplotlib.pyplot as plt
>>> import numpy as np

>>> fig, ax = plt.subplots(2, 2)
>>> for (i, j), a in np.ndenumerate(ax):
...     a.set_label(f'{i},{j}')
... 
>>> fig.axes
[<AxesSubplot:label='0,0'>, <AxesSubplot:label='0,1'>, <AxesSubplot:label='1,0'>, <AxesSubplot:label='1,1'>]

>>> fig.sca(ax[0, 0])
<AxesSubplot:label='0,0'>

>>> fig.axes
[<AxesSubplot:label='0,1'>, <AxesSubplot:label='1,0'>, <AxesSubplot:label='1,1'>, <AxesSubplot:label='0,0'>]

As this was not intended change, or communicated in any way before hand, I think we should do whatever is minimally possible to restore previous behaviour.