Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Эффективное использование STL. Библиотека программиста - Мейерс С.

Мейерс С. Эффективное использование STL. Библиотека программиста — Спб.: Питер , 2002. — 224 c.
ISBN 5-94723-382-7
Скачать (прямая ссылка): effektivnoeispolzovaniestlbibliote2002.djvu
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 45 46 47 48 49 .. 114 >> Следующая

Ассоциативные
контейнеры
Ассоциативные контейнеры по некоторым характеристикам схожи с
последовательными контейнерами, однако между этими категориями существует
ряд принципиальных различий. Так, содержимое ассоциативных контейнеров
автоматически сортируется; анализ содержимого производится по критерию
эквивалентности, а не равенства; контейнеры set и тар не могут содержать
дубликатов, а контейнеры тар и mul timap обычно игнорируют половину
данных в каждом из содержащихся в них объектов. Да, ассоциативные
контейнеры являются контейнерами, но они определенно выделяются в
самостоятельную категорию.
В этой главе мы рассмотрим основное понятие эквивалентности;
проанализируем важное ограничение, установленное для функций сравнения;
познакомимся с пользовательскими функциями сравнения для ассоциативных
контейнеров указателей; обсудим официальные и практические аспекты
неизменности ключа, а также пути повышения эффективности ассоциативных
контейнеров.
В STL отсутствуют контейнеры на базе хэш-таблиц, поэтому глава
завершается примерами двух распространенных (хотя и нестандартных)
реализаций. Несмотря на отсутствие хэш-таблиц в STL, вам не придется
реализовывать их самостоятельно или обходиться другими контейнерами.
Существует немало готовых качественных реализаций.
Задача сравнения объектов возникает в STL очень часто. Например, если
функция f i nd ищет в интервале первый объект с заданным значением, она
должна уметь сравнивать два объекта и узнавать, совпадают ли их значения.
При попытке включения нового элемента в множество функция set:: insert
должна проверить, не существует ли данное значение в контейнере.
Совет 19. Помните о различиях между равенством и эквивалентностью
84 Глава 3 • Ассоциативные контейнеры
Алгоритм find и функция set::insert являются типичными представителями
семейства функций, проверяющих совпадение двух величин, однако делают это
они по-разному. Для find совпадением считается равенство двух величин,
проверяемое оператором =. Функция set:: insert проверяет отношение
эквивалентности, обычно основанное на операторе <. Таким образом, по
одному определению два объекта могут иметь одинаковые значения, тогда как
по другому определению они будут различаться. Отсюда следует, что для
эффективного использования STL необходимо понимать различия между
равенством и эквивалентностью.
Формальное определение равенства основано на использовании оператора =.
Если результат выражения х=у равен true, значит, х и у имеют одинаковые
значения, а если f al se - разные. В целом определение весьма
прямолинейное, хотя следует помнить о том, что из равенства значений не
следует равенство всех полей данных. Предположим, класс Widget хранит
внутренние данные о времени последнего обращения:
class Widget { public:
private:
TimeStamp lastAccessed;
Для класса Wi dget можно определить оператор ==, игнорирующий значение
этого поля:
bool operator=(const Widgets lhs, const Widgets rhs)
{
// Поле lastAccessed игнорируется
}
В этом случае два объекта Widget будут считаться равными даже в том
случае, если их поля 1 astAccessed содержат разные значения.
Эквивалентность основана на относительном порядке значений объектов в
отсортированном интервале. Проще всего рассматривать ее в контексте
порядка сортировки, являющегося частью любого стандартного ассоциативного
контейнера (то есть set, mul ti set, map и mul ti map). Два объекта x и у
считаются эквивалентными по отношению к порядку сортировки, используемому
ассоциативным контейнером с, если ни один из них не предшествует другому
в порядке сортировки с. На первый взгляд такая формулировка кажется
запутанной, но на практике все просто. Возьмем контейнер set<Widget> s.
Два объекта Widget, wl и w2, имеют эквивалентные значения по отношению к
s, если ни один из них не предшествует другому в порядке сортировки s.
Стандартная функция сравнения для set<Widget> - less<Widget> - по
умолчанию просто вызывает operator< для объектов Widget, поэтому wl и w2
будут иметь значения, эквивалентные по отношению к operator<, если
истинно следующее выражение:
!(wl<w2) // Условие wl < w2 ложно
&& // и
!(w2<wl) // Условие w2 < wl ложно
Совет 19 85
Все вполне логично: два значения эквивалентны (по отношению к некоторому
критерию упорядочения), если ни одно из них не предшествует другому в
соответствии с данным критерием.
В общем случае функцией сравнения для ассоциативного контейнера является
не оператор < или даже 1 ess, а пользовательский предикат (см. совет 39).
Каждый стандартный ассоциативный контейнер предоставляет свой предикат
сортировки через функцию keycomp, поэтому два объекта х и у имеют
эквивалентные значения по отношению к критерию сортировки ассоциативного
контейнера с, если выполняется следующее условие:
!c.key_compO(x.y)&&!c.key_comp()(y,x) // х не предшествует у
// в порядке сортировки с,
// а у не предшествует х
Выражение !c.key_comp()(x,y) выглядит устрашающе, но стоит понять, что
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 45 46 47 48 49 .. 114 >> Следующая