STL-контейнеры - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему STL-контейнеры. Доклад-сообщение содержит 31 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Тест с отчетом 3 Варианты ответа: - возникнет ошибка времени выполнения - in A::A() in A::operator=(A) - in A::operator=(A) - in A::A() - возникнет ошибка компиляции

Слайд 2

Описание слайда:

STL – основные понятия В основе библиотеки STL лежат шесть понятий: контейнеры, итераторы, алгоритмы, объекты_функции, адаптеры, распределители (памяти).

Слайд 3

Описание слайда:

STL – основные понятия - пояснения В контейнерах хранятся объекты. Итератор – это не зависящая от структуры данных абстракция, позволяющая получать доступ к элементам контейнера и обходить диапазоны элементов. В алгоритмах итераторы применяются для обобщенного манипулирования диапазонами элементов, ничего не зная о типах самих элементов и структурах данных, в которых они размещаются. С помощью объектов_функций определяются обобщенные операции, применяемые к элементам, которыми манипулируют алгоритмы. Адаптеры позволяют согласовать между собой несопоставимые типы путем изменения их интерфейсов. Различают адаптеры класса (они адаптируют сами типы) и адаптеры экземпляра (они адаптируют экземпляры типов). Распределители абстрагируют операции распределения памяти и конструирования объектов, выполняемые контейнерами.

Слайд 4

Описание слайда:

STL – контейнеры (Sgi) Согласно реализации STL фирмы Silicon Graphics определено следующее множество контейнерных классов:

Слайд 5

Описание слайда:

STL – итераторы Модель итератора построена по образцу указателей в C/C++. В общем случае к итератору можно применять операции инкремента, разыменования и сравнения. К некоторым итераторам применимы также операции декремента и указательная арифметика. Категория итератора определяется набором осмысленных операций, которые можно к нему применить. В настоящее время в стандартной библиотеке определено пять категорий итераторов: итератор ввода (input – InIter), итератор вывода (output – OutIter), однонаправленный итератор (forward – ForIter), двунаправленный итератор (bidirectional – BiIter), итератор с произвольным доступом (random access – RandIter).

Слайд 6

Описание слайда:

STL – алгоритмы В STL алгоритмы – это обобщенные шаблоны функций, которые применяются к диапазонам, определяемым итераторами, и выполняют некоторые операции над самими диапазонами или над хранящимися в них элементами. Например, алгоритм std::distance() не разыменовывает переданные ему итераторы, а просто вычисляет число элементов в представленном с их помощью диапазоне. Напротив, алгоритм std::transform() присваивает элементам из одного диапазона преобразованные значения элементов из другого диапазона. std::vector v1 = . . . ; std::vector v2(v1.size()); std::transform(v1.begin(), v1.end(), v2.begin(), ::abs);

Слайд 7

Описание слайда:

STL – объекты_функции Любой класс, перегружающий оператор вызова функции (то есть operator()), является классом функтора. Объекты, созданные на основе таких классов, называются объектами функций, или функторами. Как правило, в STL объекты функций могут свободно заменяться «обычными» функциями, поэтому под термином «объекты функций» часто объединяются как функции C++, так и функторы. Можно сказать, что объектом_функцией, или функтором называется объект, который можно вызывать. Объекты_функции используются прежде всего в сочетании с алгоритмами, где встречаются в виде предикатов или функций. Предикат принимает один или несколько аргументов и возвращает булевское значение, позволяя тем самым управлять выбором элементом из диапазона. Функция принимает нуль или более аргументов и возвращает значение, которое можно использовать для трансформации или присваивания элементам.

Слайд 8

Описание слайда:

STL – контейнерные адаптеры Помимо основных контейнерных классов стандартная библиотека С++ содержит специальные контейнерные адаптеры, предназначенные для особых целей. В их реализации применяются основные контейнерные классы. Ниже перечислены стандартные контейнерные адаптеры, определенные в библиотеке. Стеки – контейнеры, элементы которых обрабатываются по принципу LIFO (последним прибыл, первым обслужен). Очереди – контейнеры, элементы которых обрабатываются по принципу FIFO (первым прибыл, первым обслужен). Иначе говоря, очередь представляет собой обычный буфер. Приоритетные очереди - контейнеры, элементам которых назначаются приоритеты. Приоритет определяется на основании критерия сортировки, переданного программистом (по умолчанию используется оператор

Слайд 9

Описание слайда:

STL – итераторные адаптеры Стандартная библиотека С++ содержит несколько готовых специализиро-ванных итераторов, называемых итераторными адаптерами. Итераторные адаптеры являются не обычными вспомогательными классами; они наделяют саму концепцию итераторов рядом новых возможностей. Выделяют три разновидности итераторных адаптеров: итераторы вставки; back_inserter (контейнер) – элементы присоединяются с конца в прежнем порядке с использованием функции push_back() front_inserter (контейнер) – элементы вставляются в начало в обратном порядке с использованием функции push_front() inserter (контейнер, позиция) – элементы вставляются в заданной позиции в прежнем порядке с использованием функции insert() потоковые итераторы; istream_iterator и оstream_iterator обратные итераторы. Эти итераторы работают в противоположном направлении: вызов оператора ++ на внутреннем уровне преобразуется в вызов оператора --, и наоборот. Все контейнеры поддерживают создание обратных итераторов функциями rbegin() и rend().

Слайд 10

Описание слайда:

STL – распределители (памяти) Концепция распределителя описывает требования к типам, предоставляющим сервисы по управлению памятью. При этом подразумевается, что в типе определены некоторые члены, а также методы для выделения и освобождения неформатированной памяти и конструирования (по месту) и уничтожения объектов того типа, который задан в параметре распределителя. По существу распределитель абстрагирует детали работы с памятью, вынося их из контейнера (и других компонентов, манипулирующих памятью) в отдельный четко определенный интерфейс, за счет чего компоненты можно специализировать такими сервисами управления памятью, которые необходимы для решения конкретной задачи.

Слайд 11

Описание слайда:

Использование контейнеров По сравнению с массивами контейнеры обладают большей гибкостью и функциональностью. Главное – это освобождение программиста от проблем захвата и корректного освобождения памяти. Они динамически увеличивают (а иногда и уменьшают) свои размеры, самостоятельно управляют памятью, следят за количеством хранящихся объектов, ограничивают алгоритмическую сложность поддерживаемых операций и обладают массой других достоинств. Использование контейнеров STL сразу открывает широкие возможности по использованию готовых алгоритмов и функций STL. Популярность контейнеров STL легко объяснима — просто они превосходят своих конкурентов, будь то контейнеры из других библиотек или самостоятельные реализации.

Слайд 12

Описание слайда:

Классификации контейнеров по способу распределения памяти В блоковых контейнерах (также называемых контейнерами со смежной памятью) элементы хранятся в одном или нескольких динамически выделяемых блоках памяти, по несколько элементов в каждом блоке. При вставке нового или удалении существующего элемента другие элементы того же блока сдвигаются вверх или вниз, освобождая место для нового элемента или заполняя место, ранее занимаемое удаленным элементом. Подобные перемещения влияют как на скорость работы, так и на безопасность. К числу стандартных блоковых контейнеров относятся vector, string и deque. Нестандартный контейнер rope также является блоковым. В узловых контейнерах каждый динамически выделенный фрагмент содержит ровно один элемент. Операции удаления и вставки выполняются только с указателями на узлы, не затрагивая содержимого самих узлов, и потому обходятся без перемещений данных в памяти. К этой категории относятся контейнеры связанных списков (такие как list и slist), а также все стандартные ассоциативные контейнеры, обычно реализуемые в форме сбалансированных деревьев. Реализация нестандартных хэшированных контейнеров тоже построена на узловом принципе.

Слайд 13

Описание слайда:

Контейнер vector Это простейший последовательный контейнер. Его прототип: template class vector Здесь Type – тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator. Конструкторы: vector(); – конструктор, создающий пустой вектор vector(size_type n); – конструктор, создающий вектор из n элементов vector(size_type n, const T& t); – конструктор, создающий вектор из n элементов, содержащих значение t vector(const vector&); – конструктор копирования template vector (InIterBegin, InIterEnd); – конструктор, создающий вектор по диапазону

Слайд 14

Описание слайда:

Контейнер vector – члены функции

Слайд 15

Описание слайда:

Контейнер vector – переопределенные типы

Слайд 16

Описание слайда:

Контейнер vector – пример #include #include using namespace std; int main( ) { vector vi; vector ::iterator It; int buf=0; // Добавление элементов while(cout buf, buf!=0) vi.push_back(buf); cout

Слайд 17

Описание слайда:

Контейнер vector – пример «ручное управление» памятью #include #include using namespace std ; typedef vector INTVECTOR; int main() { INTVECTOR V; cout

Слайд 18

Описание слайда:

Контейнер deque (двусторонняя очередь) Это еще один последовательный контейнер. Его прототип: template class deque Здесь Type – тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator. Конструкторы: deque(); – конструктор, создающий пустую очередь deque(size_type n); – конструктор, создающий очередь из n элементов deque(size_type n, const T& t); – конструктор, создающий очередь из n элементов, содержащих значение t deque(const deque&); – конструктор копирования template deque(InIterBegin, InIterEnd); – конструктор, создающий очередь по диапазону

Слайд 19

Описание слайда:

Контейнер deque – члены класса Все переопределяемые типы те же, что и у вектора: allocator_type, const_iterator, const_pointer, const_reference, const_reverse_iterator, difference_type, iterator, pointer, reference, reverse_iterator, size_type, value_type

Слайд 20

Описание слайда:

Контейнер deque - как она устроена? Кажется, что поскольку предполагается вставка элементов с обоих концов очереди, то выгодно использовать в качестве основы просто список. Но в STL используется другая схема реализации очереди, позволяющая обеспечить доступ к ее элементам за постоянное время.

Слайд 21

Описание слайда:

Контейнер deque – пример #include #include using namespace std; int main( ) { deque vi; deque ::iterator It; int buf=0; // Добавление элементов while(cout buf, buf!=0) vi.push_back(buf); cout

Слайд 22

Описание слайда:

Контейнер list Это еще один последовательный контейнер. Его прототип: template class list Здесь Type – тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator. Конструкторы: list(); – конструктор, создающий пустую очередь list(size_type n); – конструктор, создающий очередь из n элементов list(size_type n, const T& t); – конструктор, создающий очередь из n элементов, содержащих значение t list(const list&); – конструктор копирования template list(InIterBegin, InIterEnd); – конструктор, создающий очередь по диапазону

Слайд 23

Описание слайда:

Контейнер list – члены класса Все переопределяемые типы те же, что и у вектора: allocator_type, const_iterator, const_pointer, const_reference, const_reverse_iterator, difference_type, iterator, pointer, reference, reverse_iterator, size_type, value_type

Слайд 24

Описание слайда:

Контейнер list – пример #include #include using namespace std; int main( ) { list vi; list ::iterator It; int buf=0; // Добавление элементов while(cout buf, buf!=0) vi.push_back(buf); cout

Слайд 25

Описание слайда:

Контейнер list – функции sort и unique Алгоритм sort из STL не работает со списками. Вместо него включена функция-член класса sort. Функция unique удаляет повторяющиеся последовательные элементы. #include using namespace std; #include void out(char *s, const list &L) { cout

Слайд 26

Описание слайда:

Контейнер list – функции сцепки Функция splice перемещает один или более элементов из одного списка в другой не перераспределяя память. void splice(iterator position, list& x); Если i является допустимым итератором для списка L, то следующая операция вставляет содержимое списка M перед i в L, оставляя M пустым: L.splice(i,M); Внимание! L и M должны обязательно быть разными! void splice(iterator position,list& x, iterator j); Если i является допустимым итератором для списка L, а j – для M, то следующая операция удаляет элемент, на который ссылается j, и вставляет его перед i. Возможно, что L и M – это один и тот же список. L.splice(i,M,j); void splice(iterator position, list& x, iterator f, iterator l); Если i является допустимым итератором для списка L, а [j1,j2] – допустимым диапазоном для M, то следующая операция удаляет элементы этого диапазона и вставляет их перед i. L и M могут быть одним и тем же списком. L.splice(i,M,j1,j2);

Слайд 27

Описание слайда:

Контейнер list – функции сцепки - пример #include using namespace std; #include void main() { list L; list ::iterator i,j1,j2,j; for (int k=1; ks; }

Слайд 28

Описание слайда:

Контейнер list – функция remove Для удаления из списка всех элементов с заданным значением лучше всего использовать функцию-член класса remove. #include using namespace std; #include void out(char *s, const list &L) { cout

Слайд 29

Описание слайда:

Контейнер list – функция merge Для слияния элементов однотипных списков используется функция-член класса merge. #include using namespace std; #include void out(char *s, const list &L) { cout

Слайд 30

Описание слайда:

Контейнер slist Контейнер slist реализует односвязный список, в котором каждый элемент связан со следующим и не связан с предыдущим. Этот контейнер реализован не во всех библиотеках STL, в частности, в Microsoft – версии, представленной в Studio, его нет. Главное отличие этого списка от контейнера list состоит в том, что итераторы list являются двунаправленными (bidirectional) , а итераторы slist – однонаправленными итераторами (forward). С точки зрения эффективности следует заметить, что функции вставки (insert), сцепки (splice) и удаления (erase) выполняются значительно медленнее, поскольку основаны на дополнительном переборе от начала списка перед выполнением собственно операции вставки и удаления. Для ликвидации этого «перекоса» в интерфейс добавлены функции-члены insert_after, splice_after и erase_after , которыми и рекомендуется пользоваться всякий раз вместо общих функций insert, splice и erase. Следует отметить, что в ряде случаев slist превосходит list и по затратам памяти, и по скорости работы.

Слайд 31

$Контейнер slist – пример int main() { slist L; L.push_front(0); L.push_front(1); L.insert_after(L.begin(), 2); copy(L.begin(), L.end(), // The output...$

Описание слайда:

Контейнер slist – пример int main() { slist L; L.push_front(0); L.push_front(1); L.insert_after(L.begin(), 2); copy(L.begin(), L.end(), // The output is 1 2 0 ostream_iterator (cout, " ")); cout

Теги контейнеры

Похожие презентации