Как подсчитать количество элементов перед данным элементом в std :: set

Question

Я хочу найти нет элементов, присутствующих в наборе перед нижней границей данного элемента, я думал об использовании арифметики указателя с помощью std :: set :: итераторы, так как они ведут себя, как указатель, вот что я пробовал:

set<int>q; 
set<int>::iterator curr; 
set<int>::iterator strt; 
l = num.size(); 
q.insert(num[l-1]); 
strt = q.begin(); 
temp = 1; 
int x; 
for(int i=l-2;i>=0;i--) 
{ 
    curr = q.lower_bound(num[i]); 
    if(curr == q.end()) 
     stats.push_back({temp,0}); 
    else 
    { 
     x = curr-strt;//ERROR 
     stats.push_back({x,temp-x}); 
    } 
    q.insert(num[i]); 
    temp++; 
} 

есть не любой способ найти не из элементов, содержащиеся в наборе до нижней границы с данным элементом?

Answer 1

Вам необходимо выполнить итерацию по набору с начала до точки, которую вы нашли, чтобы подсчитать количество элементов. Там в library function для этого:

x = std::distance(strt, curr); 

Арифметика как curr-strt определяется только для итераторов произвольного доступа, где вычисление может быть сделано в постоянном времени. Такие функции, как distance, будут работать для более общих типов итераторов, но могут быть медленными, если итератор напрямую не поддерживает этот оператор.

Answer 2

Используя data structure augmentation, можно выполнить динамическую статистику заказа в логарифмическом времени.

Я написал один раз libstdc++ extension for this, а затем на безумном python version.