计数元素低于std :: set中的给定值

Question

我需要找到多少元素低于给定的元素std::set.

我认为使用正确的函数是std::lower_bound将迭代器返回到第一个元素,该元素大于或等于给定的一个....所以这个迭代器的索引是我正在寻找的...但我不能从迭代器中找到索引:

#include <iostream>
#include <algorithm>
#include <set>

int main()
{
    std::set<int> mySet;
    mySet.insert( 1 );
    mySet.insert( 2 );
    mySet.insert( 3 );
    mySet.insert( 4 );

    std::set<int>::const_iterator found = std::lower_bound( mySet.begin(), mySet.end(), 2 );

    if ( found != mySet.end() )
        std::cout << "Value 2 was found at position " << ( found - mySet.begin() ) << std::endl;
else
        std::cout << "Value 2 was not found" << std::endl;
}

这不编译:

16:63: error: no match for 'operator-' (operand types are 'std::set<int>::const_iterator {aka std::_Rb_tree_const_iterator<int>}' and 'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}')
16:63: note: candidates are:
In file included from /usr/include/c++/4.9/vector:65:0,
                 from /usr/include/c++/4.9/bits/random.h:34,
                 from /usr/include/c++/4.9/random:49,
                 from /usr/include/c++/4.9/bits/stl_algo.h:66,
                 from /usr/include/c++/4.9/algorithm:62,
                 from 3:

使用std :: vector代替std :: set 非常有效.

看起来像运营商 - 对a无效std::set::iterator.为什么？然后,你怎么能轻松(没有调用std::previous或直接std::next绑定到达...这不会有效)在容器中找到给定迭代器的位置？如果你不能,那么我可以用什么替代方法来找到给定元素的索引......？

Answer 1

看起来运算符- 对于 std::set::iterator 无效。为什么？

std::set::iterator::operator-()事实上，由于元素在内存中不连续，因此的实现不可能以恒定的复杂性存在。

那么，如何轻松地（在达到界限之前不调用 std::previous 或 std::next ......这不会有效）找到给定迭代器在容器中的位置？

你不能，std::set::iterator不是RandomAccessIterator。请参阅std::distance()文档：

复杂

线性。

如果不能，那么我可以使用什么替代方法来查找给定元素的索引......？

我建议计算你的元素而不必计算迭代器距离：std::count_if()可以帮助我们：

#include <iostream>
#include <algorithm>
#include <set>

int main()
{
    std::set<int> mySet;
    mySet.insert( 1 );
    mySet.insert( 2 );
    mySet.insert( 3 );
    mySet.insert( 4 );

    const std::size_t lower_than_three = std::count_if(
         std::begin(mySet)
        , std::end(mySet)
        , [](int elem){ return elem < 3; } );
    std::cout << lower_than_three << std::endl;    
}

Demo