5

I made a small program and tested that it does keep the order. However, I still want to be sure that deepcopy is guaranteed to do that.

import copy
import collections

a_dict = collections.OrderedDict()
a_dict['m'] = 10
a_dict['u'] = 15
a_dict['c'] = 5
a_dict['h'] = 25
a_dict['a'] = 55
a_dict['s'] = 30

print(a_dict)

other_dict = copy.deepcopy(a_dict)

other_dict['g'] = 75
other_dict['r'] = 35

print(other_dict)

The output of this program is 

OrderedDict([('m', 10), ('u', 15), ('c', 5), ('h', 25), ('a', 55), ('s', 30)])
OrderedDict([('m', 10), ('u', 15), ('c', 5), ('h', 25), ('a', 55), ('s', 30), ('g', 75), ('r', 35)])
Prune
  • 76,765
  • 14
  • 60
  • 81
Sharad
  • 445
  • 6
  • 20
  • 1
    You would have to look in the c code to see if deepcopy is able to copy the linked list that defines the ordereddicts order. My guess is it’s doable. – Paul Rooney Jul 24 '18 at 00:20

4 Answers4

4

Correctly implemented copying via copy.deepcopy should produce an object that is equal to the original (assuming equality is defined at all). While no, there is no explicit documented guarantees regarding OrderedDict and copy.deepcopy specifically, if the ordering of OrderedDict changed in the copy, it would not be equal to the original OrderedDict, which would violate the expectation of copy-equality in a big way.

No firm guarantee can truly be given, since the __deepcopy__ method of a key or a value could do something truly terrible (modifying the source OrderedDict for instance), but aside from pathological cases, you can rely on copy.deepcopy to preserve ordering.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • 2
    It looks like there is no special casing for `OrderedDict` in the `copy` module, which means it ends up pickling and unpickling to perform the deep copy; [the implementation of `__reduce__`](https://github.com/python/cpython/blob/3.6/Objects/odictobject.c#L956) returns the `items` iterator as the fifth item of its return `tuple`, which, per the `__reduce__` docs, [means it will be iterated in that order with the first element used as the key, and the second as the value](https://docs.python.org/3/library/pickle.html#object.__reduce__), so the implementation intentionally preserves order. – ShadowRanger Jul 24 '18 at 00:51
  • 2
    I can't believe you put the coolest part of your answer in a comment :) – Greg Schmit Jul 24 '18 at 01:10
  • 1
    @GregSchmit: It's Python, so implementation details aren't official; the spec is the documentation, not the CPython reference interpreter; implementation details are subject to change from version to version and interpreter to interpreter. Nothing specifically requires the specific implementation chosen (though it is a straightforward one); in theory, some other Python interpreter might choose a different one. – ShadowRanger Jul 24 '18 at 02:08
1

In CPython, it appears the order is preserved. I drew that conclusion from inspecting the implementation of deepcopy. In this case, it will find either the __reduce_ex__ or __reduce__ method on your OrderedDict object to use for pickling:

(https://github.com/python/cpython/blob/master/Lib/copy.py#L159-L161)

def deepcopy(x, memo=None, _nil=[]):
...
                    reductor = getattr(x, "__reduce_ex__", None)
                    if reductor is not None:
                        rv = reductor(4)
                    else:
                        reductor = getattr(x, "__reduce__", None)
                        if reductor:
                            rv = reductor()

Those return odict_iterator objects for constructing, so order would be preserved:

>>> a = {}
>>> b = collections.OrderedDict()
>>> a['a'] = 1
>>> b['a'] = 1
>>> a.__reduce_ex__(4)
(<function __newobj__ at 0x10471a158>, (<class 'dict'>,), None, None, <dict_itemiterator object at 0x104b5d958>)
>>> a.__reduce__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/opt/local/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/copyreg.py", line 65, in _reduce_ex
    raise TypeError("can't pickle %s objects" % base.__name__)
TypeError: can't pickle dict objects
>>> b.__reduce_ex__(4)
(<class 'collections.OrderedDict'>, (), None, None, <odict_iterator object at 0x104c02d58>)
>>> b.__reduce__()
(<class 'collections.OrderedDict'>, (), None, None, <odict_iterator object at 0x104c5c780>)
>>>
Greg Schmit
  • 4,275
  • 2
  • 21
  • 36
0

deepcopy of an object should return an object of the same type. so an ordereddict returned as a copy should remain ordered?

EDIT - This is not completely correct answer. Please look at Greg's comment below.

mod0
  • 155
  • 2
  • 13
  • 1
    I don't think the OP doubted that they'd get back another `OrderedDict`, they were just concerned that the new version might have *different* ordering. – ShadowRanger Jul 24 '18 at 00:56
  • 1
    Ok. If the returned object is an OrderedDict, should it not be ordered? If the returned object is an OrderedDict and it is not ordered, then it's violating the definition of the datastructure. This was the point that I was trying to make. – mod0 Jul 24 '18 at 16:51
  • 1
    @mod0, then I don't think you understand OrderedDicts work. They keep the order that objects were added, so if you have two of them in different order, you don't necessarily know which one is "right". The question is asking if the same order is preserved, which isn't a given as you imply, since during the copying, the interpreter could copy in a different order and therefore return a different OrderedDict. – Greg Schmit Aug 27 '18 at 03:53
  • @GregSchmit you are correct. I apologize for having made the assumption that the keys are sorted. I will edit my answer to reflect that. – mod0 Sep 13 '18 at 13:01
  • @mod0 It happens; no worries! – Greg Schmit Sep 13 '18 at 15:33
0

Since some folks may get here to look for answer relating to dict (the standard dict, not OrderedDict), I thought this would be useful: In Python 3.6 or later, the order is preserved for dict and therefore deepcopy of a dict will get ordering for free. (If you are concerned about implementation vs spec, then use python 3.7 as it is now in 3.7 language spec)

Please see a related question: Can I get JSON to load into an OrderedDict? Please also see this comment relating to the use of OrderedDict to preserve the oder: https://gandenberger.org/2018/03/10/ordered-dicts-vs-ordereddict/

HAltos
  • 701
  • 7
  • 6