Почему C++ STL не предоставляет никаких «древовидных» контейнеров?
Что такое 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)