Руководство по стандартной библиотеке шаблонов (STL) - [9]
Сложности выражений зависят от последовательностей.
Таблица 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);
> void pop_back();
> void erase(iterator position);
> void erase(iterator first, iterator last);
>};
>template ‹class T, class Allocator›
>bool operator==(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);
>template ‹class T, class Allocator›
>bool operator‹(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);
iterator - это итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.
const_iterator - это постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
Конструктор template ‹class InputIterator› vector(InputIterator first, InputIterator last) делает только N вызовов конструктора копирования T (где N - расстояние между first и last) и никаких перераспределений, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Он делает, самое большее, 2N вызовов конструктора копирования T и logN перераспределений, если они - только итераторы ввода, так как невозможно определить расстояние между first и last и затем сделать копирование.
![Изучаем Java EE 7](/storage/book-covers/e0/e0ee9b7e3e4f168a93df98d7e47d66089eac3652.jpg)
Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)
![Геймдизайн. Рецепты успеха лучших компьютерных игр от Super Mario и Doom до Assassin’s Creed и дальше](/storage/book-covers/d0/d0fc13172d4310c9da7b10ba57a3fcb2e3d9f10d.jpg)
Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.
![Обработка событий в С++](/build/oblozhka.dc6e36b8.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![MFC и OpenGL](/build/oblozhka.dc6e36b8.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![Симуляция частичной специализации](/storage/book-covers/7e/7e33d937f206a76edb7f45006e896cc191605df5.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![Питон — модули, пакеты, классы, экземпляры](/build/oblozhka.dc6e36b8.jpg)
Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.