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()？这样做是否有合理的原因？

- sivabudh

---

检查列表的大小不是常量时间 - 您必须迭代列表。 - anon

@Neil：它可能具有常数时间。Microsoft实现具有常数时间的size()。在容器要求中，C++标准仅表示size()应具有常数时间复杂度。 - James McNellis

GCC 实现具有线性时间 size()。 - Mike Seymour

请参考https://dev59.com/GHVC5IYBdhLWcg3woSxW，讨论为什么`std::list()`可能具有恒定复杂度或不具有恒定复杂度。 - Michael Burr

这次讨论的暗示似乎是，如果第二个列表比第一个列表短，那么std:equal将导致我们走到列表的末尾并导致SEGV。如果是这种情况，并且您不知道第二个列表的长度，那么这种方法怎么可能是安全的呢？ - user1911496

Answer 1

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

如何操作？您将不是将容器传递给函数，而是传递给迭代器。该函数无法知道第二个容器的大小。它能做的就是假定用户传递了两个有效的容器范围（即第二个范围被正确指定为左闭右开区间[lst2.begin()，lst2.begin()-lst1.begin()+lst1.end()）并进行相应操作。

- Konrad Rudolph

---

@ShaChris32：是的，你可以使用==来比较两个列表（或者一般情况下，相同类型的两个标准容器）。 - Mike Seymour

在我看来，它与迭代器一起工作而不是容器，是STL最大的优势之一。 - John Dibling

@James：这个想法是将算法与容器分离，而迭代器可以很好地实现这一点。话虽如此，Alexandrescu 最近有一个名为“Iterators Must Go”的演讲，推荐使用范围（ranges）代替迭代器。我同意他的观点。 - GManNickG

@Konrad：是的，那是容器的要求之一。 - Mike Seymour

@Mike：如果我没记错的话，容器和迭代器范围都可以被视为一个范围（你可以创建一个iterator_range对象，存储两个迭代器，并通过相同的begin()和end()方法使它们可访问）。它在boost中被广泛使用，非常方便。 - UncleBens

Answer 2

您可以编写自己的版本的等于函数，以实现您想要的效果：

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);
}

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

- R Samuel Klatchko

Answer 3

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

- eduffy

---

不，没有一种便携式的方法可以知道第二个容器的大小。这个信息对于equals来说是无法直接或间接获得的。 - Konrad Rudolph

@Konrad：当然有啦：只需从开头到结尾迭代两个列表并计算元素数量即可。 - John Dibling

@John：你是怎么获取list2的末尾迭代器的？ - Bill

我当然没有。不知道我当时在想什么。 - John Dibling

第二个范围甚至不需要指定大小。例如，您有一个生成随机数的输入迭代器，并且您想将一堆值与该列表中的序列进行比较（别问我为什么）。 - UncleBens

Answer 4

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

- Carl Norum

Answer 5

C++14新增了一个类似于R Samuel Klatchko答案中的四个参数重载。而且我检查过的至少两个STL实现（libc++和MSVC）都为随机访问迭代器实现了明显的距离检查优化。

- dhaffey