» Главная
eXcode.ru » Статьи » С / С++
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 8





Алгоритмы библиотеки STL 2




Меняющие последовательность операции (Mutating sequence operations)

Копировать (Copy)

template <class InputIterator, class OutputIterator> 
OutputIterator copy(InputIterator first, InputIterator last, 
    OutputIterator result);

     copy копирует элементы. Для каждого неотрицательного целого числа n < (last - first) выполняется присваивание *( result + n) = *( first + n). Точно делается last - first присваиваний. Результат copy не определён, если result находится в диапазоне [first, last).

template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
    BidirectionalIterator1 last, BidirectionalIterator2 result);

     copy_backward копирует элементы в диапазоне [first, last) в диапазон [result - (last - first), result), начиная от last-1 и продолжая до first. Его нужно использовать вместо copy, когда last находится в диапазоне [result - (last - first), result). Для каждого положительного целого числа n <= (last - first) выполняется присваивание *(result - n) = *(last - n). copy_backward возвращает result - (last - first). Точно делается last - first присваиваний. Результат copy_backward не определён, если result находится в диапазоне [first, last).

Обменять (Swap)

template <class T> 
void swap(T& a, T& b);

     swap обменивает значения, хранимые в двух местах.

template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

     iter_swap обменивает значения, указанные двумя итераторами a и b.

tempate <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, 
    ForwardIterator1 last1, ForwardIterator2 first2);

     Для каждого неотрицательного целого числа n < (last1 - first1) выполняется перестановка: swap(*(first1 + n), *(first2 + n)). swap_ranges возвращает first2 + (last1 - first1). Выполняется точно last1 - first1 перестановок. Результат swap_ranges не определён, если два диапазона [first1, last1) и [first2, first2 + (last1 - first1)) перекрываются.

Преобразовать (Transform)

template  <class InputIterator, class OutputIterator, class Unary0peration> 
OutputIterator transform(InputIterator first, InputIterator last, 
    OutputIterator result, UnaryOperation op);

template  <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Binary0peration> 
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, 
    InputIterator2 first2, OutputIterator result,
    BinaryOperation binary_op);

     transform присваивает посредством каждого итератора i в диапазоне [result, result + (last1 - first1)) новое соответствующее значение, равное op(* (first1 + (i - result)) или binary_op(*(first1 + (i - result), *(first2 + (i - result))). transform возвращает result + (last1 - first1). Применяются op или binary_op точно last1 - first1 раз. Ожидается, что op и binary_op не имеют каких-либо побочных эффектов. result может быть равен first в случае унарного преобразования или first1 либо first2 в случае бинарного.

Заменить (Replace)

template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, 
    const T& new_value);

template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, 
    const T& new_value);

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

 
template <class InputIterator, class OutputIterator, class T> 
OutputIterator replace_copy(InputIterator first, InputIterator last,
    OutputIterator result, const T& old_value, const T& new_value);

template <class Iterator, class OutputIterator, class Predicate, class T> 
OutputIterator replace_copy_if(Iterator first, Iterator last,
    OutputIterator result, Predicate pred, const T& new_value);

     replace_copy присваивает каждому итератору i в диапазоне [result, result + (last - first)) значение new_value или *(first + (i - result)) в зависимости от выполнения следующих соответствующих условий: *(first + (i - result)) == old_value, pred(*(first + (i - result))) == true. replace_copy возвращает result + (last - first). Соответствующий предикат применяется точно last - first раз.

Заполнить (Fill)

template <class ForwardIterator, class T> 
void fill(ForwardIterator first, ForwardIterator last, const T& value);

template <class OutputIterator, class Size, class T>
OutputIterator fill_n(Output Iterator first, Size n, const T& value);

     fill присваивает значения через все итераторы в диапазоне [first, last) или [first, first + n). fill_n возвращает first + n. Точно делается last - first (или n) присваиваний.

Породить (Generate)

template <class ForwardIterator, class Generator> 
void generate(ForwardIterator first, ForwardIterator last, 
    Generator gen);

template <class OutputIterator, class Size, class Generator> 
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

     generate вызывает функциональный объект gen и присваивает возвращаемое gen значение через все итераторы в диапазоне [first, last) или [first, first + n). gen не берёт никакие параметры. generate_n возвращает first + n. Точно выполняется last - first (или n) вызовов gen и присваиваний.

Удалить (Remove)

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, 
    const T& value);

template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, 
    Predicate pred);

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

template <class InputIterator, class OutputIterator, class T> 
OutputIterator remove_copy(InputIterator first, InputIterator last, 
    OutputIterator result, const T& value);

template <class InputIterator, class OutputIterator, class Predicate> 
OutputIterator remove_copy_if(InputIterator first, InputIterator last, 
    OutputIterator result, Predicate pred);

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

Убрать повторы (Unique)

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

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

     unique устраняет все, кроме первого, элементы из каждой последовательной группы равных элементов, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == *(i - 1) или binary_pred(*i, *(i - 1)) == true. unique возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last - first) - 1 раз.

template <class InputIterator, class OutputIterator> 
OutputIterator unique_copy(InputIterator first, InputIterator last, 
    OutputIterator result);

template <class InputIterator, class OutputIterator, 
    class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last, 
    OutputIterator result, BinaryPredicate binary_pred);

     unique_copy копирует только первый элемент из каждой последовательной группы равных элементов, указываемых итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == *(i - 1) или binary_pied(*i, *(i - 1)) == true. unique_copy возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last - first) - 1 раз.

Расположить в обратном порядке (Reverse)

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, 
    BidirectionalIterator last);

     Для каждого неотрицательного целого числа i <= (last - first)/2 функция reverse применяет перестановку ко всем парам итераторов first + i, (last - i) - 1. Выполняется точно (last - first)/2 перестановок.

template <class BidirectionalIterator, class OutputIterator> 
OutputIterator reverse_copy(BidirectionalIterator first,
    BidirectionalIterator last, OutputIterator result);

     reverse_copy копирует диапазон [first, last) в диапазон [result, result + (last - first)) такой, что для любого неотрицательного целого числа i < (last - first) происходит следующее присваивание: *(result + (last - first) - i) = *(first + i). reverse_copy возвращает result + (last - first). Делается точно last - first присваиваний. Результат reverse_copy не определён, если [first, last) и [result, result + (last - first)) перекрываются.

Переместить по кругу (Rotate)

template <class ForwardIterator> 
void rotate(ForwardIterator first, ForwardIterator middle, 
    ForwardIterator last);

     Для каждого неотрицательного целого числа i < (last - first) функция rotate помещает элемент из позиции first + i в позицию first + (i + (last - middle)) % (last - first). [first, middle) и [middle, last) - допустимые диапазоны. Максимально выполняется last - first перестановок.

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, 
    ForwardIterator last, OutputIterator result);

     rotate_copy копирует диапазон [first, last) в диапазон [result, result + (last - first)) такой, что для каждого неотрицательного целого числа i < (last - first) происходит следующее присваивание: *(result + (i + (last - middle)) % (last - first)) = *(first + i). rotate_copy возвращает result + (last - first). Делается точно last - first присваиваний. Результат rotate_copy не определён, если [first, last) и [result, result + (last - first)) перекрываются.

Перетасовать (Random shuffle)

template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffie(RandomAccessIterator first, RandomAccessIterator last, 
    RandomNumberGenerator& rand);

     random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last - first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1.

Разделить (Partitions)

template <class BidirectionalIterator, class Predicate> 
BidirectionalIterator partition(BidirectionalIterator first, 
    BidirectionalIterator last, Predicate pred);

     partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred (*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Делается максимально (last - first)/2 перестановок. Предикат применяется точно last - first раз.

template <class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIterator first, 
    BidirectionalIterator last, Predicate pred);

     stable_partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last - first) * log(last - first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last - first раз.

К началу статьи





Добавил: LedWormДата публикации: 2006-03-14 10:09:55
Рейтинг статьи:3.00 [Голосов 5]Кол-во просмотров: 8524

Комментарии читателей

Всего комментариев: 0
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

На каком хостинге расположен ваш сайт?
На платном зарубежном
5% (6)
На платном российском
14% (19)
На народе
15% (20)
На халявном с пхп и перлом
21% (28)
На localhost :)
18% (24)
А хостинг это че-то типа пудинга?
5% (6)
У меня нет сайта :(
23% (30)

Проголосовало: 133
ДОРОГОЙ МОЙ МУЖ, Отправляю тебе это письмо по электронной почте, чтобы быть уверенной, что ты его прочтешь. Думаю, ты простишь мне эту небольшую хитрость, но просто я хотела держать тебя в курсе событий за два года, прошедших с того момента, как компьютер вошел в наш дом. С детьми все хорошо. Пете в прошлом месяце исполнилось 8 лет. Учится он хорошо, все считают его красивым и общительным мальчиком. У него, несомненно, есть художественные способности. На прошлой неделе он в школе на уроке рисования изобразил всю семью. У него очень хорошо получились все лица, а особенно реалистично - твой затылок. Ты должен гордиться своим сыном. Леночке в сентябре исполнилось три годика. Она очень похожа на тебя, каким ты был в ее возрасте. Леночка - очень умная девочка. Она даже помнит, что ты провел с нами весь вечер ее дня рождения. Она его с радостью вспоминает, хотя в тот день шел дождь, а ближе к вечеру отключили свет. Со мной тоже все в порядке. В прошлом году я перекрасилась в блондинку и сейчас я думаю, что этот цвет волос мне очень даже идет. Коля (я имею в виду Николая Ивановича - менеджера по персоналу) стал очень интересоваться моей карьерой. А потом он стал моим очень близким другом. Я поняла, что заниматься домашними делами не так уж и сложно. Сначала, когда я подметала пол веником, ты чихал от пыли, но сейчас я делаю это пылесосом, который тебе совершенно не мешает. В доме теперь чистота и уют. Прошлой весной мы переклеили обои, за исключением той части комнаты, где ты поставил свой компьютер, там мы не стали обои переклеивать (не хотели тебе мешать). На этом я заканчиваю письмо, так как мне пора идти: Коля, то есть Николай Иванович, пригласил всех нас на горнолыжный курорт, и мне нужно собирать чемоданы. На время нашего отъезда я наняла домработницу. Она будет готовить тебе кофе и приносить тебе еду прямо за компьютер. Думаю, что вы хорошо проведете время с компьютером, пока мы будем отсутствовать. Петенька, Леночка и я будем думать о тебе. Постарайся и ты подумать о нас, хотя бы во время перезагрузки компьютера.
Обнимаю. Твоя Маша.
Рейтинг: 7/10 (3)
Посмотреть все анекдоты