### Jame___boy's blog

By Jame___boy, 5 months ago,

### 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));

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

### PBDS Code:

• -8

 » 5 months ago, # | ← Rev. 2 →   +1 Thanks for share this useful resources. I solved last contests F using brute force that's why it take 4.5s :( I will try this PBDS next time
 » 5 months ago, # |   +11 I think it is O(logn) in the second case... Correct me if I am wrong...
•  » » 4 months ago, # ^ |   0 Thanks, For Your Attention. I have updated it.
 » 4 months ago, # |   0 This is what exactly happened to me in 918 Div. 4 as you showed here. I could not fix at the time but I guess it is very helpful for beginners to know this concept.