std::ranges::find_if - std::common_reference中没有类型

Question

我正在使用 SG14 flat_map 作为容器。

与标准映射一样，它需要 Key 和 Value 模板参数。

然而，与标准映射不同的是，它不会在二叉搜索树中存储 std::pair<Key, Value>，而是将键和值存储在两个单独的容器中（额外的模板参数默认为 std::vector）。

template<
    class Key,
    class Mapped,
    class Compare = std::less<Key>,
    class KeyContainer = std::vector<Key>,
    class MappedContainer = std::vector<Mapped>
>
class flat_map

然后按以下方式定义了一些类型：

using key_type = Key;
using mapped_type = Mapped;
using value_type = std::pair<const Key, Mapped>;
using key_compare = Compare;
using const_key_reference = typename KeyContainer::const_reference;
using mapped_reference = typename MappedContainer::reference;
using const_mapped_reference = typename MappedContainer::const_reference;
using reference = std::pair<const_key_reference, mapped_reference>;
using const_reference = std::pair<const_key_reference, const_mapped_reference>;

如果我尝试在flat_map上使用std::ranges::find_if，就会出现错误：

error: no type named ‘type’ in 
    ‘struct std::common_reference<std::pair<const Key&, const Value&>&&, 
                                  std::pair<const Key, Value>&>’
  121 | auto it = std::ranges::find_if(map, [](auto& kv) { return kv.second.name == "foo"; });
      |           ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

如果我使用非范围的 find_if，一切都“正常工作”。

auto it = std::find_if(map.begin(), map.end(), [](auto& kv) { return kv.second.name == "foo"; });

为什么std::ranges::find_if无法工作？

godbolt上的示例：https://godbolt.org/z/r93f7qozr 编辑： @Brian提供了一个成功编译的示例，尽管与我的略有不同，特别是我的映射是const，并且我将lambda参数作为const ref接受...

这引出了以下问题：

• const 范围和 const auto& lambda 参数的组合为什么无法编译，而传递可变范围可以工作，并且按值接受 lambda 参数也可以工作？
• 我相信将非范围的 std::find_if 算法的 lambda 参数按值（auto 而不是 const auto&）作为一种反模式，因为这会导致每个元素被复制 - 因此使用 const auto& 应该是首选... 最小惊讶原则意味着我认为在 std::ranges 中也应该是这样的 - 这不是这种情况吗？

- Steve Lorimer

---

1. 请提供一个 [mre]。
2. 无法重现，在GCC和clang trunks上，stdext::flat_map似乎可以与std::ranges::find_if很好地配合使用。

- Brian61354270

你也可以看一下这里的可能实现：https://en.cppreference.com/w/cpp/algorithm/ranges/find。也许将其复制到一个新文件中，以便您可以尝试一下，看看问题是否是flat_map缺少某些东西（别名成员、成员函数如operator*等）。 - Enlico

@Brian，请在此处查看示例：https://godbolt.org/z/r93f7qozr（我已更新问题以包括链接）......值得注意的是，我的代码和你的代码之间的区别在于map是const类型，并且我将lambda参数作为const引用。 - Steve Lorimer

@SteveLorimer 很好，很高兴我们缩小了范围！值得注意的是，您在使用非const引用和可变映射时会遇到相同的错误，但在使用const引用和可变映射时不会。 - Brian61354270

注意，我会像这样编写代码：auto it1 = std::ranges::find(map, 0, &decltype(map)::value_type::second);，但是无论如何，它都不起作用。你会得到很多未满足的要求，比如“在'struct std::common_reference<std::pair<const int&, const int&>&&, std::pair<const int, int>&>'中没有名为'type'的类型”。 - JHBonarius

@JHBonarius +1 针对投影！ - Steve Lorimer

Answer 1

为什么将const范围和const auto& lambda参数组合在一起会无法编译，而传递可变范围可以工作，并且通过值获取lambda参数也可以工作？

首先，flat_map的迭代器的operator*()定义如下：

reference operator*() const {
  return reference{*kit_, *vit_};
}

reference 类型是 pair，这意味着 operator*() 将返回一个 prvalue 的 pair，所以 lambda 的参数类型不能为 auto&，即 lvalue 引用，因为它无法绑定 rvalue。

其次，const flat_map 不符合 input_range 概念，也就是说，它的迭代器不符合要求，而要求是 input_iterator，需要满足 indirectly_readable ，需要满足 common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&>，前者是 pair<const int&, const int&>&&，后者是 pair<const int, int>&，两者之间没有 common_reference。

解决方法是为它们定义 common_reference，就像 P2321 所做的那样（这也意味着你的代码在 C++23 中是合法的）。

template<class T1, class T2, class U1, class U2,
         template<class> class TQual, template<class> class UQual>
  requires requires { typename pair<common_reference_t<TQual<T1>, UQual<U1>>,
                                    common_reference_t<TQual<T2>, UQual<U2>>>; }
struct basic_common_reference<pair<T1, T2>, pair<U1, U2>, TQual, UQual> {
  using type = pair<common_reference_t<TQual<T1>, UQual<U1>>,
                    common_reference_t<TQual<T2>, UQual<U2>>>;
};

关于common_reference的详细信息，请参考此问题。

- 康桓瑋