lower bound for set in cpp

Question

To find index of a element in a vector we usually find it=lower_bound(vector.begin(),vector.end(),element)

and subtract it like this int index = it-vector.begin()

But same concept is not applicable for set why and how can I do that? Because int pos = it-a.begin() is giving me error in below program.

I want to find position of element in the set in that element.

#include<bits/stdc++.h>
using namespace std;
set<int>a;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        int u;
        cin>>u;
        a.insert(u);
    }
    int ans=0;
    while(n--){

        for(int i=0;i<m;i++){
            int u;
            cin>>u;
            set<int>::iterator it = a.lower_bound(u);
            int pos = it-a.begin();
            a.erase(it);
            a.insert(a.begin(),u);
            ans+=pos;
        }
    }
    cout<<ans;
}

[Why one shouldn't include `bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). — Aconcagua, Sep 03 '19 at 04:02
About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... — Aconcagua, Sep 03 '19 at 04:03
Get used to check stream-state after input operations. When scanning n, m, k, what do you think will happen if user incorrectly writes *51 s 7*? — Aconcagua, Sep 03 '19 at 04:06
A `set` can't be either randomly accessed or reordered – `a.insert(a.begin(),u)` has the same effect as `a.insert(u)`. Either use a different structure throughout and maintain sorted uniqueness yourself, or create a `std::deque` from the set and work with that. — molbdnilo, Sep 03 '19 at 05:41

score 4 · Answer 1 · edited Sep 03 '19 at 04:28

You cannot use generic algorithm std::lower_bound() with std::set iterators exactly for the same reason you cannot calculate distance by it2 - it1 - that requires random access iterator and std::set does not provide them. You can use std::set::lower_bound() though instead and std::distance( it1, it2 ) to calculate difference but you need to be aware that would be more expensive for non random access iterators. So your code can be fixed by this:

        int pos = std::distance( a.begin(), it );

be aware that result of std::distance() may not fit into int (same problem for calculating distance by it2 - it1 though) .

Note: you may prefer to use std::distance() instead of subtracting one iterator from another for code generosity as it would be efficient on random access one and still work on forward iterator, though more expensive.

Note2: finding a position in std::set usually points to wrong design. You either use wrong data structure or wrong approach.

Not only `std::distance` – using such an index (on the set!), once determined, would be just as expensive as well... Not sure if either of could be realised better than linear, especially as no fully balanced tree is mandated. — Aconcagua, Sep 03 '19 at 04:09

score 0 · Answer 2 · answered Sep 03 '19 at 04:40

If you need to do this in O(log n) you need a order statistic tree. This is a binary search tree that keeps additional information in its nodes such as the subtree size which will allow you to compute the information you need quickly. You can implement such a data structure yourself. or use the GCC policy-based data structure extension if you don't mind writing non-portable code.

lower bound for set in cpp

2 Answers2