Какова базовая структура данных STL, установленная на C++?

Question

Я хотел бы знать, как набор реализован в C++. Если бы я должен был реализовать свой собственный контейнер с контейнером без использования контейнера, поставляемого в STL, что было бы лучшим способом решить эту задачу?

Я понимаю, что STL-наборы основаны на абстрактной структуре данных двоичного дерева поиска. Итак, какова базовая структура данных? Массив?

Также, как insert() работает для набора? Как набор проверяет, существует ли в нем элемент?

Я читал в wikipedia, что другой способ реализовать набор с хэш-таблицей. Как это будет работать?

Answer 1

Вы могли бы реализовать бинарное дерево поиска по первому определению Node-структуры:

struct Node 
{ 
    void *nodeData; 
    Node *leftChild; 
    Node *rightChild; 
} 

Затем вы можете определить корень дерева с другим Node *rootNode;

Запись на Википедии Binary Search Tree имеет довольно хороший пример того, как реализовать метод вставки, поэтому я также рекомендую проверить это.

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

Answer 2

Как конкретный контейнер реализован на C++ полностью зависит от реализации. Все, что требуется, состоит в том, чтобы результат соответствовал требованиям, изложенным в стандарте, таким как требования к сложности для различных методов, требования к итераторам и т. Д.

Answer 3

Как сказал KTC, как реализован std::set, может отличаться - стандарт C++ просто указывает абстрактный тип данных. Другими словами, в стандарте не указывается, как должен реализовываться контейнер, а какие именно операции он должен поддерживать. Однако большинство реализаций STL, насколько мне известно, используют red-black trees или другие сбалансированные деревья двоичного поиска некоторого вида (например, GNU libstdC++ использует красно-черные деревья).

Хотя теоретически можно реализовать набор как хеш-таблицу и получить более быструю асимптотическую производительность (амортизированная O (длина ключа) по сравнению с O (log n) для поиска и вставки), для чего требуется, чтобы пользователь предоставлял хеш-функцию для независимо от типа, который они хотели сохранить (см. Wikipedia's entry on hash tables, чтобы получить хорошее объяснение того, как они работают). Что касается реализации двоичного дерева поиска, вы бы не захотели использовать массив, как упоминал Рауль, вам нужна какая-то структура данных Node.

Answer 4

Я понимаю, что STL-наборы основаны на абстрактной структуре данных двоичного дерева поиска. Итак, какова основная структура данных? Массив?

Как указывалось другими, оно варьируется. Набор обычно реализуется как дерево (красно-черное дерево, сбалансированное дерево и т. Д.), Хотя могут существовать и другие реализации.

Также, как вставка() работает для набора ?

Это зависит от базовой реализации вашего набора.Если он реализован как двоичное дерево, то Wikipedia имеет выборочную рекурсивную реализацию для функции insert(). Вы можете проверить это.

Как установить, установлен ли элемент в нем?

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

Я прочитал на википедии, что другой способ осуществить комплекс является с хэш таблицы. Как это будет работать?

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