Структура данных для тематического списка клиентов

Question

Мне нужна структура данных с O (1) операциями добавления, поиска и удаления для темы, подписанной списком клиентов.

Некоторые функции, которые необходимо поддерживать: isTopicExists, isClientExists, getClientsForTopic, addClientForTopic, removeClientForTopic и getTopicsForClient.

Учитывая имя темы, идентификатор клиента, который мы можем считать уникальным, и указатель клиента, какую структуру данных лучше всего использовать? Какие реализации доступны?

Answer 1

Хеш-карта может показаться неплохой идеей. Его ожидаемая сложность - O (1), но пессимистический сценарий со многими коллизиями может привести вас к O (n) в зависимости от того, как реализовано сцепление. Логарифмический поиск здесь будет трудно победить, поэтому я бы выбрал самобалансирующееся двоичное дерево поиска, даже std :: map (красно-черное дерево в большинстве реализаций STL). Единственный способ сделать его более эффективным - использовать вектор (массив), но только в том случае, если ваши идентификаторы малы или смещены, но расположены близко друг к другу. Вы не можете победить математику здесь.