23 General utilities library [utilities]

23.14 Function objects [function.objects]

23.14.14 Searchers [func.search]

23.14.14.2 Class template boyer_­moore_­searcher [func.search.bm]

template <class RandomAccessIterator1,
          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
          class BinaryPredicate = equal_to<>>
  class boyer_moore_searcher {
  public:
    boyer_moore_searcher(RandomAccessIterator1 pat_first,
                         RandomAccessIterator1 pat_last,
                         Hash hf = Hash(),
                         BinaryPredicate pred = BinaryPredicate());

    template <class RandomAccessIterator2>
      pair<RandomAccessIterator2, RandomAccessIterator2>
        operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;

  private:
    RandomAccessIterator1 pat_first_;   // exposition only
    RandomAccessIterator1 pat_last_;    // exposition only
    Hash hash_;                         // exposition only
    BinaryPredicate pred_;              // exposition only
  };

boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());

1
#

Requires: Тип значения RandomAccessIterator1 должен соответствовать DefaultConstructible требованиям, CopyConstructible требованиям и CopyAssignable требованиям.

2
#

Requires: Для любых двух значений A и B типа iterator_­traits<RandomAccessIterator1>​::​value_­type, если pred(A, B) == true, то hf(A) == hf(B) должно быть true.

3
#

Effects: Создает boyer_­moore_­searcher объект, инициализируясь pat_­first_­ с pat_­first, pat_­last_­ с pat_­last, hash_­ с hfи pred_­ с pred.

4
#

Throws: Любое исключение брошенная копию конструктора RandomAccessIterator1, или с помощью конструктора по умолчанию, конструктор копирования или оператор присваивания копии типа ценностной RandomAccessIterator1или конструктор копирования или operator() из BinaryPredicate или Hash. Может bad_­alloc вызвать ошибку, если не может быть выделена дополнительная память, необходимая для внутренних структур данных.

template <class RandomAccessIterator2> pair<RandomAccessIterator2, RandomAccessIterator2> operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;

5
#

Requires: RandomAccessIterator1 и RandomAccessIterator2 должен иметь один и тот же тип значения.

6
#

Effects: Находит подпоследовательность равных значений в последовательности.

7
#

Returns: Пара итераторов i и j такие, что

  • (7.1)

    i - это первый итератор в диапазоне, [first, last - (pat_­last_­ - pat_­first_­)) такой, что для каждого неотрицательного целого числа, n меньшего, чем pat_­last_­ - pat_­first_­ выполняется следующее условие:, pred(*(i + n), *(pat_­first_­ + n)) != falseи

  • (7.2)

    j == next(i, distance(pat_­first_­, pat_­last_­)).

Возвращает, make_­pair(first, first) если [pat_­first_­, pat_­last_­) пусто, в противном случае возвращает, make_­pair(last, last) если такой итератор не найден.

8
#

Complexity: В большинстве (last - first) * (pat_­last_­ - pat_­first_­) случаев применения предиката.