Какова базовая структура данных набора STL в C++?
Я хотел бы знать, как набор реализован в C++. Если бы я должен был реализовать свой собственный контейнер набора, не используя STL, обеспеченный контейнер, каков был бы лучший способ пойти об этой задаче?
Я понимаю, что наборы STL основаны на структуре абстрактных данных дерева двоичного поиска. Таким образом, какова базовая структура данных? Массив?
Кроме того, как делает insert() работа для набора? Как набор проверяет, существует ли элемент уже в нем?
Я читал на Википедию, что другой способ реализовать набор с хеш-таблицей. Как это работало бы?
4 ответа
Вы можете реализовать двоичное дерево поиска, сначала определив структуру Node:
struct Node
{
void *nodeData;
Node *leftChild;
Node *rightChild;
}
Затем вы можете определить корень дерева с другим Node *rootNode;
В статье Википедии о Двоичном дереве поиска есть довольно хороший пример того, как реализовать метод вставки, поэтому я бы также рекомендовал проверить это.
С точки зрения дубликатов, они, как правило, не допускаются в наборах, поэтому вы можете просто отбросить этот ввод, вызвать исключение и т. Д., В зависимости от вашей спецификации.
Я понимаю, что наборы STL основаны на абстрактной структуре данных двоичного дерева поиска. Итак, какова основная структура данных? Массив?
Как отмечали другие, он варьируется. Набор обычно реализуется как дерево (красно-черное дерево, сбалансированное дерево и т. Д.), Хотя могут существовать и другие реализации.
Кроме того, как insert () работает для набора ?
Это зависит от базовой реализации вашего набора. Если это реализовано как двоичное дерево, Википедия имеет образец рекурсивной реализации для функции insert (). Вы можете проверить это.
Как набор проверяет, существует ли в нем элемент ?
Если он реализован в виде дерева, то он просматривает дерево и проверяет каждый элемент. Однако наборы не позволяют хранить повторяющиеся элементы. Если вам нужен набор, позволяющий дублировать элементы, вам понадобится мультимножество.
Я читал в Википедии, что еще один способ реализовать набор - это использовать хеш-таблицу .Как это будет работать?
Вы можете иметь в виду hash_set, где набор реализован с использованием хеш-таблиц. Вам нужно будет предоставить хеш-функцию, чтобы знать, в каком месте хранить ваш элемент. Эта реализация идеальна, если вы хотите быстро найти элемент. Однако, если важно, чтобы ваши элементы хранились в определенном порядке, тогда реализация дерева более подходящая, поскольку вы можете перемещаться по нему в предварительном порядке, в порядке или после.
Как сказал KTC, способ реализации std::set может быть различным - стандарт C++ просто определяет абстрактный тип данных. Другими словами, стандарт не определяет, как должен быть реализован контейнер, а только какие операции он должен поддерживать. Однако большинство реализаций STL, насколько мне известно, используют красно-черные деревья или другие сбалансированные двоичные деревья поиска того или иного вида (GNU libstdc++, например, использует красно-черные деревья).
Хотя теоретически вы можете реализовать набор в виде хэш-таблицы и получить более высокую асимптотическую производительность (амортизированная O(длина ключа) против O(log n) для поиска и вставки), это потребует от пользователя предоставления хэш-функции для любого типа, который он хочет хранить (см. статью Wikipedia о хэш-таблицах для хорошего объяснения того, как они работают). Что касается реализации двоичного дерева поиска, вы не захотите использовать массив - как упомянул Рауль, вам понадобится какая-то структура данных типа Node.
То, как конкретный контейнер реализован в C ++, полностью зависит от реализации. Все, что требуется, - это соответствие результата требованиям, изложенным в стандарте, таким как требования к сложности для различных методов, требования к итераторам и т. Д.