如何统计std :: set中给定元素之前的元素数

Question

我想在给定元素的下界之前找到set中没有元素，我想用指针运算和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。