Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Примитивы, определённые в библиотеке
Чтобы упростить задачу определения iterator_category, value_type и distance_type для определяемых пользователем итераторов, библиотека обеспечивает следующие предопределённые классы и функции:
| // iterator tags (теги итераторов) struct input_iterator_tag {};struct output_iterator_tag {};struct forward_iterator_tag {};struct bidirectional_iterator_tag {};struct random_access_iterator_tag {}; // iterator bases (базовые классы итераторов) template <class T, class Distance = ptrdiff_t> struct input_iterator {};struct output_iterator {};// output_iterator не шаблон, потому что у итераторов вывода// не определены ни значимый тип, ни тип расстояния.template <class T, class Distance = ptrdiff_t> struct forward_iterator {};template <class T, class Distance = ptrdiff_t> struct bidirectional_iterator {};template <class T, class Distance = ptrdiff_t> struct random_access_iterator {}; // iterator_category (функции категорий итераторов) template <class T, class Distance>inline input_iterator_tagiterator_category(const input_iterator<T, Distance>&) { return input_iterator_tag();} inline output_iterator_tag iterator_category(const output_iterator&) { return output_iterator_tag();}template <class T, class Distance>inline forward_iterator_tagiterator_category(const forward_iterator<T, Distance>&) { return forward_iterator_tag();}template <class T, class Distance>inline bidirectional_iterator_tagiterator_category(const bidirectional_iterator<T, Distance>&) { return bidirectional_iterator_tag();)template <class T, class Distance>inline random_access_iterator_tagiterator_category(const random_access_iterator<T, Distance>&) { return random_access_iterator_tag();}template <class T>inline random_access_iterator_tag iterator_category(const T*) { return random_access_iterator_tag();} // value_type of iterator (функции значимого типа итераторов) template <class T, class Distance>inline T* value_type(const input_iterator<T, Distance>&) (return (T*) (0);}template <class T, class Distance>inline T* value_type(const forward_iterator<T, Distance>&) { return (T*) (0);}template <class T, class Distance>inline T* value_type(const bidirectional_iterator<T, Distance>&) { return (T*) (0);}template <class T, class Distance>inline T* value_type(const random_access_iterator<T, Distance>&) { return (T*) (0);}template <class T>inline T* value_type(const T*) { return (T*) (0); } // distance_type of iterator (функции типа расстояния итераторов) template <class T, class Distance>inline Distance* distance_type(const input_iterator<T, Distance>&) { return (Distance*) (0);}template <class T, class Distance>inline Distance* distance_type(const forward_iterator<T, Distance>&) { return (Distance*) (0);}template <class T, class Distance>inline Distance* distance_type(const bidirectional_iterator<T, Distance>&) { return (Distance*) (0);}template <class T, class Distance>inline Distance* distance_type(const random_access_iterator<T, Distance>&) { return (Distance*) (0);} template <class T>inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*) (0); } |
Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей double, и такой, чтобы работал с большой (large) моделью памяти компьютера, то это может быть сделано таким определением:
| class MyIterator: public bidirectional_iterator <double, long> {// код, осуществляющий ++, и т.д.}; |
Тогда нет необходимости определять iterator_category, value_type, и distance_type в MyIterator.
Операции с итераторами (Iterator operations)
Так как только итераторы произвольного доступа обеспечивают + и - операторы, библиотека предоставляет две шаблонные функции advance и distance. Эти функции используют + и - для итераторов произвольного доступа (и имеют, поэтому, сложность постоянного времени для них); для итераторов ввода, последовательных и двунаправленных итераторов функции используют ++, чтобы обеспечить реализацию со сложностью линейного времени. advance берет отрицательный параметр n только для итераторов произвольного доступа и двунаправленных итераторов. advance увеличивает (или уменьшает для отрицательного n) итераторную ссылку i на n. distance увеличивает n на число единиц, сколько требуется, чтобы дойти от first до last.
| template <class InputIterator, class Distance>inline void advance(InputIterator& i, Distance n); template <class InputIterator, class Distance>inline void distance(InputIterator first, InputIterator last, Distance& n); |
distance должна быть функцией 3-х параметров, сохраняющей результат в ссылке вместо возвращения результата, потому что тип расстояния не может быть выведен из встроенных итераторных типов, таких как int*.
Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.
В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.
| Таблица 1. Требования контейнеров | ||||
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после | сложность |
| X::value_type | Т | время компиляции | ||
| X::reference | время компиляции | |||
| X::const_refe rence | время компиляции | |||
| X::pointer | тип указателя, указывающий на X::reference | указатель на T в модели памяти, используемой контейнером | время компиляции | |
| X::iterator | тип итратора, указывающий на X::reference | итератор любой категории, кроме итератора вывода. | время компиляции | |
| X::const_iter ator | тип итератора, указывающий на X:: const_reference | постоянный итератор любой категории, кроме итератора вывода. | время компиляции | |
| X::difference _type | знаковый целочисленный тип | идентичен типу расстояния X::iterator и X::const_iterator | время компиляции | |
| X::size_type | беззнаковый целочисленный тип | size_type может представлять любое неотрицательное значение difference_type | время компиляции | |
| X u; | после: u.size() == 0. | постоянная | ||
| X() | X().size() == 0. | постоянная | ||
| X(a) | a == X(a). | линейная | ||
| X u(a); X u == a; | X u; u = a; | после: u == a. | линейная | |
| (&a)->~X() | результат не используется | после: a.size() == 0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается. | линейная | |
| a.begin() | iterator; const_iterator для постоянного a | постоянная | ||
| a.end() | iterator; const_iterator для постоянного a | постоянная | ||
| a == b | обратимый в bool | a.size() == b.size() && equal(a.begin(), a.end(), b.begin()) | == - это отношение эквивалентности. примечание: eqial определяется в разделе алгоритмов. | линейная |
| a!= b | обратимый в bool | !(a == b) | линейная | |
| r = a | X& | if(&r!= &a) { (&r)-> X::~X(); new (&r) X(a); return r; } | после: r == a. | линейнaя |
| a.size() | size_type | size_type n = 0; distance (a.begin(), a.end(), n); return n; | постоянная | |
| a.max_size() | size_type | size() самого большого возможного контейнера. | постоянная | |
| a.empty() | обратимый в bool | a.size() == 0 | постоянная | |
| a < b | обратимый в bool | lexicographical _compare (a.begin(), a.end(), b.begin(), b.end()) | до: < определён для значений T. < - отношение полного упорядочения. lexicographical _compare определяется в разделе алгоритмов. | линейная |
| a > b | обратимый в bool | b < a | линейнaя | |
| a <= b | обратимый в bool | !(a > b) | линейная | |
| a >= b | обратимый в bool | !(a < b) | линейная | |
| a.swap(b) | void | swap(a, b) | постоянная |
Функция-член size() возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.
begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является законечным.
Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:
| Таблица 2. Требования обратимых контейнеров (в дополнение к контейнерам) | |||
| выражение | возвращаемый тип | семантика исполнения | сложность |
| X::reverse _iterator | reverse_iterator<iterator, value_type, reference, difference_type> для итератора произвольного доступа. reverse_bidirectional_iterator< iterator, value_type, reference, difference_type> для двунаправленного итератора | время компиляции | |
| X::const_r everse_ite rator | reverse_iterator<const_iterator, value_type, const_reference, difference_type> для итератора произвольного доступа. reverse_bidirectional_iterator< const_iterator, value_type, const_reference, difference_type> для двунаправленного итератора. | время компиляции | |
| a.rbegin() | reverse_iterator; const_reverse_iter ator для постоянного a | reverse_iterator(end()) | постоянная |
| a.rend() | reverse_iterator; const_reverse_iter ator для постоянного a | reverse_iterator(begin()) | постоянная |
Последовательности (Sequences)
Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).
В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [ql, q2) - допустимый диапазон в a, t - значение X::value_type.
Сложности выражений зависят от последовательностей.
| Таблица 3. Требования последовательностей (в дополнение к контейнерам) | ||
| выражение | возвращаемый тип | утверждение/примечание состояние до/после |
| 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 для последовательностей должны быть, по крайней мере, из категории последовательных итераторов.
| Таблица 4. Необязательные операции последовательностей | |||
| выражение | возвращаемый тип | семантика исполнения | контейнер |
| 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 и затем сделать копирование.
Функция-член capasity (ёмкость) возвращает размер распределённой памяти в векторе. Функция-член reserve - директива, которая сообщает vector(вектору) запланированноe изменение размера, так чтобы он мог соответственно управлять распределением памяти. Это не изменяет размер последовательности и занимает, самое большее, линейное время от размера последовательности. Перераспределение в этом случае происходит тогда и только тогда, когда текущая ёмкость меньше, чем параметр reserve. После reserve ёмкость (capasity) больше или равна параметру reserve, если происходит перераспределение; а иначе равна предыдущему значению capasity. Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Гарантируется, что нет никакого перераспределения во время вставок, которые происходят после того, как reserve выполняется, до времени, когда размер вектора достигает размера, указанного reserve.
insert (вставка) вызывает перераспределение, если новый размер больше, чем старая ёмкость. Если никакого перераспределения не происходит, все итераторы и ссылки перед точкой вставки остаются справедливыми. Вставка единственного элемента в вектор линейна относительно расстояния от точки вставки до конца вектора. Амортизированная сложность во время жизни вектора, вставляющего единственный элемент в свой конец, постоянна. Вставка множественных элементов в вектор с единственным вызовом вставляющей функции-члена линейна относительно суммы числа элементов плюс расстояние до конца вектора. Другими словами, намного быстрее вставить много элементов в середину вектора сразу, чем делать вставку по одному элементу. Шаблонная вставляющая функция-член предраспределяет достаточно памяти для вставки, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Иначе функция вставляет элементы один за другим и не должна использоваться для вставки в середину векторов.
erase (стирание) делает недействительными все итераторы и ссылки после пункта стирания. Деструктор T вызывается столько раз, каково число стёртых элементов, а оператор присваивания T вызывается столько раз, каково число элементов в векторе после стёртых элементов.
Чтобы оптимизировать распределение места, даётся определение для bool.
| class vector<bool, allocator> { public: // битовая ссылка (bit reference): class reference { public: ~reference(); operator bool() const; reference& operator=(const bool x); void flip(); // инвертирует бит (flips the bit) }; // определения типов (typedefs): typedef bool const_reference; typedef iterator; typedef const_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef bool value_type; typedef reverse_iterator; typedef const_reverse_iterator; // размещение/освобождение (allocation/deallocation): vector(); vector(size_type n, const bool& value = bool()); vector(const vector<bool, allocator>& x); template <class InputIterator> vector(InputIterator first, InputIterator last); ~vector(); vector<bool, allocator>& operator=(const vector<bool, allocator>& x); void reserve(size_type n); void swap(vector<bool, 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 bool& x); iterator insert(iterator position, const bool& x = bool()); void insert(iterator position, size_type n, const bool& 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);}; void swap(vector<bool, allocator>::reference x, vector<bool, allocator>::reference y); bool operator==(const vector<bool, allocator>& x, const vector<bool, allocator>& y); bool operator<(const vector<bool, allocator>& x, const vector<bool, allocator>& y); |
reference - класс, который имитирует поведение ссылок отдельного бита в vector< bool >.
Ожидается, что каждое исполнение обеспечит определение vector< bool > для всех поддерживаемых моделей памяти.
| Сейчас невозможно шаблонизировать определение. То есть мы не можем написать: template <template <class U> class Allocator == allocator> class vector<bool, Allocator> { /*... */ }; Поэтому обеспечивается только vector<bool, Allocator>. |
Список (List)
list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.
| template <class T, template <class U> class Allocator = allocator>class list {public: // определения типов: 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 Т value_type; typedef reverse_iterator; typedef const_reverse_iterator; // размещение/удаление: list() list(size_type n, const T& value = T()); template <class InputIterator> list(InputIterator first, InputIterator last); list(const list<T, Allocator>& x); ~list(); list<T, Allocator>& operator=(const list<T,Allocator>& x); void swap(list<T, Allocator& x); // средства доступа: 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(); bool empty() const; size_type size() const; size_type max_size() const; reference front(); const_reference front() const; reference back(); const_reference back() const; // вставка/стирание: void push_front(const T& x); 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_front(); void pop_back(); void erase(iterator position); void erase(iterator first, iterator last); // специальные модифицирующие операции cо списком: void splice(iterator position, list<T, Allocator>& x); void splice(iterator position, list<T, Allocator>& x, iterator i); void splice(iterator position, list<T, Allocator>& x, iterator first, iterator last); void remove(const T& value); template <class Predicate> void remove_if(Predicate pred); void unique(); template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); void merge(list<T, Allocator>& x); template <class Compare> void merge(list<T,Allocator>& x, Compare comp); void reverse(); void sort(); template <class Compare> void sort(Compare comp);}; template <class T, class Allocator> bool operator==(const list<T, Allocator>& x, const list<T, Allocator>& y); template <class T, class Allocator>bool operator<(const list<T, Allocator>& x, const list<T, Allocator>& y); |
iterator - двунаправленный итератор, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.
const_iterator - постоянный двунаправленный итератор, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
insert не влияет на действительность итераторов и ссылок. Вставка единственного элемента в список занимает постоянное время, и ровно один раз вызывается конструктор копирования T. Вставка множественных элементов в список зависит линейно от числа вставленных элементов, а число вызовов конструктора копирования T точно равно числу вставленных элементов.
erase делает недействительными только итераторы и ссылки для стёртых элементов. Стирание единственного элемента - операция постоянного времени с единственным вызовом деструктора T. Стирание диапазона в списке занимает линейное время от размера диапазона, а число вызовов деструктора типа T точно равно размеру диапазона.
Так как списки позволяют быструю вставку и стирание в середине списка, то некоторые операции определяются специально для них:
list обеспечивает три операции стыковки, которые разрушительно перемещают элементы из одного списка в другой:
void splice(iterator position, list<T, Allocator>& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x == this.
void splice(iterator position, list<T, Allocator>& x, iterator i) вставляет элемент, указываемый i, из списка x перед position и удаляет элемент из x. Требуется постоянное время. i - допустимый разыменовываемый итератор списка x. Результат не изменяется, если position == i или position == ++i.
void splice(iterator position, list<T, Allocator>& x, iterator first, iterator last) вставляет элементы из диапазона [first, last) перед position и удаляет элементы из x. Требуется постоянное время, если &x == this; иначе требуется линейное время. [first, last) - допустимый диапазон в x. Результат не определён, если position - итератор в диапазоне [first, last).
remove стирает все элементы в списке, указанном итератором списка i, для которого выполняются следующие условия: *i == value, pred(*i) == true. remove устойчиво, то есть относительный порядок элементов, которые не удалены, тот же самый, как их относительный порядок в первоначальном списке. Соответствующий предикат применяется точно size() раз.
unique стирает все, кроме первого элемента, из каждой последовательной группы равных элементов в списке. Соответствующий бинарный предикат применяется точно size() - 1 раз.
merge сливает список аргумента со списком (предполагается, что оба сортированы). Слияние устойчиво, то есть для равных элементов в двух списках элементы списка всегда предшествуют элементам из списка аргумента. x пуст после слияния. Выполняется, самое большее, size() + x.size() - 1 сравнений.
reverse переставляет элементы в списке в обратном порядке. Операция линейного времени.
sort сортирует список согласно operator< или сравнивающему функциональному объекту. Она устойчива, то есть относительный порядок равных элементов сохраняется. Выполняется приблизительно NlogN сравнений, где N равно size().
Двусторонняя очередь (Deque)
deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают линейное время. Как с векторами, управление памятью обрабатывается автоматически.
| template <class T, template <class U> class Allocator = allocator>class deque {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 Т value_type; typedef reverse_iterator; typedef const_revcrse_iterator; // размещение/удаление: deque(); deque(size_type n, const T& value = T()); deque(const deque<T, Allocator>& x); template <class InputIterator> deque(InputIterator first, InputIterator last); ~deque(); deque<T, Allocator>& operator=(const deque<T,Allocator>& x); void swap(deque<T, Allocator>& x); // средства доступа: 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; 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; // вставка/стирание: void push_front(const T& x); 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_front(); void pop_back(); void erase(iterator position); void erase(iterator first, iterator last);}; template <class T, class Allocator>bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y); template <class T, class Allocator>bool operator<(const deque<T, Allocator>& x, const deque<T, Allocator>& y); |
iterator - итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.
const_iterator - постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
difference_type - знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator.
insert (вставка) в середину двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. insert и push (помещение) с обоих концов двусторонней очереди делают недействительными все итераторы двусторонней очереди, но не влияют на действительность всех ссылок на двустороннюю очередь. В худшем случае вставка единственного элемента в двустороннюю очередь занимает линейное время от минимума двух расстояний: от точки вставки - до начала и до конца двусторонней очереди. Вставка единственного элемента либо в начало, либо в конец двусторонней очереди всегда занимает постоянное время и вызывает единственный запрос конструктора копии T. То есть двусторонняя очередь особенно оптимизирована для помещения и извлечения элементов в начале и в конце.
erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.
Date: 2015-12-12; view: 373; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |