Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Ассоциативные контейнерные классы





Программирование на языке C

Лабораторная работа 10

Программа на языке C++. Использование библиотеки STL. Множества и списки.

Цель: Изучить принципы использования библиотеки шаблонов STL (Standard Template Library) на языке C++. Научится разрабатывать программы, используя классы множеств и списков.

Основные теоретические сведения

Ассоциативные контейнерные классы

Ассоциативные контейнеры (Associative containers) обеспечивают быстрый поиск данных, основанных на ключах и представляются следующими классами:

  • Множество (set)
  • Множество с дубликатами (multiset)
  • Словарь (map)
  • Словарь с дубликатами (multimap)

Все они берут в качестве параметров Key (ключ) и упорядочивающее отношение Compare, которое вызывает полное упорядочение по элементам Key. Кроме того, map и multimap ассоциируют произвольный тип T с Key. Объект типа Compare называется сравнивающим объектом (comparison object) контейнера.

В этом разделе, когда мы говорим о равенстве ключей, мы подразумеваем отношение эквивалентности, обусловленное сравнением и не (not) operator== для ключей. То есть считается, что два ключа k1 и k2 являются равными, если для сравнивающего объекта comp истинно comp(k1, k2) == false && comp(k2, k1) == false.

Ассоциативный контейнер поддерживает уникальные ключи (unique keys), если он может содержать, самое большее, один элемент для каждого значения ключа. Иначе он поддерживает равные ключи (equal keys). set и map поддерживают уникальные ключи. multiset и multimap поддерживают равные ключи.

Для set и multiset значимый тип - тот же самый, что и тип ключа. Для map и multimap он равен pair<const Key, T >.

iterator ассоциативного контейнера относится к категории двунаправленного итератора. insert не влияет на действительность итераторов и ссылок контейнера, а erase делает недействительными только итераторы и ссылки на стёртые элементы.

В следующей таблице обозначается: X - класс ассоциативного контейнера, a - значение X, a_uniq - значение X, когда X поддерживает уникальные ключи, a a_eq - значение X, когда X поддерживает многократные ключи, i и j удовлетворяют требованиям итераторов ввода и указывают на элементы value_type, [ i, j) - допустимый диапазон, p - допустимый итератор для a, q - разыменовываемый итератор для a, [ q1, q2) - допустимый диапазон в a, t - значение X::value_type и k - значение X::key_type.

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

выражение возвращаемый тип утверждение/примечание состояние до/после сложность
       
X::key_type Key . время компиляции
X::key_compare Compare по умолчанию less<key_type>. время компиляции
X::value_compare тип бинарного предиката то же, что key_compare для set и multiset; отношение упорядочения пар, вызванное первым компонентом (т.е. Key), для map и multimap. время компиляции
X(c) X a(c); . создает пустой контейнер; использует с как объект сравнения. постоянная
X() X a; . создает пустой контейнер; использует Compare() как объект сравнения. постоянная
X(i,j,c) X a(i,j,c); . cоздает пустой контейнер и вставляет в него элементы из диапазона [i, j); использует с как объект сравнения. вообще NlogN (N - расстояние от i до j); линейная, если [i, j) отсортирован value_comp()
X(i,j) X a(i,j); . то же, что выше, но использует Compare() как объект сравнения. то же, что выше
a.key_comp() X::key_compare возвращает объект сравнения, из которого а был создан. постоянная
a.value_comp() X::value_compare возвращает объект value_compare, созданный из объекта сравнения. постоянная
a_uniq.insert(t) pair<iterator, bool> вставляет t, если и только если в контейнере нет элемента с ключом, равным ключу t. Компонент bool возвращенной пары показывает, происходит ли вставка, а компонент пары iterator указывает на элемент с ключом, равным ключу t. логарифмическая
a_eq.insert(t) iterator вставляет t и возвращает итератор, указывающий на вновь вставленный элемент. логарифмическая
a.insert(p, t) iterator вставляет t, если и только если в контейнерах с уникальными ключами нет элемента с ключом, равным ключу t; всегда вставляет t в контейнеры с дубликатами. всегда возвращает итератор, указывающий на элемент с ключом, равным ключу t. итератор p - подсказка, указывающая, где вставка должна начать поиск. вообще логарифмическая, но сводится к постоянной, если t вставлен прямо перед p.
a.insert(i, j) результат не используется вставляет в контейнер элементы из диапазона [i, j); вообще Nlog(size()+N) (N - расстояние от i до j); линейная, если [i, j) отсортирован согласно value_comp()
a.erase(k) size_type стирает все элементы в контейнере с ключом, равным k. возвращает число уничтоженных элементов. log(size()) + count(k)
a.erase(q) результат не используется стирает элемент, указанный q. сводится к постоянной
a.erase(ql, q2) результат не используется стирает все элементы в диапазоне [ql, q2). log(size())+ N, где N - расстояние от ql до q2.
a.find(k) iterator; const_iterator для константы a возвращает итератор, указывающий на элемент с ключом, равным k, или a.end(), если такой элемент не найден. логарифмическая
a.count(k) size_type возвращает число элементов с ключом, равным k. log(size()) + count(k)
a.lower_bound(k) iterator; const_iterator для константы a возвращает итератор, указывающий на первый элемент с ключом не меньше, чем k. логарифмическая
a.upper_bound(k) iterator; const_iterator для константы a возвращает итератор, указывающий на первый элемент с ключом больше, чем k. логарифмическая
a.equal_range(k) pair<iterator, itеrator>; pair<const_iter ator, const_iterator> для константы a эквивалент make_pair(lower_boud(k), upper_bound (k)). логарифмическая

 

Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов i и j таких, что расстояние от i до j является положительным, value_comp (*j, *i) == false. Для ассоциативных контейнеров с уникальными ключами выдерживается более сильное условие value_comp (*i, *j) == true.

 

Date: 2015-12-12; view: 381; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию