M
M
Mercury132019-04-05 23:38:57
C++ / C#
Mercury13, 2019-04-05 23:38:57

Finding the intersection of std::maps faster than O(|A| + |B|)?

There are two std::maps with the same "less than" operation. Go through all the elements that are in both.
Any relationship between maps is possible - the first is much larger than the second, and the second is much larger than the first, and one is guaranteed to be nested in the second.
The physical assembly of the intersection is not necessary, it is enough to pass through the lambda function.
Is it possible to obtain complexity, for example, O(|A ∩ B| log max{|A|, |B|}) using C++ standard library functions?

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question