Author serhiy.storchaka
Recipients arigo, aronacher, eric.snow, inada.naoki, rhettinger, serhiy.storchaka
Date 2017-09-11.05:27:11
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1505107631.48.0.565245014142.issue31265@psf.upfronthosting.co.za>
In-reply-to
Content
Note that mixed insertion and deletion is worst-case O(n) in current implementation.

Original Raymond's design didn't preserve ordering during deletion. It had worst-case O(1) for mixed insertion and deletion. I didn't follow the numerous discussions about compact dict implementation, but at some point it became keeping holes and preserving ordering during deletion. This leads to the need of periodical O(n) reallocation for mixed insertion and deletion. Perhaps the technical reason of this was the couple relation between C implementation of OrderedDict and dict.
History
Date User Action Args
2017-09-11 05:27:11serhiy.storchakasetrecipients: + serhiy.storchaka, arigo, rhettinger, aronacher, inada.naoki, eric.snow
2017-09-11 05:27:11serhiy.storchakasetmessageid: <1505107631.48.0.565245014142.issue31265@psf.upfronthosting.co.za>
2017-09-11 05:27:11serhiy.storchakalinkissue31265 messages
2017-09-11 05:27:11serhiy.storchakacreate