英文:
How to make ranges::binary_search (heterogeneous search in particualar) work with references
问题
我正在尝试使引用包装器与异构搜索一起工作，并使其符合范围要求。这是我想要工作的代码段：
struct addressable { int address; };
template <typename T>
struct ref : std::reference_wrapper<T> {
// 用于异构搜索的比较操作
}
template <typename T>
ref<T> wrap_ref(T& value) { return {value}; }
int main() {
const std::vector<addressable> nums { {1}, {2}, {3}, {4}, {5}, {6} };
ref_vec<const addressable> num_refs;
for (const auto& num : nums) { num_refs.push_back(wrap_ref(num)); }
const auto found = std::ranges::binary_search(num_refs, 2); // 不起作用
}
对于经典的 std 算法，异构搜索正常工作（对于它们来说，实现 < 和 == 就足够了）。现在，ranges 的算法有更严格的要求，所以我尝试以以下方式实现强制排序操作：
template <typename T>
struct ref : std::reference_wrapper<T> {
auto operator<=>(const ref<T>& other) const {
return std::reference_wrapper<T>::get().address <=> other.get().address;
}
bool operator==(const ref<T>& other) const {
return std::reference_wrapper<T>::get().address == other.get().address;
}
// 异构比较
friend auto operator<=>(const ref<T>& l, const int r) { return l.get().address <=> r; }
friend auto operator<=>(const int l, const ref<T>& r) { return l <=> r.get().address; }
friend bool operator==(const ref<T>& l, const int r) { return l.get().address == r; }
friend bool operator==(const int l, const ref<T>& r) { return l == r.get().address; }
};
然而，这导致了一系列编译错误，似乎在警告 indirect_strict_weak_order 和 strict_weak_order 概念未被解析。我不明白为什么它们没有被解析 - 我们有强序，并且据我了解，引用在间接部分上得到了适当的支持。我漏掉了什么？
这里是编译器探索器的示例链接：https://godbolt.org/z/8xaWfah9b。
英文:
I am trying to make reference wrappers work with heterogeneous search, and make it ranges-compliant. Here is the snippet I want to work:
struct addressable { int address; };
template <typename T>
struct ref : std::reference_wrapper<T> {
// comparisons for heterogeneous search
}
template <typename T>
ref<T> wrap_ref(T& value) { return {value}; }
int main() {
const std::vector<addressable> nums { {1}, {2}, {3}, {4}, {5}, {6} };
ref_vec<const addressable> num_refs;
for (const auto& num : nums) { num_refs.push_back(wrap_ref(num)); }
const auto found = std::ranges::binary_search(num_refs, 2); // doesn't work
}
The heterogeneous search is working fine for classic std algorithms (for them it is enough to implement < and ==. Now, ranges ones have more stringent requirements, so I tried implementing strong ordering operations in the following manner:
template <typename T>
struct ref : std::reference_wrapper<T> {
auto operator<=>(const ref<T>& other) const {
return std::reference_wrapper<T>::get().address <=> other.get().address;
}
bool operator==(const ref<T>& other) const {
return std::reference_wrapper<T>::get().address == other.get().address;
}
// heterogeneous comparisons
friend auto operator<=>(const ref<T>& l, const int r) { return l.get().address <=> r; }
friend auto operator<=>(const int l, const ref<T>& r) { return l <=> r.get().address; }
friend bool operator==(const ref<T>& l, const int r) { return l.get().address == r; }
friend bool operator==(const int l, const ref<T>& r) { return l == r.get().address; }
};
This, however, leads to a number of compilation errors, which seem to warn about indirect_strict_weak_order and strict_weak_order concepts not being resolved. I do not understand why aren't they resolved - we have strong order, and references are, to my understanding, properly supported for the indirect part. What am I missing?
Here is compiler explorer example: https://godbolt.org/z/8xaWfah9b.
答案1
得分: 6
Sure, here's the translated content:
异构搜索对经典的
std算法工作良好（对它们来说，只需实现<和==就足够了）。现在，ranges版本具有更严格的要求。
ranges 版本默认使用 ranges::less 进行比较，它对比较类型有比 std 版本更严格的语法和语义要求，但您仍然可以将 std::less 作为比较器传递，它只要求表达式 lhs < rhs 有效即可。
const auto found = ra::binary_search(num_refs, 2, std::less{});
英文:
> The heterogeneous search is working fine for classic std algorithms
> (for them it is enough to implement < and ==. Now, ranges ones have
> more stringent requirements
The ranges version uses ranges::less for comparison by default, which has stricter syntactic and semantic requirements for comparison types than the std version, but you can still pass std::less as a comparator that only requires expressions lhs < rhs to be valid
const auto found = ra::binary_search(num_refs, 2, std::less{});
答案2
得分: 5
Ranges算法不支持异构比较。请使用投影：
std::ranges::binary_search(num_refs, 2, {}, [](ref<const addressable> r) {
return r.get().address;
});
在这种特定情况下，您不能使用 ranges::less{}(2, ref<const addressable>(...))，因为ranges::less要求两个参数在彼此之间是totally_ordered，这要求它们具有common_reference。在const int&和const ref<const addressable>&之间没有共同的引用，除非您添加从ref<const addressable>到const int&的转换。
英文:
Ranges algorithms don't work with heterogenous comparisons. Use a projection:
std::ranges::binary_search(num_refs, 2, {}, [](ref<const addressable> r) {
return r.get().address;
});
In this specific case, you can't use ranges::less{}(2, ref<const addressable>(...)), because ranges::less requires the two arguments to be totally_ordered with each other, which requires them to have a common_reference. There is no common reference between const int& and const ref<const addressable>&, unless you add a conversion from ref<const addressable> to const int&.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论