Чтение онлайн

на главную - закладки

Жанры

РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Менг Ли

Шрифт:

Последовательности (Sequences)

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).

В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q -

разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type.

Сложности выражений зависят от последовательностей.

Таблица 10. Требования последовательностей (в дополнение к контейнерам)

выражение возвращаемый тип утверждение/примечание состояние до/после
X(n, t) X a(n, t); после: size==n. создаёт последовательность с n копиями t.
X(i, j) X a(i, j); после: size==расстоянию между i и j. создаёт последовательность, равную диапазону [i, j).
a.insert(p, t) iterator вставляет копию t перед p. возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t) результат не используется вставляет n копий t перед p.
a.insert(p, i, j) результат не используется вставляет копии элементов из диапазона [i, j) перед p.
a.erase(q) результат не используется удаляет элемент, указываемый q.
a.erase(ql, q2) результат не используется удаляет элементы в диапазоне [ql, q2). 

vector (вектор), list (список) и deque (двусторонняя очередь) выдвигают программисту различные предложения сложности и должны использоваться соответственно. vectоr - тип последовательности, которая используется по умолчанию. list нужно использовать, когда имеются частые вставки и удаления из середины последовательности, deque - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

Типы iterator и const_iterator для последовательностей должны быть, по крайней мере, из категории последовательных итераторов.

Таблица 11. Необязательные операции последовательностей

выражение возвращаемый тип семантика исполнения контейнер
a.front reference; const_reference для постоянного a *a.begin vector, list, deque
a.back reference; const_reference для постоянного a *a.(--end) vector, list, deque
a.push_front(t) void a.insert(a.begin, t) list, deque
a.push_back(t) void a.insert(a.end, t) vector, list, deque
a.pop_front void a.erase(a.begin) list, deque
a.pop_back void a.erase(--a.end) vector, list, deque
a[n] reference; const_reference
для постоянного a
*(a.begin + n) vector, deque

Все операции в расположенной выше таблице обеспечиваются только для контейнеров, для которых они занимают постоянное время.

Вектор (Vector)

vector - вид последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает операции вставки и удаления в конце с постоянным (амортизированным) временем; вставка и удаление в середине занимают линейное время. Управление памятью обрабатывается автоматически, хотя для улучшения эффективности можно давать подсказки.

template ‹class T, template ‹class U› class Allocator = allocator›

class vector {

public:

 // определения типов (typedefs):

 typedef iterator;

 typedef const_iterator;

 typedef Allocator‹T›::pointer pointer;

 typedef Allocator‹T›::reference reference;

 typedef Allocator‹T›::const_reference const_reference;

 typedef size_type;

 typedef difference_type;

 typedef T value_type;

 typedef reverse_iterator;

 typedef const_reverse_iterator;

 // размещение/освобождение (allocation/deallocation):

 vector;

 vector(size_type n, const T& value = T);

 vector(const vector‹T, Allocator›& x);

 template ‹class InputIterator›

 vector(InputIterator first, InputIterator last);

 ~vector;

 vector‹T, Allocator›& operator=(const vector‹T, Allocator›& x);

 void reserve(size_type n);

 void swap(vector‹T, Allocator›& x);

 // средства доступа (accessors):

 iterator begin;

 const_iterator begin const;

 iterator end;

 const_iterator end const;

 reverse_iterator rbegin;

 const_reverse_iterator rbegin;

 reverse_iterator rend;

 const_reverse_iterator rend;

 size_type size const;

 size_type max_size const;

 size_type capacity const;

 bool empty const;

 reference operator[](size_type n);

 const_reference operator[](size_type n) const;

 reference front;

 const_reference front const;

 reference back;

 const_reference back const;

 // вставка/стирание (insert/irase):

 void push_back(const T& x);

 iterator insert(iterator position, const T& x = T);

 void insert(iterator position, size_type n, const T& x);

 template ‹class InputIterator›

 void insert(iterator position, InputIterator first, InputIterator last);

Поделиться:
Популярные книги

Мастер 10

Чащин Валерий
10. Мастер
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Мастер 10

Черный Маг Императора 5

Герда Александр
5. Черный маг императора
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Черный Маг Императора 5

Проводник

Кораблев Родион
2. Другая сторона
Фантастика:
боевая фантастика
рпг
7.41
рейтинг книги
Проводник

Возвращение демонического мастера. Книга 6

Агафонов Антон Романович
6. Вселенная Вечности
Фантастика:
фэнтези
5.00
рейтинг книги
Возвращение демонического мастера. Книга 6

Отмороженный 11.0

Гарцевич Евгений Александрович
11. Отмороженный
Фантастика:
боевая фантастика
рпг
попаданцы
фантастика: прочее
фэнтези
5.00
рейтинг книги
Отмороженный 11.0

Лорд Системы

Токсик Саша
1. Лорд Системы
Фантастика:
фэнтези
попаданцы
рпг
4.00
рейтинг книги
Лорд Системы

Неправильный солдат Забабашкин

Арх Максим
1. Неправильный солдат Забабашкин
Фантастика:
попаданцы
альтернативная история
5.62
рейтинг книги
Неправильный солдат Забабашкин

Газлайтер. Том 16

Володин Григорий Григорьевич
16. История Телепата
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Газлайтер. Том 16

Мл. сержант. Назад в СССР. Книга 3

Гаусс Максим
3. Второй шанс
Фантастика:
альтернативная история
6.40
рейтинг книги
Мл. сержант. Назад в СССР. Книга 3

Бестужев. Служба Государевой Безопасности. Книга 5

Измайлов Сергей
5. Граф Бестужев
Фантастика:
городское фэнтези
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Бестужев. Служба Государевой Безопасности. Книга 5

Господин следователь. Книга 2

Шалашов Евгений Васильевич
2. Господин следователь
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Господин следователь. Книга 2

На границе империй. Том 9. Часть 3

INDIGO
16. Фортуна дама переменчивая
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 9. Часть 3

Разбуди меня

Рам Янка
7. Серьёзные мальчики в форме
Любовные романы:
современные любовные романы
остросюжетные любовные романы
5.00
рейтинг книги
Разбуди меня

Вечная Война. Книга II

Винокуров Юрий
2. Вечная война.
Фантастика:
юмористическая фантастика
космическая фантастика
8.37
рейтинг книги
Вечная Война. Книга II