Проверьте, является ли один диапазон поддиапазоном другого диапазона в хорошем стиле STL

Question

Предположим, у нас есть два диапазона r1 = [first1, last1) и r2 = [first2, last2)

Предположим, что r2 является поддиапазоном из r1, если существуетi>=0, что

1. [first1 + i, first1 + i + last2 - first2) - допустимый диапазон

2. для всех j в [0, last2 - first2):

   *(first1 + i + j) == *(first2 + j)
   

Вложенный цикл может легко определить, является ли r2 поддиапазоном r1, или даже одним циклом с вложенным вызовом шаблона std::equal.Есть ли более сжатый STL-способ выразить ту же идею в C ++?Также приветствуются решения на C ++ 0x.Заранее спасибо.

Answer 1

Я думаю std::search это то, что вы ищете.From http://www.cplusplus.com/reference/algorithm/search/ [std::search] "Ищет диапазон [first1, last1) для первого вхождения последовательности, определенной [first2, last2), и возвращает итератор в свой первый элемент."

Answer 2

Это ваш первый комментарий:

#include <iostream>
#include <vector>
#include <iterator>

template<class MyIterator>
bool is_subrange(const MyIterator& first1, const MyIterator& last1, const MyIterator& first2, const MyIterator& last2)
{
   return std::distance(first1, first2) >=0 && std::distance(last2, last1) >= 0;
}

int main()
{
   std::vector<int> v;
   for (int i=0; i < 100; ++i)
      v.push_back(i);
   std::cout << std::distance(v.begin(), v.end()) << std::endl;
   std::cout << std::distance(v.end(), ++v.begin()) << std::endl;
   std::cout << is_subrange(v.begin(), v.end(), ++v.begin(), --v.end()) << std::endl;
   std::cout << is_subrange(++v.begin(), v.end(), v.begin(), --v.end()) << std::endl;

   return 0;
}

Это позволяет избежать сравнения каждого элемента при работе с поддиапазонами внутри таких же простых контейнеров, как векторы.

Конечно, функция is_subrange ()это очень просто и усложняется со списками, так как они дважды связаны, и, следовательно, расстояние никогда не может быть отрицательным, например, std :: distance (l.begin (), l.end ()) == 1 и std :: distance (l.end (), l.begin ()) == 1 возможны.Диапазоны как [100,0] и [20,4] также не обрабатываются этим простым образцом, но это выполнимо.

В любом случае, std :: search () выполнит работу, как ранее отправлено Марком-b

ура,