1

int値iを囲むすべての範囲[a、b]を見つけようとしています。ここで、a <= i<=bです。set<std:pair<int,int>>範囲のセットに使用しています。

以下では、yieldで等しい範囲を使用すると、範囲vector<int>の開始と終了を1つ過ぎた結果になります。

について同じことを行うと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>>値（12）を囲む範囲、つまり[11.20] がequal_rangeに含まれないのはなぜですか。

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]の「範囲内」ではなく、それよりも大きいです。のless-than演算子はstd::pair、最初の要素を最初に比較し、それらが等しい場合にのみ2番目の要素を調べます。したがって、はどのmake_pair(11,x)要素よりも小さくなります。make_pair(12, y) xy

つまりequal_range、[12,12]は[11,20]の後、[21,30]の前に挿入されるということです。これは正しいことです。

ペアを値の範囲として扱いたい場合は、それを行うためのコードを記述する必要があります。ペアの組み込みの比較がそれを行うと想定しないでください。あなたは実際にはintのペアの範囲でint12を見つけようとしていますが、intのペアの範囲でペア[12,12]を見つけるコードを書いています。それは同じことではありません。

于 2012-11-11T23:12:38.383 に答える
3

範囲内に何も[11, 20]含まれていないため、範囲には含まれていません。に等しい要素がないため、空の範囲を返します（ハーフオープン間隔で表されます）。[12, 12][x, x)

ところで、範囲の上限を逆参照すると、に等しい可能性があるため、未定義の動作が呼び出される可能性がありますs.end()。

于 2012-11-11T23:05:33.367 に答える
1

std::set<std::pair<int, int> >整数と交差させるのにあまり役立たないと思います。s.lower_bound(std::make_pair(i + 1, i + 1)検索を切り捨てることはできますが、2番目の境界が十分に大きい場合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 に答える
1

ペアは前後に[12, 12]ソートされます。[11, 20][21, 30]

std :: set :: equal_range（）には、等しい要素の範囲が含まれています。セットに等しい要素がない（特にない[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、値の下限（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 に答える