Почему C++ STL не предоставляет никаких «древовидных» контейнеров?

Опубликовано: 18 Февраля, 2023

Что такое STL в С++?

The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions. It is a library of container classes, algorithms, functions and iterators. 

Это обобщенная библиотека, поэтому ее компоненты параметризованы. Знание классов шаблонов является необходимым условием для работы с STL. STL состоит из 4 компонентов:

  • Алгоритмы
  • Контейнеры
  • Функции
  • Итераторы

Контейнеры: Контейнеры — это объекты, которые обрабатывают набор других объектов или элементов последовательно или иерархически, реализуя четко определенные структуры данных.

Примеры: вектор, набор, очередь, стек, список, карта и т. д.

Примечание. Ознакомьтесь с этой статьей, чтобы узнать больше о STL и контейнерах.

Почему в STL нет контейнера «дерево»:

Во-первых, мы должны посмотреть, для чего нужно дерево:

  • Пользователи хотят хранить данные иерархически или
  • Пользователь хочет данные в определенном порядке.

Для обоих этих случаев у нас уже есть контейнеры

set, multiset и unordered_set:

  • Набор и мультимножество хранят элементы в упорядоченном порядке, оба являются динамическими контейнерами. Множество и мультимножество внутренне построены с использованием концепции бинарного дерева поиска. Он вставляет и удаляет элементы данных за время O(log N ) и не сохраняет повторяющиеся значения.
  • Если вы хотите хранить повторяющиеся значения, вы можете использовать мультимножество, а если вы не хотите, чтобы они были в каком-либо конкретном порядке, вы можете использовать unordered_set, который вставляет и удаляет элементы данных за время O (1) .

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

map, multimap и unordered_map:

  • Динамические контейнеры, такие как map, multimap и unordered_map хранят данные в виде пары ключ-значение. Если ключ должен быть уникальным, вы можете использовать карту или unordered_map и
  • В мультикарте несколько элементов могут иметь одинаковые ключи. Пара ключ-значение может использоваться для хранения родительской и дочерней связи.

Одним из самых больших преимуществ этих контейнеров является то, что они являются универсальными классами, поэтому их можно настраивать. unordered_map хранит данные в случайном порядке за время O(1) , а map и multimap хранят данные в упорядоченном порядке за время O(log N) .

Now according to our needs, we can use any of these containers to have the same characteristics as that of a tree.

Статьи по Теме:

  • Стандартная библиотека шаблонов C++ (STL)
  • Multimap в стандартной библиотеке шаблонов C++ (STL)
  • Список в стандартной библиотеке шаблонов C++ (STL)
  • Мультинабор в стандартной библиотеке шаблонов C++ (STL)
  • Карта в стандартной библиотеке шаблонов C++ (STL)