std :: set :: equal_range std :: pair的容器

Question

我試圖找到所有的範圍[a，b]，其中包含int值i，其中< = i < = b。我正在使用set<std:pair<int,int>>作爲一組範圍。

下面，在vector<int>上使用相同的範圍會得到該範圍的開始值和結束值。

當我對set<pair<int,int>>執行相同操作時，結果會在範圍末尾的一個結尾處開始和結束，因此不包括包含該值的範圍。

#include <set> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

int main() 
{ 
    int ia[] = {1,2,3,4,5,6,7,8,9,10}; 
    set<int> s1(begin(ia),end(ia)); 
    auto range1 = s1.equal_range(5); 

    cout << *range1.first << " " << *range1.second << endl; //prints 5 6 

    pair<int,int> p[] = {make_pair(1,10), 
         make_pair(11,20), 
         make_pair(21,30), 
         make_pair(31,40)}; 
    set<pair<int,int>> s(begin(p), end(p));  

    auto range = s.equal_range(make_pair(12,12)); 

    cout << range.first->first << " " << range.first->second << endl; //prints 21 30, why? 
    cout << range.second->first << " " << range.second->second << endl; //prints 21 30 

} 

prints
5 6
21 30
21 30
爲什麼在set<pair<int,int>> equal_range不包括包圍所述值（12），即[11.20]

Answer 1

equal_range完全正確地表現：

assert(std::make_pair(11, 20) < std::make_pair(12, 12)); 
assert(std::make_pair(12, 12) < std::make_pair(21, 30)); 

[11,20]不是一個範圍，它是一對。對[12,12]不在另一對「內」，即使這樣說也沒有意義。

[12,12]不是「在」之內[11,20]，它比它大。小於號運算符std::pair的第一要素首先比較，且僅當它們相等它再看第二個元素，所以make_pair(11,x)小於make_pair(12, y)任何x和y

所以equal_range告訴你， [11,12]之後和[21,30]之前插入[12,12]，這是正確的。

如果您想將對視爲值的範圍，您需要編寫代碼來執行此操作，而不是假定對的內置比較可以執行此操作。你實際上試圖在一對int中找到一個int 12，但是已經編寫了代碼來在一對int中找到一對[12,12]。這不是一回事。

Answer 2

它不包括在[11, 20]的範圍內，範圍，因爲它不包括任何東西在範圍內。與[12, 12]沒有相同的元素，所以它返回一個空的範圍（以半開區間[x, x)表示）。

BTW取消引用範圍的上限可能會調用未定義的行爲，因爲它可能等於s.end()。

Answer 3

雙[12, 12]排序方式爲[11, 20]之前和[21, 30]之前。

std::set::equal_range()包括範圍等於元素。您的套件中沒有相同的元素（尤其不是[11, 20]），因此equal_range()返回[21, 30], [21, 30]。

Answer 4

equal_range被實現爲先調用lower_bound然後調用upper_bound來搜索其餘數據集。

template <class ForwardIterator, class T> 
    pair<ForwardIterator,ForwardIterator> 
    equal_range (ForwardIterator first, ForwardIterator last, const T& value) 
{ 
    ForwardIterator it = lower_bound (first,last,value); 
    return make_pair (it, upper_bound(it,last,value)); 
} 

看你的樣品： 它調用lower_bound找到下界的值（這是對（12,12），其在

pair<int,int> p[] = {make_pair(1,10), 
        make_pair(11,20), 
        make_pair(21,30), // <--- lower_bound() points to here 
        make_pair(31,40)}; 

到達然後調用UPPER_BOUND（）來搜索在（21,30），（31,40），它cound't找到它，它返回（21,30）

http://www.cplusplus.com/reference/algorithm/upper_bound/

Answer 5

我不認爲你std::set<std::pair<int, int> >不會幫助您將其與整數相交：您可以找到s.lower_bound(std::make_pair(i + 1, i + 1)以關閉搜索，但如果第二個邊界足夠大，則所有從低於i + 1的索引開始的範圍可能包含值i。如果您知道範圍的最大大小，您可以通過s.lower_bound(std::make_pair(i - max_range_size, i - max_range_size))將搜索範圍限制在前面，這可能會有所幫助。你需要檢查每個又將範圍來鑑定您的i屬於他們：

auto it = s.lower_bound(std::make_pair(i - max_range_size, i - max_range_size)); 
auto upper = s.lower_bound(std::make_pair(i + 1, i + 1)); 
for (; it != upper; ++it) { 
    if (i < it->second) { 
     std::cout << "range includes " << i << ": " 
        << [" << it.first << ", " << it->second << "]\n"; 
} 

（或這樣的事情...）