Jexy's blog

Can i calculate std::distance() for iterators in std::set with O(1) complexity?
By Jexy, history, 21 month(s) ago, translation, In English

?

Tags c++, set
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

No, you can't. However, if you use ordered set, you can do this in $$$O(log(N))$$$

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

No, it is not possible to calculate std::distance() for iterators in std::set with O(N) complexity. The reason for this is that std::set is implemented as a balanced binary search tree, which means that the elements are stored in a non-contiguous order. As a result, the distance between two iterators in a std::set can only be calculated by traversing the tree from one iterator to the other, which takes O(log n) time complexity, where n is the number of elements in the set. Therefore, std::distance() for iterators in std::set has a worst-case time complexity of O(log n).

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Therefore, std::distance() for iterators in std::set has a worst-case time complexity of O(log n)

    no lol iterator traversal on std::set is $$$O(\text{distance})$$$, so basically this is $$$O(N)$$$

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can use __gnu_pbds::tree and set node update to tree_order_statistics_node_update.

After that just call order_of_key to find distance between two elements in $$$O(\log N)$$$ time.

For std::set<Key,Compare,Allocator>::iterator, it is mentioned in https://en.cppreference.com/w/cpp/iterator/distance that its time complexity is linear. Not sure if we could do better as std::set<> is too packaged.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

it is impossible to get distance or indicies in a set in less than O(N) time, however using the ordered set data structure can do this in O(log N) time.

ordered set implementation

https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

→ Reply