Итераторы и алгоритмы - История изменений

Sergey.kazenyuk: /* Общие алгоритмы */

2012-06-11T02:43:40Z

‎Общие алгоритмы

Oparin.vsevolod: /* Внешние источники */

2011-05-31T10:03:20Z

‎Внешние источники

Oparin.vsevolod: /* Алгоритмы */

2011-05-31T10:02:48Z

‎Алгоритмы

Oparin.vsevolod: переименовал «Сказка об итераторах» в «Итераторы и алгоритмы»

2011-05-29T11:54:03Z

переименовал «Сказка об итераторах» в «Итераторы и алгоритмы»

Oparin.vsevolod: /* Алгоритмы */

2011-05-29T11:52:54Z

‎Алгоритмы

Oparin.vsevolod: /* Немодифицирующие алгоритмы */

2011-05-29T11:47:57Z

‎Немодифицирующие алгоритмы

Oparin.vsevolod: /* Сортировки, кучи и перестановки */

2011-05-29T11:44:30Z

‎Сортировки, кучи и перестановки

Oparin.vsevolod: /* Кучи */

2011-05-29T11:29:52Z

‎Кучи

Oparin.vsevolod: /* Кучи */

2011-05-29T11:27:22Z

‎Кучи

Oparin.vsevolod: /* Кучи */

2011-05-29T11:26:18Z

‎Кучи

@@ Строка 79: / Строка 79: @@
 <tt>swap_ranges(Forward p1, Forward q1, Forward p2)</tt> меняет местами значение каждого элемента последовательности из <tt>[p1, q1)</tt> со значением соответствующего элемента из <tt>[p2, ...)</tt>.
-<tt>min(const T& a, const T&b [, Compare cmp ])</tt> находит минимум двух элементов и возвращает ссылку на минимальный. Может на вход принимать третий аргумент: компоратор, т.е. функций, которой надо сравнивать элементы.
+<tt>min(const T& a, const T&b [, Compare cmp ])</tt> находит минимум двух элементов и возвращает ссылку на минимальный. Может на вход принимать третий аргумент: компаратор, т.е. функций, которой надо сравнивать элементы.
 <tt>max(const T& a, const T&b [, Compare cmp ])</tt> аналогичен минимуму.

← Предыдущая		Версия 10:03, 31 мая 2011
Строка 215:		Строка 215:

	[http://cplusplus.com/reference/algorithm/ Референс по алгоритмам]		[http://cplusplus.com/reference/algorithm/ Референс по алгоритмам]
−	[http://cplusplus.com/reference/~~algorithm~~/ Об итераторах на английском]	+
		+	[http://cplusplus.com/reference/std/iterator/ Об итераторах на английском]

← Предыдущая		Версия 10:02, 31 мая 2011
Строка 210:		Строка 210:

	<tt>partial_sum(Input p1, Input q1, Output res[, BinaryOperation op])</tt> находит частичные суммы последовательности <tt>[p1, q1)</tt> и записывает их в res. Можно задать свою операцию сложения <tt>op</tt>. Возвращает итератор, указывающий на конец <tt>res</tt>.		<tt>partial_sum(Input p1, Input q1, Output res[, BinaryOperation op])</tt> находит частичные суммы последовательности <tt>[p1, q1)</tt> и записывает их в res. Можно задать свою операцию сложения <tt>op</tt>. Возвращает итератор, указывающий на конец <tt>res</tt>.
		+
		+
		+	== Внешние источники ==
		+
		+	[http://cplusplus.com/reference/algorithm/ Референс по алгоритмам]
		+	[http://cplusplus.com/reference/algorithm/ Об итераторах на английском]

@@ Строка 63: / Строка 63: @@
 == Алгоритмы ==
-C++ поддерживает набор функций, позволяющий работать с цепочками элементов (range of elements). Джентльменский набор таких функций объявлен в хедере &lt;algorithm&gt;.
+C++ поддерживает набор функций, позволяющий работать с последовательностями элементов (range of elements). Джентльменский набор таких функций объявлен в хедере &lt;algorithm&gt;.
 Каждый алгоритм может работать только с определенными типами итераторов. Необходимый тип будет указываться в качестве типа аргумента.
 Например, запись <tt>count(Input p, Input q, T value)</tt> означает, что функция <tt>count</tt> принимает на вход итератор типа <tt>Input</tt>.
 Под записью "итератор на элемент" следует понимать "итератор, указывающий на элемент".

@@ Строка 88: / Строка 88: @@
 <tt>count(Input p, Input q, T value)</tt> находит число вхождений элемента <tt>value</tt> в коллекцию <tt>[p, q)</tt>.
-<tt>count_if(Input p, Input q, UPredicate pr)</tt> находит число элементов коллекции <tt>[p, q)</tt>, удовлетворяющий унарному предикату <tt>pr</tt>.
+<tt>count_if(Input p, Input q, UnaryPredicate pred)</tt> находит число элементов коллекции <tt>[p, q)</tt>, удовлетворяющий унарному предикату <tt>pred</tt>.
-<tt>for_each(Input p, Input q, Func f)</tt> вызывает последовательно функцию <tt>f</tt> для каждого элемента коллекции <tt>[p, q)</tt>.
+<tt>for_each(Input p, Input q, Func f)</tt> вызывает последовательно функцию <tt>f</tt> для каждого элемента коллекции <tt>[p, q)</tt>. Возвращает <tt>f</tt>.
-<tt>equal(Input p1, Input q1, Input p2 [, BPredicate pr])</tt> сравнивает две последовательности <tt>[p1, q1)</tt>, <tt>[p2, ?)</tt>. Возвращает <tt>true</tt>, если первая является префиксом второй, т.е. элементы из <tt>[p1, q1)</tt> совпадают с первыми <tt>q1 - p1</tt> элементами <tt>[p2, ?)</tt>. В качестве дополнительного аргумента можно передать бинарный предикат равенства. Если вторая последовательность оказывается короче первой, поведение функции не определено.
+<tt>equal(Input p1, Input q1, Input p2 [, BinaryPredicate pr])</tt> сравнивает две последовательности <tt>[p1, q1)</tt>, <tt>[p2, ?)</tt>. Возвращает <tt>true</tt>, если первая является префиксом второй, т.е. элементы из <tt>[p1, q1)</tt> совпадают с первыми <tt>q1 - p1</tt> элементами <tt>[p2, ?)</tt>. В качестве дополнительного аргумента можно передать бинарный предикат равенства. Если вторая последовательность оказывается короче первой, поведение функции не определено.
 <tt>mismatch(Input p1, Input q1, Input p2[, BPredicate pr])</tt> сравнивает две последовательности <tt>[p1, q1)</tt>, <tt>[p2, ?)</tt>. Возвращает пару итераторов, указывающих на первое различие. Если <tt>[p1, q1)</tt> является префиксом <tt>[p2, ?)</tt>, то <tt>mismatch</tt> возвращает пару <tt>(q1, q2)</tt>, где <tt>q2</tt> является элементов соответствующим <tt>q1</tt> в <tt>[p2, ?)</tt>.
-<tt>lexicographical_compare(Input p1, Input q1, Input p2, Input q2[, Compare cmp])</tt> возвращает меньше ли лексикографически <tt>[p1, q1)</tt> чем <tt>[p2, q2)</tt>. Имеет дополнительный аргумент: компаратор cmp, сравнивающий два элемента последовательностей.
+<tt>lexicographical_compare(Input p1, Input q1, Input p2, Input q2[, Compare cmp])</tt> возвращает меньше ли лексикографически <tt>[p1, q1)</tt> чем <tt>[p2, q2)</tt>. Имеет дополнительный аргумент: компаратор cmp, сравнивающий два элемента последовательностей. Возвращает <tt>bool<tt>.
 <tt>min_element(Forward p1, Forward q1[, Compare cmp])</tt> возвращает итератор, указывающий на минимальный элемент в последовательности <tt>[p1, q1)</tt>. Имеет дополнительный аргумент: компаратор <tt>cmp</tt>.

← Предыдущая	Версия 11:54, 29 мая 2011
(нет различий)

← Предыдущая		Версия 11:44, 29 мая 2011
Строка 197:		Строка 197:

	<tt>sort_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp])</tt> сортирует кучу.		<tt>sort_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp])</tt> сортирует кучу.
		+
		+	=== Алгоритмы для работы с численными последовательностями ===
		+
		+	Функции, описанные ниже, находятся в хедере <tt>numeric</tt>
		+
		+	<tt>accumulate(Input p1, Input q1, T init[, BinaryOperation op])</tt> суммирует последовательно от <tt>p1</tt> к <tt>q1</tt> все элементы последовательности начиная со значения T. Пример: <tt>((1,2,3), 10) -> 16</tt>. Вместо суммы можно передать собственную операцию <tt>op</tt>. Элементы последовательности будут передаваться <tt>op</tt> в качестве второго аргумента.
		+
		+	<tt>adjacent_difference(Input p1, Input q1, Output res[, BinaryOperation op])</tt> записывает в <tt>res</tt> частичные разности <tt>[p1, q1)</tt>. Так если <tt>[p1, q1) = (x0, x1, x2)</tt>, то в <tt>res</tt> будет записано <tt>(x0, x1 - x0, x2 - x1)</tt>. Вместо разности можно передать собственную операцию <tt>op</tt>. Возвращает итератор, указывающий на конец <tt>res</tt>.
		+
		+	<tt>inner_product(Input p1, Input q1, Input p2, T init[, BinaryOperation1 add, BinaryOperation2 mult])</tt> находит сумму попарных произведений элементов последовательностей <tt>[p1, q1)</tt> и <tt>[p2, ...)</tt> плюс начальное значение <tt>init</tt>. Можно задать свои операции сложения и умножения <tt>add</tt> и <tt>mult</tt>.
		+
		+	<tt>partial_sum(Input p1, Input q1, Output res[, BinaryOperation op])</tt> находит частичные суммы последовательности <tt>[p1, q1)</tt> и записывает их в res. Можно задать свою операцию сложения <tt>op</tt>. Возвращает итератор, указывающий на конец <tt>res</tt>.

@@ Строка 188: / Строка 188: @@
 ===== Кучи =====
-Куча здесь используется в смысле структуры данных. Последовательность <tt>[0, n)</tt> --- куча, если для любого <tt>0 &lt;= i &lt; n</tt> верно <tt>a[i] &lt; a[2 * i + 1]</tt> и <tt>a[i] &lt; a[2 * i + 2]</tt>. Более подробно можно посмотреть в Кормене.
+Куча здесь используется в смысле структуры данных. Последовательность <tt>[0, n)</tt> --- куча, если для любого <tt>0 &lt;= i &lt; n</tt> верно <tt>a[i] &lt;= a[2 * i + 1]</tt> и <tt>a[i] &lt;= a[2 * i + 2]</tt>. Более подробно можно посмотреть в Кормене.
 <tt>push_heap(RandomAccess p1, RandomAccess q1[, Comparator cmp])</tt> расширяет кучу <tt>[p1, q1 - 1)</tt> до <tt>[p1, q1)</tt>, добавляя элемент <tt>q1 - 1</tt>. Можно передать свой компаратор.

← Предыдущая		Версия 11:26, 29 мая 2011
Строка 189:		Строка 189:


		+
		+	<tt>push_heap(RandomAccess p1, RandomAccess q1[, Comparator cmp])</tt> расширяет кучу <tt>[p1, q1 - 1)</tt> до <tt>[p1, q1)</tt>, добавляя элемент <tt>q1 - 1</tt>. Можно передать свой компаратор.
		+
		+	<tt>pop_heap(RandomAccess p1, RandomAccess q1[, Comparator cmp])</tt> переставляет кучу <tt>[p1, q1)</tt> так, что первый элемент оказывается на <tt>q1 - 1</tt> позиции, а <tt>[p1, q1 - 1)</tt> снова образует кучу.
		+
		+	<tt>make_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp])</tt> переставляет последовательность <tt>[p1, q1)</tt> так, чтобы она представляла кучу.

	<tt>sort_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp])</tt> сортирует кучу.		<tt>sort_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp])</tt> сортирует кучу.