Is there a structure in Python similar to C++ STL map?

Question

dict is usually close enough - what do you want that it doesn't do?

If the answer is "provide order", then what's actually wrong with for k in sorted(d.keys())? Uses too much memory, maybe? If you're doing lots of ordered traversals interspersed with inserts then OK, point taken, you really do want a tree.

dict is actually a hash table rather than a b-tree. But then map isn't defined to be a b-tree, so it doesn't let you do things like detaching sub-trees as a new map, it just has the same performance complexities. All that's really left to worry about is what happens to dict when there are large numbers of hash collisions, but it must be pretty rare to use Python in situations where you want tight worst-case performance guarantees.

Python SortedDict is a similar to C++ STL map. You can read about it here or here.

SortedDict is a container of key-value pairs in which an order is imposed on the keys according to their ordered relation to each other. As with Python’s built-in dict data type, SortedDict supports fast insertion, deletion, and lookup by key.

I believe that the standard python type dict() will do the trick in most cases. The difference from C++'s std::map is that dict is impemented as a hash map and C++'s map is tree-based.

Python dictionaries [5.5].

Have you looked into Python dictionaries?

Look at bintrees module (pip install bintrees). This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython/C.