advertisement

контейнеры STL

29 %
71 %
advertisement
Information about контейнеры STL
Education

Published on February 20, 2014

Author: mcroitor

Source: slideshare.net

Description

Небольшой обзор контейнеров STL и итераторов.
advertisement

КОНТЕЙНЕРЫ STL Михаил Кройтор

Содержание         Итераторы Свойства итераторов Контейнеры Общие свойства контейнеров Последовательные контейнеры Ассоциативные контейнеры Использование контейнеров рекомендации

Обозначения        обозначения Х - некторый класс (контейнер); u, a, b - объекты класса X; r - итератор; T - значимый тип (элементов контейнера); t - значение типа T; n - целочисленное значение.

Итераторы  Итератор - объект, предоставляющий доступ к элементам контейнера и позволяющий их перебирать. ВИДЫ ИТЕРАТОРОВ Итератор вывода Итератор ввода Последовательный итератор Двунаправленный итератор Итератор произв. доступа

Итераторы      Итератор ввода (input iterator) – позволяет получать значения элементов контейнера; Итератор вывода (output iterator) – позволяет изменять значения элементов контейнера; Последовательный итератор (forward iterator) – гарантируют последовательный перебор элементов; Двунаправленный итератор (bidirectional iterator) – позволяют перебирать элементы контейнера как в прямом, так и в обратном порядке; Итератор произвольного доступа (random access iterator) – ;

Свойства итераторов: итераторы ввода Свойство Пояснение X(a) X u(a); X u = a; Конструктор копирования. Предполагается наличие деструктора a = b; Оператор копирования. a==b; a != b; Операторы сравнения *a; Оператор разыменования. Возвращается ссылка на объект из контейнера. ++r; r++; Последовательный перебор итераторов NB: Итераторы ввода не гарантируют, что если a == b, то a++ == b++

Свойства итераторов: итераторы вывода Свойство Пояснение X(a) X u(a); X u = a; Конструктор копирования. Предполагается наличие деструктора *a = t; Оператор разыменования. Возвращается ссылка на объект из контейнера. ++r; r++; Последовательный перебор итераторов

Свойства итераторов: последовательные итераторы Свойство Пояснение Обладает всеми свойствами итераторов ввода и вывода a==b; a != b; Операторы сравнения. a == b => ++a == ++b

Свойства итераторов: двунаправленные итераторы Свойство Пояснение Обладает всеми свойствами последовательных итераторов --r; r--; Последовательный перебор итераторов

Свойства итераторов: итераторы произвольного доступа Свойство Пояснение Обладает всеми свойствами двунаправленных итераторов r += n; r –= n; Сдвиг на n элементов от итератора r r + n; n + r; r – n; Сдвиг на n элементов от итератора а b – a; Расстояние между итераторами a[n] Последовательный перебор итераторов a > b; a < b; a ≥ b; a ≤ b; Операторы упорядочения.

Контейнеры    под контейнером понимают объект, содержащий другие (обычно однотипные) объекты. Доступ к элементом контейнера осуществляется через итераторы. Контейнеры С++ представляют собой шаблонные классы с общим базовым интерфейсом.

Конетйнеры Последовательные    Список (list) Очередь (deque) Вектор (vector) Ассоциативные     Множество (set) Хеш-массив (map) Множество с повторами (multiset) Хеш-массив с повторами (multimap)

Контейнеры: структура выражение значение X::value_type Равен типу T X::reference Равен типу T& X::iterator тип итератора, указывает на X::reference X::const_iterator Константный итератор X() Конструктор по умолчанию X(a) Конструктор копирования a.begin() Возвращает Iterator; const_iterator для постоянного a a.end() Возвращает Iterator; const_iterator для постоянного a a.size() Возвращает размер контейнера a.empty() Проверяет, если контейнер пустой … …

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

Последовательные контейнеры: дополнительные свойства выражение семантика контейнер a.front() *a.begin() vector, list, deque a.back() *(--a. end()) vector, list, deque a.push_front(t) a.insert(a.begin(), t) list, deque a.push_back(t) a.insert(a.end(), t) vector, list, deque a.pop_front() a.erase(a.begin()) list, deque a.pop_back() a.erase(-- a.end()) vector, list, deque a[n] *(a.begin() + n) vector, deque

Ассоциативные контейнеры: общие свойства свойство пояснение X::key_type Тип ключа X::value_type Тип значения X::key_compare Тип функции сравнения ключей (функтор) X(i, j), X(i, j, c) Создание контейнера и заполнение его значениями из [i, j). c – объект сравнения a.insert(t) a.insert(i, j) a.insert(p, t) Вставка элемента (полуотрезка) a.erase(k); a.erase(q); Удаление элемента по ключу или итератору. a.find(k) Поиск значения по ключу a.count(k) Подсчет элементов с ключом, равным к … …

Использование контейнеров

Рекомендации: выбор контейнера Критерий Рекомендация Возможность вставки нового элемента на произвольную позицию контейнера Если нужна, выбирайте последовательный контейнер; ассоциативные контейнеры не подходят. Структура памяти контейнера должна соответствовать правилам языка C Только vector критична скорость поиска Рассмотрите сортированные векторы и ассоциативные контейнеры Критична скорость доступа Список не подходит ... ...

Рекомендации: использование STL       Не пытайтесь писать контейнерно-независимый код; Реализуйте быстрое и корректное копирование объектов в контейнерах; Старайтесь не использовать итераторы повторно; Используйте алгоритмы вместо циклов Всегда включайте нужные заголовки Научитесь читать сообщения компилятора

Add a comment

Related presentations

Related pages

Контейнеры STL: Liste. Teil 4 | PureCodeCpp

Для "массивов", wobei der aktive Zugabe von geplanten, löschen und verschieben Elemente, библиотека STL предлагает ...
Read more

Контейнеры STL. Teil 2 | PureCodeCpp

STL вводит ряд понятий и структур данных, dass in fast allen Fällen erlauben erheblich vereinfachen Code. Вводятся ...
Read more

STL Containers - C++ Reference - cplusplus.com - The C++ ...

Containers replicate structures very commonly used in programming: dynamic arrays , queues , stacks , heaps (priority_queue), linked lists , trees ...
Read more

STL: ассоциативные контейнеры и итераторы

stl:ассоциативныеконтейнерыиитераторы stl: ассоциативные контейнеры и итераторы
Read more

Стандартная библиотека шаблонов stl stl (Standard Template ...

Стандартная библиотека шаблонов STL. STL (Standard Template Library) является частью стандарта C++.
Read more

ОСНОВЫ C++ STL - MSU

stl . Указатели и ... stl Итераторы Контейнеры
Read more

Standard Template Library (STL) - SGI

Standard Template Library Programmer's Guide. Introduction to the STL: How to use this site: Table of Contents: Download the STL: Index: Index by Category:
Read more

Java collections framework - Wikipedia

... and ObjectSpace Generic Collection Library (JGL), whose main goal was consistency with the C++ Standard Template Library (STL). ...
Read more

Основы C++ - Лекция № 15 - Standard Template Library ...

Основы C++ - Лекция № 15 - Standard Template Library Последовательные контейнеры
Read more

Контейнеры STL - msdn.microsoft.com

Стандартная библиотека предоставляет различные типобезопасные контейнеры для ...
Read more