c++11 - 为什么 std::is_permutation 不能在两种不同类型的数据之间起作用？

Question

假设我有一个整数向量和字符串向量，并且我想比较它们是否具有等效元素，而不考虑顺序。最后，我问整数向量是否是字符串向量的排列(反之亦然)。我希望能够只调用 is_permutation，指定一个允许我比较两者的二元谓词，然后继续我的生活。例如:

bool checkIntStringComparison( const std::vector<int>& intVec,
                 const std::vector<std::string>& stringVec,
                 const std::map<int, std::string>& intStringMap){
  return std::is_permutation<std::vector<int>::const_iterator, std::vector<std::string>::const_iterator>(
        intVec.cbegin(), intVec.cend(), stringVec.cbegin(), [&intStringMap](const int& i, const std::string& string){
    return string == intStringMap.at(i);
  });
}

但是尝试编译它(在 gcc 中)会返回一条错误消息，归结为:

no match for call to stuff::< lambda(const int&, const string& >)(const std::_cxx11::basic_string&, const int&)

看看它如何从 lambda 切换调用签名？如果我交换它们，签名就会以另一种方式交换。

深入研究这个错误，似乎标准为 std::is_permutation 指定了 ForwardIterator1 和 2 必须是相同的类型。所以我理解这方面的编译器错误。但为什么会这样呢？如果我提供一个允许我比较两者的二元谓词(或者如果我们之前在两者之间定义了一些相等运算符？)，那么算法的真正核心不就是搜索容器 1 以确保其所有元素都是在容器 2 中唯一吗？

Answer 1

问题是一个元素可以出现多次。这意味着谓词不仅需要能够将第一个范围的元素与第二个范围的元素进行比较，还要能够将第一个范围的元素与其自身进行比较:

if (size(range1) != size(range2))
    return false;
for (auto const& x1 : range1)
    if (count_if(range1, [&](auto const& y1) { return pred(x1, y1); }) !=
        count_if(range2, [&](auto const& y2) { return pred(x1, y2); }))
        return false;
return true;

由于创建一个采用两个不同签名的函数对象相对比较棘手，并且传递两个谓词会令人困惑，因此最简单的选择是指定两个范围必须具有相同的值类型。

您的选择是:

• 将一个范围(或两个范围)包装在提供相同值类型的转换中(例如使用 Boost.Adaptors.Transformed)；
• 编写您自己的 std::is_permutation 实现(例如复制 cppreference 上的示例实现)；
• 实际上，请注意，gcc(即 libstdc++)实现并不强制要求值类型相同；它只需要几个您必须提供的签名，因此请编写一个多态谓词，例如函数对象或多态 lambda，或者具有可从两种范围值类型转换的参数类型(例如，在您的情况下 boost::variant<int, string> - 丑陋，但可能没那么糟糕)。这是不可移植的，因为另一个实现可能会选择强制执行该要求。