計算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 ::矢量STD代替的::套作品perfectly。

看起來像operator-不適用於std::set::iterator。爲什麼？ 然後，你怎麼可以很容易地（沒有打電話std::previous或std::next直到達到...這不會有效）找到一個給定的迭代器在容器中的位置？如果你不能，那麼我可以用什麼修飾來找到給定元素的索引......？

Answer 1

看起來像operator-對於std :: set :: iterator無效。爲什麼？

確實，std::set::iterator::operator-()的實現不能以恆定的複雜度存在，因爲元素在內存中不是連續的。

---

那麼，你怎麼能輕鬆地（沒有調用的std ::以前或std ::下一直到達到束縛......這不會是有效的），找到一個給定的迭代器的位置在容器？

您不能，std::set::iterator不是RandomAccessIterator。見std::distance()文檔：

複雜

線性。

---

如果你不能，那麼我可以用什麼alterantive找到一個給定的元素的索引...？

我建議，而無需計算的迭代器距離，算你的元素：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

Answer 2

您可以使用下面的代碼如下：

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

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); 
    std::size_t dist = std::distance(found, mySet.end()); 
    std::cout << "Number of lower bound elements: " << dist << std::endl; 
} 

Answer 3

由於std::set::iterator是BidirectionalIterator除非我們使用遞減運算符，否則我們不能從它中減去。我們可以做的事情就是走集合並計算迭代次數，直到達到比我們想要的更大的數字。

std::set<int> mySet; 
// fill values 
int counter = 0; 
for (auto it = mySet.begin(), *it < some_value && it != mySet.end(); ++it) 
{ 
    if (e < some_value) 
     counter++; 
} 

這是一個最壞mySet.size()迭代是一樣快，您可以用BidirectionalIterator打交道時得到它。

另請注意，由於我們沒有使用RandomAccessIterator，因此std::lower_bound沒有O（log N）複雜性。當使用非RandomAccessIterator時，它具有線性複雜性。

Answer 4

擴展所有現有的答案 - 你可以隨時編寫自己的operator-。

template<class T, class = typename 
    std::enable_if< 
    std::is_same< 
    typename T::iterator_category, 
    std::bidirectional_iterator_tag 
>::value>::type> 
typename std::iterator_traits<T>::difference_type operator-(const T& a, const T& b) 
{ 
    return std::distance(b, a); 
}