c++ - 如何计算std :: set中给定元素之前的元素数量

Question

我想在给定元素的下限之前找到集合中不存在的元素，我想使用指针算术和 std::set::iterators 因为它们的行为像指针，这是我尝试的：

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

您必须从开始到您发现的点遍历集合以计算元素的数量。有一个库函数：

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

类似算术运算curr-strt仅针对随机访问迭代器定义，其中计算可以在恒定时间内完成。类似的函数distance适用于更通用的迭代器类型，但如果迭代器不直接支持该运算符，则可能会很慢。

Answer 2

使用数据结构增强，可以在对数时间内进行动态顺序统计。

我曾经为此编写了一个 libstdc++ 扩展，后来又疯狂地编写了一个python 版本。