CODEWITHSUNDEEP
c++distancemultimapequal-range
David
David

Reputation: 337

std::distance is slow and how to improve it?

std::distance seems to be very slow. I have a large multimap and try to use equal_range to find the element with common key: 

auto range = in_map.equal_range(neuron_with_spikes[i]); 
int count = std::distance(range.first, range.second);

The std::distance takes more time than equal_range. Naively I would assume when doing equal_range, the distance is automatically calculated. In fact, it's two independent calculations.

Is there a different way to get the total number of element of the equal_range?

Upvotes: -2

Views: 1536

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275966

No; it is possible to implement a std map type construct where counting the distance between iterators is O(lg n), but std maps do not implement it. And retrofitting it is not easy; writing your own container is probably just as easy.

In such a modified map, the balanced binary tree keeps track of total nodes under; this adds a constant overhead factor to tree mutation and memory usage, but none in O notation.

The easiest way, because you only need count and not distance, probably to replace your multimap with a map from key to vector of elements; and manually manage the vector of elements. Distance is O(n) but count becomes O(lg n).

Upvotes: 1

Paul Evans
Paul Evans

Reputation: 27577

std::multimap::equal_range is O(log <size of the container>) and std::distance is O(linear <size of the range>) and std::multimap::count is the sum of those two.

This is total reasonable as the map is sorted and you need to visit each element in the range to count them - so unless you can get rid of some this in your solution - looks like normal behavior for what you're trying to do.

Upvotes: 2

Related Questions