应该设置:: equal_range()返回对(set :: lower_bound()，set :: upper_bound()) [英] Should set::equal_range() return pair( set::lower_bound(), set::upper_bound() )

问题描述

是的，我知道，我应该有一个复制品，但是复制品很烦人.在制作一个(也许给clang一个bug)之前，我想确保我对应该应该如何工作的理解是正确的.

Yeah, I know, I should have a repro, but the repro is annoying to produce. Before I produce one (and maybe give clang a bug) I want to ensure that my understanding of how things should work is correct.

• MSVC:将 set :: equal_range()返回为 {lower_bound()，upper_bound()} .

Clang:将 set :: equal_range()返回为 {lower_bound()，upper_bound()-1} .(使用stdlib = libc ++)-当然是我的示例.

Clang: Returns set::equal_range() as {lower_bound(),upper_bound()-1}. (using stdlib=libc++) - and of course for my example.

我对STL编程的最近20年期望是MSVC是正确的.实际上，我20年前编写的代码曾经在clang和gcc中都可以使用，但是现在仅在MSVC中可以使用(也许gcc-我还没有尝试过-我正在使用一些标头C ++ 20，并且仅在stdlib = libc ++和MSVC中使用，而在gcc中则没有).

My expectation for the last 20 years of STL programming is that MSVC is correct. And in fact the code I am editing I wrote 20 years ago and it used to work in both clang and gcc, but now is only working in MSVC (and maybe gcc - I haven't tried it - I am using some headers that are C++20 and only in stdlib=libc++ and MSVC but not in gcc ).

无论如何，我对 set :: equal_range()应该返回正确的内容的假设是吗?

Anyway, is my assumption about what set::equal_range() should return correct?

好吧，看看吧:

带有-stdlib = libc ++的lang语: https://godbolt.org/z/xfnasKa73

Clang with -stdlib=libc++: https://godbolt.org/z/xfnasKa73

没有-stdlib = libc ++的Clang: https://godbolt.org/z/5qYEj4MEd

Clang without -stdlib=libc++: https://godbolt.org/z/5qYEj4MEd

让我知道您是否认为我的比较者是虚假的.

Let me know if you think my comparator is bogus.

这是测试代码:

#include <iostream>
#include <utility>
#include <set>

using namespace std;

struct Range : public pair< size_t, size_t >
{
    using pair::pair;
    bool operator < ( Range const & _r ) const
    {
        return second < _r.first;
    }
};

typedef set< Range > vTySet;

int
main()
{
    vTySet setRanges = {{0,0},{9,9},{10,10},{13,13},{32,32},{34,34},{61,61},{65,90},{101,101},{110,110}};
    Range rngTest = { 97, 122 };
    pair< vTySet::iterator, vTySet::iterator > pritEqualRange = setRanges.equal_range( rngTest );
    size_t nDistEqualRange = distance( pritEqualRange.first, pritEqualRange.second );
    pair< vTySet::iterator, vTySet::iterator > pritLowerUpper = { setRanges.lower_bound( rngTest ), setRanges.upper_bound( rngTest ) };
    size_t nDistLowerUpper = distance( pritLowerUpper.first, pritLowerUpper.second );
    cout << "nDistEqualRange:" << nDistEqualRange << "\n";
    cout << "nDistLowerUpper:" << nDistLowerUpper << "\n";
}

推荐答案

用于 std :: set 的任何自定义比较器都应满足

Any custom comparator that is used for std::set should satisfy Compare requirements (strict weak ordering + equivalence). You have UB in your code, and the difference you see is the consequence of that UB. In your example, the elements are pairs (a, b) and the comparator (let's call it less) is (a, b) < (c, d) iff b < c.

考虑两对(5，2)和(6，3).不对称属性要求(5，2)<(6，3)为true，则(6，3)<(5，2)应该为false.但这也是事实:

Consider two pairs (5, 2) and (6, 3). The asymmetry property requires that if (5, 2) < (6, 3) is true, then (6, 3) < (5, 2) should be false. But it is also true:

Range r1(5, 2);
Range r2(6, 3);
std::cout << less(r1, r2); // 1
std::cout << less(r2, r1); // 1, but should be 0

这样的比较器也打破了等价关系的传递性:

The transitivity of the equivalence relation is also broken by such a comparator:

Range r1(1, 3);
Range r2(2, 5);
Range r3(4, 6);
std::cout << equiv(r1, r2); // 1
std::cout << equiv(r2, r3); // 1
std::cout << equiv(r1, r3); // 0, but should be 1

演示

应注意，这些要求不仅适用于集合中的元素，而且还适用于您作为键传递给 std :: set :: equal_range(const Key&)的元素.

It should be noted that these requirements apply not only to the elements in the set, but also to those that you pass as a key to std::set::equal_range(const Key&).

这篇关于应该设置:: equal_range()返回对(set :: lower_bound()，set :: upper_bound())的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！