3 ms·
"- Python's dict is a fast unordered hashmap. However, if you need order-aware operations like C++'s std::map::lower_bound(), you're out of luck; Python's stand
by ZeroCool2u 3y ago
"- Python's dict is a fast unordered hashmap. However, if you need order-aware operations like C++'s std::map::lower_bound(), you're out of luck; Python's standard library doesn't have a tree implementation."
I'm fairly certain that in Python 3.7 and later standard library dictionaries are now ordered by default.
- alfons_foobar 3y agoOrdered by insertion (see [Mailinglist](https://mail.python.org/pipermail/python-dev/2017-December/151283.html https://mail.python.org/pipermail/python-dev/2017-December/1...)) This might or might not be what you want/expect...
- johndough 3y agoYou are correct. Dicts are ordered by insertion. Also, I'd like to add that, maybe surprisingly, sets are not. >>> set([3, 2, 1]) {1, 2, 3} >>> set([10, 100, 1000]) {1000, 10, 100}
- azundo 3y agoI believe lower_bound is ordering by key comparison - python dicts are insertion ordered.
- DangitBobby 3y agoA little nitpick: they were always ordered by insertion, 3.7 just codified that behavior as a guarantee instead of an implementation detail.
- az09mugen 3y agoYou're right, it's even python 3.6, and you have also the OrderedDict https://realpython.com/python-ordereddict/ https://realpython.com/python-ordereddict/
- timmaxw 3y agoYes, Python dicts remember insertion order. This is different from C++ std::map, which maintains the keys in sorted order. For example, std::map::lower_bound(X) finds "the smallest key in the map which is greater than or equal to X" in O(log(N)) time. I don't think Python has any data structure in the standard library that supports this operation while also supporting insertion in O(log(N)) time.