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

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

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

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

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

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

Мейерс С. Эффективное использование STL. Библиотека программиста — Спб.: Питер , 2002. — 224 c.
ISBN 5-94723-382-7
Скачать (прямая ссылка): effektivnoeispolzovaniestlbibliote2002.djvu
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 114 >> Следующая

class hash_контейнер;
Полученное объявление весьма близко к объявлению хэшированных контейнеров
в реализации SGI. Главное различие между ними заключается в том, что в
реализации SGI для типов HashFunction и CompareFunction предусмотрены
значения по умолчанию. Объявление hash_set в реализации SGI выглядит
следующим образом (слегка исправлено для удобства чтения):
templare<typename Т,
typename HashFunction = hash<T>, typename CompareFunction = equal_to<T>,
typename Allocator = allocator<T> >
class hash_set;
В реализации SGI следует обратить внимание на использование equal to в
качестве функции сравнения по умолчанию. В этом она отличается от
стандартных ассоциативных контейнеров, где по умолчанию используется
функция сравнения
1 ess. Смысл этого изменения не сводится к простой замене функции.
Хэшированные контейнеры SGI сравнивают два объекта, проверяя ихравенство,
а неэквивалентность (см. совет 19). Для хэшированных контейнеров такое
решение вполне разумно, поскольку в хэшированных ассоциативных
контейнерах, в отличие от их стандартных аналогов (обычно построенных на
базе деревьев), элементы не хранятся в отсортированном порядке.
Совет 25 109
В реализации Dinkumware принят несколько иной подход. Она также позволяет
задать тип объектов, хэш-функцию, функцию сравнения и распределитель, но
хэш-функция и функция сравнения по умолчанию перемещены в отдельный класс
hashcompare, который передается по умолчанию в параметре Hashinglnfo
шаблона контейнера.
Например, объявление hash_set (также отформатированное для наглядности) в
реализации Dinkumware выглядит следующим образом:
tempiate<typename T.typename CompareFunction> class hash_compare;
tempiate<typename T.
typename Hashinglnfo = hash_compare<T,less<T".
typename Allocator = allocator<T>> class hash_set;
В этом интерфейсе внимание стоит обратить на использование параметра
Hashinglnfo, содержащего функции хэширования и сравнения, а также
перечисляемые типы, управляющие минимальным количеством гнезд в таблице и
максимальным допустимым отношением числа элементов контейнера к числу
гнезд. В случае превышения пороговой величины количество гнезд в таблице
увеличивается, а некоторые элементы в таблице хэшируются заново (в
реализации SGI предусмотрены функции, обеспечивающие аналогичные
возможности управления количеством гнезд в таблице).
После небольшого форматирования объявление hash compare (значение по
умолчанию для Hashinglnfo) выглядит примерно так:
tempiate<typename T.typename CompareFunction=less<T>>
class hash_compare{
public:
enum{
bucket_size = 4. // Максимальное отношение числа элементов к числу гнезд
min_buckets = 8 // Минимальное количество гнезд
}
size_t operator()(const Т&) const: // Хзш-функция
bool operator()(const Т&,
const Т&) const;
// Некоторые подробности опущены.
// включая использование CompareFunction
}:
Перегрузка operator () (в данном случае для реализации функций
хэширования и сравнения) используется гораздо чаще, чем можно
представить. Другое применение этой концепции продемонстрировано в совете
23.
Реализация Dinkumware позволяет программисту написать собственный класс-
аналог hash_compare (возможно, объявленный производным от hash compare).
Если этот класс будет определять bucketsize, min buckets, две функции
operatorO (с одним и с двумя аргументами) и еще несколько мелочей, не
упомянутых выше, он может использоваться для управления конфигурацией и
поведением контейнеров Dinkumware hash_set и hashjnul ti set. Управление
конфигурацией hashjnap и hash_ multi map осуществляется аналогичным
образом.
110 Глава 3 • Ассоциативные контейнеры
Учтите, что в обоих вариантах все принятие решений можно поручить
реализации и ограничиться объявлением следующего вида:
hash_set<int> intTable; // Создать хэшированное множество int
Чтобы это объявление нормально компилировалось, хэш-таблица должна
содержать данные целочисленных типов (например, int), поскольку
стандартные хэш-функции обычно ограничиваются целочисленными типами (в
реализации SGI стандартные хэш-функции обладают более широкими
возможностями; о том, где найти дополнительную информацию, рассказано в
совете 50).
Принципы внутреннего устройства реализаций SGI и Dinkumware очень сильно
различаются. В реализации SGI использована традиционная схема открытого
хэширования с массивом указателей на односвязные списки элементов. В
реализации Dinkumware используется двусвязный список. Различие достаточно
принципиальное, поскольку оно влияет на категории итераторов,
поддерживаемых этими реализациями. Хэшированные контейнеры SGI
поддерживают прямые итераторы, что исключает возможность обратного
перебора; в них отсутствуют такие функции, как rbegi п или rend.
Реализация Dinkumware поддерживает двусторонние итераторы, что позволяет
осуществлять перебор как в прямом, так и в обратном направлении. С другой
стороны, реализация SGI чуть экономнее расходует память.
Какая из этих реализаций лучше подходит для ваших целей? Понятия не имею.
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 114 >> Следующая