Hacker News Reader

Comment by ZeroCool2u | Hacker News Reader

"- 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.

View on HN

Ordered by insertion (see [Mailinglist](https://mail.python.org/pipermail/python-dev/2017-December/1...))

This might or might not be what you want/expect...

You 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}

Yes, 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.

You're right, it's even python 3.6, and you have also the OrderedDict https://realpython.com/python-ordereddict/

A little nitpick: they were always ordered by insertion, 3.7 just codified that behavior as a guarantee instead of an implementation detail.

I believe lower_bound is ordering by key comparison - python dicts are insertion ordered.

Reply on news.ycombinator.com