c++ - set get position of an element -

i want solve following problem: given vector of n elements, find number of swaps insertion sort algorithm needs sort.

ex:
n = 5
2 1 3 1 2
answer: 4

explanation(step step insertion sort algorithm):
initialy: 2 1 3 1 2
1 2 3 1 2 ; 1 swap 1( 1 goes left)
1 2 3 1 2 ; 0 swaps
1 1 2 3 2 ; 2 swaps ( 1 goes 2 pos left )
1 1 2 2 3 ; 1 swap ( 2 goes 1 pos left)

my solution

i keep position of every item in initial array can remove set later based on value , position.(1st loop)
count number of elements smaller current number add them counter , remove element set. ( 2nd loop )

as can see, problem std::distance has linear complexity cause set has bidirectional iterators. how can o(1) complexity without having implement own tree?

int count_operations(vector<int> &v) {     set<pair<int, int>> s;     // o(n * logn)     for(int = 0; < (int) v.size(); ++i)     {         s.insert(make_pair(v[i], i));     }     int cnt = 0;     // desired: o(n * log n) ; current o(n^2)     for(int = 0; < (int) v.size(); ++i)     {         auto item = make_pair(v[i], i);         auto = s.find(item);         int dist = distance(s.begin(), it);//o(n); want o(1)         s.erase(it);         cnt += dist;     }     return cnt; } 

the problem getting rank of each element in set, can done order statistic tree (using pbds library in gnu libc++) follows.

#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <vector> #include <utility> using namespace std; using namespace __gnu_pbds;  typedef tree<     pair<int, int>, /* key type */     null_mapped_type, /* value type */     less< pair<int, int> >, /* comparison */     rb_tree_tag, /* having rb tree */     tree_order_statistics_node_update> order_set;  int count_ops(std::vector<int> &v) {     order_set s;     int cnt = 0;     /* o(n*log(n)) */     for(int = 0; < v.size(); i++)         s.insert(pair<int, int>(v[i], i));     for(int = 0; < v.size(); i++)     {         /* finding rank o(log(n)), overall complexity o(n*log(n)) */         cnt += s.order_of_key(pair<int, int>(v[i], i));         s.erase(pair<int, int>(v[i], i));     }     return cnt; }