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 сначала не проверяет, имеют ли 2 контейнера одинаковые size()? Была ли законная причина?

Answer 1

Замечание: почему std :: equal сначала не проверяет, имеют ли два контейнера одинаковый размер ()? Была ли законная причина?

Как? Вы не передаете контейнеры функции, вы передаете в итераторы . Функция не может узнать размер второго контейнера . Все, что он может сделать, это предположить, что пользователь прошел в двух допустимых диапазонах контейнера (то есть, что второй диапазон правильно указан как полуоткрытый интервал [lst2.begin(), lst2.begin() - lst1.begin() + lst1.end() [) и действовать соответственно.

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

Чтобы оба диапазона имели одинаковое количество элементов, подпись должна содержать конец второго диапазона.

Answer 3

Поскольку проверка размера может быть O(n) операцией.

Answer 4

Это дает вам правильный ответ - вы сказали ему проверить, равны ли два контейнера в диапазоне от lst1.begin() до lst1.end(). Вы все еще сравниваете два пустых списка в отношении equal(). Если вы измените код для сравнения с lst2.begin() на lst2.end(), вы получите то, что ожидали.

Answer 5

C ++ 14 добавил перегрузку с четырьмя аргументами, очень похожую на ответ в ответе Самуэля Клатчко. И, по крайней мере, две реализации STL, которые я проверял (libc ++ и MSVC), реализуют очевидную оптимизацию проверки расстояния для итераторов произвольного доступа.