ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Category:

C++: ключ во множестве STL

Зачем были придуманы ассоциативные контейнеры (множества, отображения и так далее)? Как я понимаю, чтобы уменьшить время поиска элемента данных в структуре данных по сравнению с последовательными контейнерами (массив, вектор, список, очередь и так далее).

За счет чего достигается уменьшение времени поиска? За счет того, что ассоциативные контейнеры построены на принципах древовидных структур данных. В последовательном контейнере (если он не отсортирован) придется проверить все элементы контейнера, чтобы убедиться, что заданный для поиска элемент отсутствует в этом контейнере. А в ассоциативном контейнере для этого придется проверить только часть элементов. Зато в последовательный контейнер (в его конец) можно легко и быстро вставить новый элемент. А чтобы вставить новый элемент в ассоциативный контейнер, нужно сначала найти подходящее для него место (не нарушающее заданный порядок сортировки) и только потом вставлять. Впрочем, все эти задачи выполняются в недрах библиотеки STL, а программисту достаточно понимать возможности, достоинства и недостатки каждого из контейнеров, а не его внутреннее устройство.

Поиск в ассоциативных контейнерах производится по ключу. Во множествах ключом является сам элемент, а в отображениях элемент представляет собой пару, состоящую из ключа элемента и значения элемента.

Если с отображением всё понятно, то со множеством мне стало понятно не сразу. Если множество состоит из элементов какого-то базового типа (int, double, char и так далее), то тоже всё понятно. Но рассмотрим множество из элементов какого-то пользовательского типа (класса). Например, множество объектов класса person, в котором, к примеру, есть три поля: фамилия, имя и телефон. Это один из примеров из учебника Лафоре.

Может ли ключом быть не весь объект, а одно поле этого объекта или совокупность двух полей из трех этого объекта? В учебнике Лафоре мельком сказано, что это возможно, однако, прямо о том, как это сделать, не рассказывается, а просто показано в примерах, но автор нигде на этом моменте не фиксируется. Цитата, стр. 724:

Давайте поговорим о поиске. Он производится с помощью ключей, обычно представляющих собой одно численное или строковое значение, которое может быть как атрибутом объекта в контейнере, так и самим объектом.


Внутреннее устройство множества требует, чтобы при его определении был задан порядок сортировки элементов в нем (по умолчанию — по возрастанию). Именно то, что элементы множества постоянно находятся в отсортированном состоянии, ускоряет поиск в нём, о чем говорилось в начале поста. Чтобы сортировка по возрастанию работала, над элементами множества (в нашем примере — объектами класса person) нужно проводить как минимум операцию «меньше» (см. предыдущий пост), а это значит, что эта операция должна быть доступна. Для этого необходима ее перегрузка (переопределение), чтобы она смогла работать с объектами класса person.

И вот как раз при перегрузке этой операции можно определить, что из себя будет представлять ключ. Можно посмотреть, как это сделано в примере setpers из учебника Лафоре, стр. 732. Онлайн этот пример можно посмотреть тут.

Цитата:
bool operator< (const person& p1, const person& p2)
{
    if(p1.lastName == p2.lastName)
        return (p1.firstName < p2.firstName) ? true : false;
    return (p1.lastName < p2.lastName) ? true : false;
}

То есть в данном случае ключом объекта класса person из трех полей (фамилия, имя, телефон) является совокупность двух полей — фамилии (lastName) и имени (firstName). То есть, к примеру, следующие объекты класса person (или в данном случае эти наборы полей можно назвать кортежами)

1) Пушкин, Александр, 123-4567
2) Пушкин, Александр, 295-8790

будут считаться равными (несмотря на то, что у них разные телефоны) и во множество можно включить только один из них, потому что множество в STL по определению не может содержать одинаковые элементы (в отличие от мультимножества).

Чтобы сделать ключом объекта класса person из трех полей (фамилия, имя, телефон) только одно поле, например, фамилию, перепишем процитированную выше функцию:
bool operator< (const person& p1, const person& p2)
{
    return (p1.lastName < p2.lastName) ? true : false;
}

Теперь следующие объекты класса person

1) Пушкин, Александр, 123-4567
2) Пушкин, Лев, 295-8790

тоже будут считаться одинаковыми (несмотря на то, что у них разные имена и телефоны) и во множество STL можно будет включить только один из них.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments