c++ - C++98 中的异构容器查找

Question

在我正在进行的项目中，我不得不使用 c++98。需要在某些结构 vector 中执行快速查找，仅使用这些结构的一些元素作为键，到目前为止，我很高兴地传递给 std::lower_bound 和 std::upper_bound 一个 value 参数，其类型不同于那些结构的类型，以及一个可以正确处理这种异构情况的比较仿函数。

一切都按预期工作，但今天我突然意识到标准可能不允许这样做，我在几篇论文中找到了这种预感的证实，比如 this one它还对我正在学习的标准提出了修正案，该修正案已在 C++0x 中实现，如 this other paper confirms .

我的问题是:事实上我的代码是否按预期工作，尽管不遵守标准的字面意思，这仅仅是巧合，是具体实现，一个非保证的结果，我应该改变编译器什么的？

换句话说，考虑到这个代码库不会用任何东西编译，我真的应该真的真的改变我的代码以使其符合标准(这会使它变得非常复杂)，还是我可以不去打扰它呢？暂时除了 g++？

Answer 1

只有您可以决定保持现状是否值得冒险。但是，如果您转到 C++11，则措辞已更改以允许您正在做的事情。

我认为编译器供应商不太可能改变他们的标准库为旧版本标准工作的方式。所以我看不出您的 C++98 代码很可能会中断，除非您将它移至未经测试的编译器。即使发生这种情况，您始终可以实现自己的(替代)版本的 std::lower_bound 来适应。

根据我对 C++11 标准的阅读，你没问题。

25.4.3.1 lower_bound [ lower.bound ]

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

1 Requires: The elements e of [first,last) shall be partitioned with respect to the expression e < value or comp(e, value).

2 Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

3 Complexity: At most log 2 (last − f irst) + O(1) comparisons.

要求 2 并未规定 value 与 *e 属于同一类型。

您引用的文档还说:

But is it legal? The standard's position on this question is not encouraging. For one thing, 25.3 says that for the algorithms to work correctly, the comparison object has to induce a strict weak ordering on the values.

这来自 C++03 标准，不是我在 C++11 标准中找到的措辞:

25.4 Sorting and related operations [ alg.sorting ]

3 For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

它对 std::lower_bound 使用的算法给出了明确的豁免:

25.4.3 Binary search [ alg.binary.search ]

1 All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the implied or explicit comparison function.

此措辞允许比较函数的“参数”与容器元素具有不同类型。它只需要匹配“搜索键”。