std::distance complexity in set STL and Policy Based Data Structures(PBDS).
source link: https://codeforces.com/blog/entry/123961
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
set
For random access iterators, std::distance is O(1). Unfortunately set iterator does not support random access, so the std::distance algorithm has to iterate over the pointers to compute distance, and worst case is O(n).
Example: https://codeforces.com/contest/1915/submission/239386119 (Time limit exceeded)
You can achieve O(log(n)) distance complexity in sets if you use Policy Based Data Structures(PBDS).
Example: https://codeforces.com/contest/1915/submission/239436173 (Accepted)
vector
For std::vector the complexity is O(1) since the iterators support random access. You can also use subtraction operator with the same effect.
Example : (int) (lower_bound(vec.begin(),vec.end(),x) — v.begin()) returns distance from begin to first element in array with value >= x, so it's the same as std::distance(vec.begin(), lower_bound(vec.begin(),vec.end(),x));
Some useful links:
PBDS Code:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK