Отсутствие древовидных контейнеров в C STL

Стандартная библиотека шаблонов C (STL) не предлагает никаких «деревовидных» контейнеров . Это упущение вызывает вопрос: почему? И какие альтернативы подходят?

Почему в STL нет древовидных контейнеров?

Есть две причины, по которым может потребоваться древовидная структура данных:

1. Иерархическое представление объектов: Моделирование древовидной иерархии объектов в коде с использованием древовидной структуры.

2. Характеристики эффективного доступа: Обеспечение быстрого доступа к элементам на основе отношений упорядочения, аналогично бинарным деревьям поиска.

Альтернативы для древовидных структур

• Библиотека Boost Graph: Для представления произвольных графиков, в том числе иерархических. структуры.

• Упорядоченные ассоциативные контейнеры:

  • std::map и std::multimap: Сопоставляет ключи со значениями, упорядоченными по ключу.
  • std::set и std::multiset: коллекции уникальных элементов, упорядоченных по value.

Эти контейнеры эффективно работают как сбалансированные двоичные деревья, гарантируя эффективное логарифмическое время доступа для вставок, удалений и поиска. Они также предоставляют дополнительные преимущества, такие как:

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

Пример:

Если вы хотите сохранить иерархию сотрудников с генеральным директором в корне и несколькими уровнями подчиненных, можно использовать std::map<:string std::vector>>. Здесь ключами карты будут имена сотрудников, а связанные векторы будут содержать имена их непосредственных подчиненных.

Заключение

Хотя C STL не предоставляет напрямую с древовидными контейнерами, он предлагает подходящие альтернативы как для иерархического представления, так и для эффективных характеристик доступа. Библиотека графов Boost может обрабатывать сложные графовые структуры, а упорядоченные ассоциативные контейнеры обеспечивают древовидный доступ с помощью универсального и хорошо зарекомендовавшего себя интерфейса.