1

我试图找到包含 int 值 i 的所有范围 [a,b]，其中 a <= i <= b。我正在使用set<std:pair<int,int>>一组范围。

在下文中，在 a 上使用相等的范围vector<int>会产生范围的开始和结束之后的范围。

当我对 a 执行相同操作时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
为什么equal_range上set<pair<int,int>>不包括包围值（12）的范围，即[11.20]

4

5 回答 5

4

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) xy

所以equal_range告诉你 [12,12] 将插入 [11,20] 之后和 [21,30] 之前，这是正确的。

如果要将对视为值的范围，则需要编写代码来执行此操作，而不是假设对的内置比较可以做到这一点。您实际上是在尝试在一系列整数对中找到一个整数 12，但是已经编写了代码来在一系列整数对中找到一对 [12,12]。那不是一回事。

于 2012-11-11T23:12:38.383 回答
3

它不包括[11, 20]在范围内，因为它不包括范围内的任何内容。没有与 相等的元素[12, 12]，因此它返回一个空范围（由半开区间 表示[x, x)）。

顺便说一句，取消引用范围的上限可能会调用未定义的行为，因为它可能等于s.end().

于 2012-11-11T23:05:33.367 回答
1

该对在 之后和 之前[12, 12]排序。[11, 20][21, 30]

std::set::equal_range()包括一系列相等的元素。您的集合中没有相等的元素（尤其是 not [11, 20]），所以equal_range()返回[21, 30], [21, 30]。

于 2012-11-11T23:15:36.247 回答
1

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以定位 value 的下限（即 pair(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) 上搜索，但找不到，它返回(21,30)

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

于 2012-11-11T23:22:32.587 回答
1

我认为你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";
}

（或类似的东西......）

于 2012-11-11T23:24:39.773 回答