Алгоритмы, не меняющие последовательность

Операции с каждым элементом (For each)

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

     for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f. Принято, что f не применяет какую-то непостоянную функцию к разыменованному итератору. f применяется точно last-first раз. Если f возвращает результат, результат игнорируется.

Найти (Find)

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

     find возвращает первый итератор i в диапазоне [first, last), для которого соблюдаются следующие соответствующие условия: *i == value, pred (*i) == true. Если такой итератор не найден, возвращается last. Соответствующий предикат применяется точно find(first, last, value) - first раз.

Найти рядом (Аdjacent find)

template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
         BinaryPredicate binary_pred);

     adjacent_find возвращает первый итератор i такой, что i и i+1 находятся в диапазоне [first, last) и для которого соблюдаются следующие соответствующие условия: *i == *(i + 1), binary_pred(*i, *(i + 1)) == true. Если такой итератор i не найден, возвращается last. Соответствующий предикат применяется, самое большее, max((last - first) - 1, 0) раз.

Подсчет (Count)

template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value, Size& n);

template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

     count добавляет к n число итераторов i в диапазоне [first, last), для которых соблюдаются следующие соответствующие условия: *i == value, pred (*i) == true. Соответствующий предикат применяется точно last-first раз.

     count должен сохранять результат в параметре ссылки вместо того, чтобы возвращать его, потому что тип размера не может быть выведен из встроенных типов итераторов, как, например, int*.

Отличие (Mismatch)

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
    InputIterator1 last1, InputIterator2 first2,
    BinaryPredicate binary_pred);

     mismatch возвращает пару итераторов i и j таких, что j == first2 + (i - first1) и i является первым итератором в диапазоне [first1, last1), для которого следующие соответствующие условия выполнены: !(*i == *(first2 + (i - first1))), binary_pred (*i, *(first2 + (i - first1))) == false. Если такой итератор i не найден, пара last1 и first2 + (last1 - first1) возвращается. Соответствующий предикат применяется, самое большее, last1 - first1 раз.

Сравнение на равенство (Equal)

template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 
        BinaryPredicate binary_pred);

     equal возвращает true, если для каждого итератора i в диапазоне [first1, last1) выполнены следующие соответствующие условия: *i == *(first2 + (i - first1)), binary_pred(*i, *(first2 + (i - first1))) == true. Иначе equal возвращает false. Соответствующий предикат применяется, самое большее, last1 - first1 раз.

Поиск подпоследовательности (Search)

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, 
    ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, 
    class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, 
    ForwardIterator2 first2, ForwardIterator2 last2, 
    BinaryPredicate binary_pred);

     search находит подпоследовательность равных значений в последовательности. search возвращает первый итератор i в диапазоне [first1, last1 - (last2 - first2)) такой, что для любого неотрицательного целого числа n, меньшего чем last2 - first2, выполнены следующие соответствующие условия: *(i + n) == *(first2 + n), binary_pred(*(i + n), *(first2 + n)) == true. Если такой итератор не найден, возвращается last1. Соответствующий предикат применяется, самое большее, (last1 - first1) * (last2 - first2) раз. Квадратичное поведение, однако, является крайне маловероятным.



Опубликовал admin
18 Июл, Воскресенье 2004г.



Программирование для чайников.