First one (2027 ms): 253857814
The second one (249 ms): 253859120
In my observation, both of them have a time complexity of O(n2logn2)
- First one: I created a vector of pairs that have a size of nearly n2 and inserted all of them in a map which will take O(n2logn2) time complexity.
- Second one: I created a vector of pairs with a similar size of nearly n2. And I then sorted it which will take O(n2logn2) time complexity.
Map has a large constant factor, use vectors whenever you can. If you can't use vectors use unordered map with custom hash
Okay. Thanks. Can you provide any resources for unordered map with custom hash?
link
C++ std::sort() is giga optimized
For maps, they will create a lot of small memory blocks, and the internal tree structure requires additional resources.
For vectors, it's just an array, it will only expand a few (logarithmic) times. The memory blocks are consecutive. And sortings itself adds much less additonal resource to compute.
I don't really use unordered maps (hash maps). I suppose that you can pass with a normal map in most times if the problem requires one. Though sometimes there are significant time improvement with hash maps.