Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
- Название:РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
- Автор:
- Жанр:
- Издательство:МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
- Год:1999
- ISBN:нет данных
- Рейтинг:
- Избранное:Добавить в избранное
-
Ваша оценка:
Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL) краткое содержание
РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL) - читать онлайн бесплатно полную версию (весь текст целиком)
Шрифт:
Интервал:
Закладка:
Итератор j называется доступным ( reachable ) из итератора i, если и только если имеется конечная последовательность применений operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i==j).
Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) - пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.
Все категории итераторов требуют только те функции, которые осуществимы для данной категории со сложностью постоянного времени (амортизированные). Поэтому таблицы требований для итераторов не имеют столбца сложности.
В следующих разделах мы принимаем: a и b - значения X, n - значение типа расстояния Distance, u, tmp и m - идентификаторы, r и s - леводопустимые (lvalues) значения X, t - значение значимого типа T.
Итераторы ввода (Input iterators)
Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T, если справедливы следующие выражения:
Таблица 2. Требования итератора ввода
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после |
|---|---|---|---|
| X(a) | - | - | X(a) - копия a. примечание: предполагается деструктор. |
| X u(a); X u = a; | - | - | после: u - копия a. |
| u = a | X& | - | после: u - копия a. |
| a == b | обратимый в bool | - | если a - копия b, тогда a == b возвращает true. == - это отношение эквивалентности в области действия ==. |
| a!= b | обратимый в bool | !(a == b) | - |
| *a | обратимый в T | - | до: a - разыменовываемое. если a - копия b, то *a эквивалентно *b. |
| ++r | X& | - | до: r - разыменовываемое. после: r - разыменовываемое или r - законечное. |
| void r++ | void | void ++r | - |
| *r++ | Т | {X tmp = r; ++r; return tmp;} | - |
ПРИМЕЧАНИЕ.Для итераторов ввода нет никаких требований на тип или значение r++ кроме требования, чтобы *r++ работал соответственным образом. В частности, r == s не подразумевает, что ++r == ++s. (Равенство не гарантирует свойство замены или ссылочной прозрачности.) Что касается ++r, то нет больше никаких требований на значения любых копий r за исключением того, что они могут быть безопасно уничтожены или присвоены. После выполнения ++r не требуется, чтобы были копии (предыдущего) r в области ==. Алгоритмы с итераторами ввода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными ( single pass ) алгоритмами. Не требуется, чтобы значимый тип T был леводопустимым типом (lvalue type) . Эти алгоритмы могут использоваться с входными потоками как источниками входных данных через класс istream_iterator.
Итераторы вывода (Output iterators)
Класс или встроенный тип X удовлетворяет требованиям итератора вывода, если справедливы следующие выражения:
Таблица 3. Требования итератора вывода
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после |
|---|---|---|---|
| X(a) | - | - | *a = t эквивалентно *X(a) = t. примечание: предполагается деструктор. |
| X u(a); X u = a; | - | - | - |
| *a = t | результат не используется | - | - |
| ++r | X& | - | - |
| r++ | Х или Х& | - | - |
ПРИМЕЧАНИЕ.Единственное допустимое использование operator* - на левой стороне выражения присваивания. Присваивание через то же самое значение итератора происходит только однажды . Алгоритмы с итераторами вывода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными ( single pass ) алгоритмами. Равенство и неравенство не обязательно определены. Алгоритмы, которые берут итераторы вывода, могут использоваться с выходными потоками для помещения в них данных через класс ostream_iterator, также как с итераторами вставки и вставляющими указателями. В частности, следующие два условия должны соблюдаться: во-первых, через любое значение итератора должно выполняться присваивание до его увеличения (то есть, для итератора вывода i недопустима последовательность кода i++; i++;); во-вторых, любое значение итератора вывода может иметь только одну активную копию в любое данное время (например, недопустима последовательность кода i = j; *++i = a; *j = b;).
Последовательные итераторы (Forward iterators)
Класс или встроенный тип X удовлетворяет требованиям последовательного итератора, если справедливы следующие выражения:
Таблица 4. Требования последовательного итератора
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после |
|---|---|---|---|
| X u; | - | - | примечание: u может иметь исключительное значение. примечание: предполагается деструктор. |
| X() | - | - | примечание: X() может быть исключительным. |
| X(a); | - | - | a == X(a) |
| X u(a); X u = a; | - | X u; u = a; | после: u == a. |
| a == b | обратимый в bool | - | == - это отношение эквивалентности. |
| a!= b | обратимый в bool | !(a == b) | - |
| r = a | X& | - | после: r == a. |
| *a | обратимый в T | - | до: a - разыменовываемое. a==b подразумевает *a==*b. Если X - модифицируемый, то *a = t - допустимо. |
| ++r | X& | - | до: r - разыменовываемое. после: r - разыменовываемое или r - законечное. r == s и r - разыменовываемое подразумевает ++r==++s. &r==&++r. |
| r++ | X | {X tmp = r; ++ r; return tmp;} | - |
ПРИМЕЧАНИЕ.Тот факт, что r == s подразумевает ++r == ++s (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.
Двунаправленные итераторы (Bidirectional iterators)
Класс или встроенный тип X удовлетворяет требованиям двунаправленного итератора, если к таблице, которая определяет последовательные итераторы, мы добавим следующие строки:
Таблица 5. Требования двунаправленного итератора (в дополнение к последовательному итератору)
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после |
|---|---|---|---|
| --r | X& | - | до: существует s такое, что r==++s. после: s - разыменовываемое. --(++r)==r. --r==--s подразумевает r==s.&r==&--r. |
| r-- | X | {X tmp = r; - -r; return tmp;} | - |
ПРИМЕЧАНИЕ.Двунаправленные итераторы позволяют алгоритмам перемещать итераторы назад так же, как вперёд.
Шрифт:
Интервал:
Закладка:
