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

Question

[yar_s]

Здравствуйте, мне дали задание реализовать класс для работы с множествами, т.е. set тут не поможет, все самостоятельно. Основные операции трудностей не вызывают, но я вот никак не могу остановиться на какой-нибудь одной определённой структуре данных. Не знаю подойдет ли идея с битовым вектором? Использовать массив как-то слишком банально и не очень эффективно.
Какие вы посоветуете использовать структуры данных?

Answer 1

[Сергей Протько]

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

Comments

[yar_s]

Спасибо за совет! А vector имеет какие-либо преимущества в данной задаче?

[Сергей Протько]

Нет, у вас узким местом в задаче является поиск элементов при вставке, что бы обеспечить уникальность значения. Для бинарных деревьев операция поиска дешевле, нежели для векторов.