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://mirror.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://mirror.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:
- https://youtu.be/MiBrJTNOEP0?si=12Op-IbK7lfqdIbp (বাংলা ভিডিও টিউটোরিয়াল)
- https://mirror.codeforces.com/blog/entry/45902 (Time complexity of std::distance)
- https://stackoverflow.com/questions/13505562/getting-index-of-set-element-via-iterator/13505578
- https://mirror.codeforces.com/blog/entry/5631?#comment-239276 (How to access to i*th element of a set in c++ effectively (*O(1) or (logN))?)
- https://mirror.codeforces.com/blog/entry/11080 (C++ STL: Policy based data structures)
- https://mirror.codeforces.com/blog/entry/11080?#comment-533322 (drawback of using less_equal)
