C++ std::equal——不测试两个大小相等的范围的理由是什么？

Question

我刚刚编写了一些代码来测试 std::equal 的行为，然后感到惊讶：

int main()
{
  try
  {
    std::list<int> lst1;
    std::list<int> lst2;

    if(!std::equal(lst1.begin(), lst1.end(), lst2.begin()))
      throw std::logic_error("Error: 2 empty lists should always be equal");

    lst2.push_back(5);

    if(std::equal(lst1.begin(), lst1.end(), lst2.begin()))
      throw std::logic_error("Error: comparing 2 lists where one is not empty should not be equal");
  }
  catch(std::exception& e)
  {
    std::cerr << e.what();
  }  
}

输出（令我惊讶）：

Error: comparing 2 lists where one is not empty should not be equal

观察：为什么它是 std::equal 不会首先检查两个容器是否具有相同的 size() ？有正当理由吗？

Answer 1

观察：为什么 std::equal 不首先检查两个容器是否具有相同的 size() ？有正当理由吗？

如何？您不将容器传递给函数，而是传入迭代器。函数无法知道第二个容器的大小。它所能做的就是假设用户确实传入了两个有效的容器范围（即第二个范围被正确指定为半开区间 [lst2.begin(), lst2 .begin() - lst1.begin() + lst1.end()[) 并采取相应行动。

Answer 2

您始终可以编写自己的 equal 版本，它可以有效地实现您想要的功能：

template <class InputIterator1, class InputIterator2>
bool equalx(InputIterator1 first1, InputIterator1 last1,
            InputIterator2 first2, InputIterator2 last2)
{
  while ((first1 != last1) && (first2 != last2))
  {
    if (*first1 != *first2)   // or: if (!pred(*first1,*first2)), for pred version
      return false;
    ++first1; ++first2;
  }
  return (first1 == last1) && (first2 == last2);
}

为了确保两个范围具有相同数量的元素，签名必须包含第二个范围的结尾。

Answer 3

因为检查大小可能是一个 O(n) 操作。

Answer 4

它给了你正确的答案 - 你告诉它检查两个容器在 lst1.begin() 到 lst1.end() 范围内是否相等。就 equal() 而言，您仍在比较两个空列表。如果您将代码从 lst2.begin() 更改为 lst2.end() 进行比较，您将得到您所期望的结果。

Answer 5

C++14 添加了一个四参数重载，就像 R Samuel Klatchko 的答案中的重载一样。至少我检查的两个 STL 实现（libc++ 和 MSVC）为随机访问迭代器实现了明显的距离检查预先优化。