8

这个问题之后,我尝试复制粘贴在 VS2010 中找到的示例:

#include <algorithm>
#include <vector>
#include <iostream>

struct S
{
    int number;
    char name;

    S ( int number, char name  )
        : number ( number ), name ( name )
    {}

    // only the number is relevant with this comparison
    bool operator< ( const S& s ) const
    {
        return number < s.number;
    }
};

struct Comp
{
    bool operator() ( const S& s, int i )
    {
        return s.number < i;
    }

    bool operator() ( int i, const S& s )
    {
        return i < s.number;
    }
};

int main()
{
    std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {3,'F'}, {4,'G'} }; //this syntax won't compile in VS2010, so you can leave an empty vector here

    auto p = std::equal_range(vec.begin(),vec.end(),2,Comp());

    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->name << ' ';
}

这将在发布模式下编译正常,但在调试模式下,它将无法编译。原因是在调试模式下,实现将使用给定的谓词检查迭代器范围是否已经排序:

template<class _FwdIt,
    class _Pr> inline
    void _Debug_order2(_FwdIt _First, _FwdIt _Last, _Pr _Pred,
        _Dbfile_t _File, _Dbline_t _Line, forward_iterator_tag)
    {   // test if range is ordered by predicate, forward iterators
    for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
        if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
            _DEBUG_ERROR2("sequence not ordered", _File, _Line);
    }

这最终调用:

template<class _Pr, class _Ty1, class _Ty2> inline
    bool _Debug_lt_pred(_Pr _Pred,
        const _Ty1& _Left, const _Ty2& _Right,
        _Dbfile_t _File, _Dbline_t _Line)
    {   // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
    if (!_Pred(_Left, _Right))
        return (false);
    else if (_Pred(_Right, _Left))
        _DEBUG_ERROR2("invalid operator<", _File, _Line);
    return (true);
    }

除了在我的情况下,没有operator()人可以同时接受左右“S”论点。那么,Visual 实现中是否存在错误?还是原始示例不应该是可移植的?我想我可以通过提供第三个 operator() 重载来使它工作,但它似乎应该在没有的情况下工作

谢谢

4

5 回答 5

12

标准中没有任何内容要求比较器可以使用范围中的两个对象进行调用。所以这是 VS 2010 使用的标准库中的一个错误。

以下是所有相关要求(引用 C++11):

[下限]§1+2:

1要求:的元素e[first,last)根据表达式 ... 进行划分 comp(e, value)

2返回:i范围内最远的迭代器,使得对于范围内[first,last]的任何迭代器,以下相应条件成立: ... 。j[first,i)comp(*j, value) != false

[上限]§1+2:

1要求:的元素e[first,last)根据表达式 ... 进行划分!comp(value, e)

2返回:i范围内最远的迭代器,使得对于范围内[first,last]的任何迭代器,以下相应条件成立: ... 。j[first,i)comp(value, *j) == false

[equal.range]§1+2:

1要求:的元素e[first,last)根据表达式 ...comp(e, value)和进行划分!comp(value, e)。此外,对于, ...的所有元素e,应暗示。[first, last)comp(e, value)!comp(value, e)

2回报:

...

make_pair(lower_bound(first, last, value, comp),
          upper_bound(first, last, value, comp))

(省略号用于非比较器版本)。

于 2013-09-12T15:08:30.377 回答
2

Angew 已经引用了该标准并指出 VS 是有缺陷的。我只是想强调一下,VS2010这里有两个错误(在调试模式下):

  1. 它尝试使用Compare::operator(_Ty1, _Ty2)标准不要求存在的内容。这个已知的错误已由 Angew 突出显示,并由 Ben 的评论指出。

  2. 它测试输入范围是否已排序,标准也没有要求。这是一个更严重的错误,因为它降低了可用性,equal_range并且在最坏的情况下需要一个完整的范围,即使这在算法上不是必需的。也许有人可以向 MS 提交错误报告?

请注意,第一个错误只是equal_range第二个错误的结果(在 的实现中)。据推测,对于大多数应用程序,输入范围已经排序,部分原因是用户不必要地对其进行了排序(证明 MS 库中的错误会导致错误的用户代码),并且只需提供一个额外的比较运算符即可解决问题(至于 OP 的问题)。

于 2013-09-12T16:35:04.783 回答
1

[lib.equal.range] 告诉:

要求:类型 T 是 LessThanComparable (20.1.2)。

效果:找到最大的子范围 [i, j) 使得值可以插入到其中的任何迭代器 k 中而不会违反排序。k 满足相应条件:!(*k < value) && !(value < *k) 或 comp(*k, value) == false && comp(value, *k) == false。

您的代码满足这两个条件并且应该可以正常编译,这意味着它是 Visual Studio 中的一个错误。

于 2013-09-12T15:23:23.507 回答
1

作为一般答案。每个编译器和标准库都会有他们没有正确实现标准的怪癖和地方。这意味着除非代码在不同的平台上进行测试,否则总有可能需要进行细微的更改。

从好的方面来说,如果有人试图保持标准,这些变化应该是非常小的。

于 2013-09-12T15:31:15.530 回答
-1

为了使相等范围正常工作,需要对范围进行排序,我认为 VS 编译器试图说您的意图是错误的,也许?

于 2013-09-12T15:15:05.793 回答