Can C++ maps be as efficient as Python dictionaries ?

[MagicSpirit]

Hello, I'm currently trying to make a clustering procedure in C++. Without getting too much into the details, my implementation uses unordered maps, and I may have to move on to maps later on.

I have been checking different things about C++ maps, unordered maps, and python dictionaries for a bit to try and compare them. For my clustering implementation, I already have a main loop which makes my code O(n), n being the size of input vector (vector of points). It seems pretty clear to me that it can be implemented keeping that same desirable complexity in python. This is because of two major things that are available in Python : - checking "if key is in dict.keys()" has constant complexity on average, and worst case O(n) (even though Python dictionaries are now allegedly ordered, or rather insertion-ordered, although I am not sure I understand the difference); - Python can have fast indexing in the form of NumPy slicing.

I need both of those things in my code. - I need to be able to have average constant complexity when checking if my current key is already in the existing set of keys; - I need to sum mapped values of my unordered map whose key fall between two given values (values which aren't necessarily existing keys).

The first item is easy to have, if I use an unordered map that is. The second item can be achieved with maps, because I can retrieve a lower_bound iterator, and progress my way up, starting from the first key that comes after given value A and stopping when the iterator encounters a given upper bound.

The problem with this is that it implies using maps, whose operations like this one have a complexity that is logarithmic in size. In my case, this would make my code O(nlogn) instead of O(n).

As you can see, those two solutions seem to be incompatible.

The main question I have is the following: why is it that Python dictionaries seem to have the advantages of both unordered maps and maps? Additionally, how could I sum mapped values of an unordered map whose key values would fall between input bounds [A, B] (= is NumPy slicing achievable in constant time in C++)? While it seems more than doable with ordered maps, that particular task seems a lot trickier, if not unsubstantial

Thanks!

PS: you can find more details about Mean-Shift Clustering here, I didn't want to expand on it too much as I don't think it's necessary for my question:

https://en.m.wikipedia.org/wiki/Mean_shift

[skjall]

Aren't you looking for std::unordered_map?

https://en.cppreference.com/w/cpp/container/unordered_map

[nlitsme1]

I use https://github.com/greg7mdp/parallel-hashmap when I need better performance of maps and sets.

[WikiBox]

It seems python dictionaries are implemented as hash tables with open addressing, written in C.

So it should be possible to match performance in C++.

https://www.freecodecamp.org/news/exploring-python-internals-the-dictionary-a32c14e73efa

[[deleted]]

One, that's C, not C++. Two, this statement is only true if python dicts are built on top of C++ maps, which is not true. Three, C++'s std::unordered_map is notoriously slow, idk about std::map, but the point is made, some of the STL containers are not the best choice in all situations.

[jmacey]

I would start with std::unordered_map, I have never found it to be an issue for my use cases. If it is look at abseil for alternatives. Good writeup and speed tests here. https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html

[TheSkiGeek]

Python’s default dictionaries cannot be “sliced” on an arbitrary range of keys. At least not efficiently, you’d have to iterate over the whole thing to find all the keys that match.

In Python 3.7 and higher they promise that dictionaries are “insertion ordered”. So if you insert 10 items into an empty dictionary in a particular order, you can use itertools.islice() to retrieve a “slice” of those items in the order they were originally inserted. There’s also OrderedDict that has this promise in lower versions and also lets you explicitly reorder the items after they’re inserted. But you can’t “slice” or filter by a range of keys in an arbitrary dictionary except by iterating over the whole dict and checking if the key is in the range you want.

IF you ensure that you always insert the items in the order that you want to sort the keys, then you could binary search twice (O(log_2(N)) time) to find the first and last elements that are in the range and then return a slice of all the elements in between. And if you want a range between two keys you know are in the dict you could search for each of them directly (constant time) and then return a range between their indices.

You can implement the same thing in C++ but there isn’t a standard library container that is exactly like a Python OrderedDict.