В этом интерфейсе внимание стоит обратить на использование параметра
HashingInfo
, содержащего функции хэширования и сравнения, а также перечисляемые типы, управляющие минимальным количеством гнезд в таблице и максимальным допустимым
отношением числа элементов контейнера к числу гнезд. В случае превышения пороговой величины количество гнезд в таблице увеличивается, а некоторые элементы в таблице хэшируются заново (в реализации SGI предусмотрены функции, обеспечивающие аналогичные возможности управления количеством гнезд в таблице).
После небольшого форматирования объявление
hash_compare
(значение по умолчанию для
HashingInfo
) выглядит примерно так:
template<typename T ,typename CompareFunction=less<T> >
class hash_compare {
public:
enum {
bucket_size = 4, // Максимальное отношение числа элементов к числу гнезд
min_buckets = 8 // Минимальное количество гнезд
}
size_t operator(const T&) const; // Хэш-функция
bool operator (const T&, const T&) const;
… // Некоторые подробности опущены,
// включая использование CompareFunction
};
Перегрузка
operator
(в данном случае для реализации функций хэширования и сравнения) используется гораздо чаще, чем можно представить. Другое применение этой концепции продемонстрировано в совете 23.
Реализация Dinkumware позволяет программисту написать собственный касс-аналог
hash_compare
(возможно, объявленный производным от
hash_compare
). Если этот класс будет определять
bucket_size
,
min_buckets
, две функции
operator
(с одним и с двумя аргументами) и еще несколько мелочей, не упомянутых выше, он может использоваться для управления конфигурацией и поведением контейнеров Dinkumware
hash_set
и
hash_multiset
. Управление конфигурацией
hash_map
и
hash_multimap
осуществляется аналогичным образом.
Учтите, что в обоих вариантах все принятие решений можно поручить реализации и ограничиться объявлением следующего вида:
hash_set<int> intTable; // Создать хешированное множество int
Чтобы это объявление нормально компилировалось, хэш-таблица должна содержать данные целочисленных типов (например,
int
), поскольку стандартные хэш-функции обычно ограничиваются целочисленными типами (в реализации SGI стандартные хэш-функции обладают более широкими возможностями; о том, где найти дополнительную информацию, рассказано в совете 50).
Принципы внутреннего устройства реализаций SGI и Dinkumware очень сильно различаются. В реализации SGI использована традиционная схема открытого хэширования с массивом указателей на односвязные списки элементов. В реализации Dinkumware
используется двусвязный список. Различие достаточно принципиальное, поскольку оно влияет на категории итераторов, поддерживаемых этими реализациями. Хэшированные контейнеры SGI поддерживают прямые итераторы, что исключает возможность обратного перебора; в них отсутствуют такие функции, как
rbegin
или
rend
. Реализация Dinkumware поддерживает двусторонние итераторы, что позволяет осуществлять перебор как в прямом, так и в обратном направлении. С другой стороны, реализация SGI чуть экономнее расходует память.
Какая из этих реализаций лучше подходит для ваших целей? Понятия не имею. Только вы можете ответить на этот вопрос, однако в этом совете я даже не пытался изложить все необходимое для принятия обоснованного решения. Речь идет о другом — вы должны знать, что несмотря на отсутствие хэшированных контейнеров непосредственно в STL, при необходимости можно легко найти STL-совместимые хэшированные контейнеры (с разными интерфейсами, возможностями и особенностями работы). Более того, в свободно распространяемых реализациях SGI и STLport вам за них даже не придется платить.
Итераторы
На первый взгляд итераторы представляются предметом весьма простым. Но стоит присмотреться повнимательнее, и вы заметите, что стандартные контейнеры STL поддерживают четыре разных типа итераторов:
iterator, const_iterator, reverse_iterator
и
const_reverse_iterator
. Проходит совсем немного времени, и выясняется, что в некоторых формах insert и erase только один из этих четырех типов принимается контейнером. И здесь начинаются вопросы. Зачем нужны четыре типа итераторов? Существует ли между ними какая-либо связь? Можно ли преобразовать итератор от одного типа к другому? Можно ли смешивать разные типы итераторов при вызове алгоритмов и вспомогательных функций STL? Как эти типы связаны с контейнерами и их функциями?
В настоящей главе вы найдете ответы на эти вопросы, а также поближе познакомитесь с разновидностью итераторов, которой обычно не уделяют должного внимания:
istreambuf_iterator
. Если вам нравится STL, но не устраивает быстродействие
istream_iterator
при чтении символьных потоков, возможно,
istreambuf_iterator
поможет справиться с затруднениями.
Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator
Как известно, каждый стандартный контейнер поддерживает четыре типа итераторов. Для контейнера
container<T>
тип
iterator
работает как
T*
тогда как
const_iterator
работает как
const T*
(также встречается запись
T const*
). При увеличении
iterator
или
const_iterator
происходит переход к следующему элементу контейнера в прямом порядке перебора (от начала к концу контейнера). Итераторы
reverse_iterator
и
const_reverse_iterator
также работают как
T*
и
const T*
соответственно, но при увеличении эти итераторы переходят к следующему элементу в обратном порядке перебора (от конца к началу).