C++ set - 密钥小于x的元素数

Question

我有一个set<int>,我想看看它中有多少元素小于x.(x也是int)

我该怎么办？

Answer 1

使用lower_bound来计算std::distance(s.begin(), s.lower_bound(x)).(如果x是一个关键,这个严格的计算元素的数量之前 x.)

是的，这是 O(n)，这一点都不好 (6认同)
与此解决方案的复杂性相关的相关链接:http://stackoverflow.com/questions/15321013/c-set-counting-elements-less-than-a-value (5认同)
@LeoLeontev：嗯，迭代器增量是 O(n)，而不是谓词的应用。如果这种计数是您的热路径，那么您可能更喜欢“平面集”实现，其中迭代器是随机访问的，并且您可以计算恒定时间的差异。 (2认同)