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

Вы можете реализовать двоичное дерево поиска, сначала определив структуру Node:

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

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

В статье Википедии о двоичном дереве поиска есть довольно хороший пример того, как реализовать метод вставки, поэтому Я также рекомендую это проверить.

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

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

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

Пошаговая отладка с исходным кодом g++ 6.4 stdlibc ++

Знаете ли вы, что в пакете g++-6 по умолчанию Ubuntu 16.04 или GCC 6.4 build from source вы можете перейти в библиотеку C ++ без дополнительной настройки?

Делая это, мы легко делаем вывод, что в этой реализации используется красно-черное дерево.

Это имеет смысл, поскольку std::set можно обходить по порядку, что было бы неэффективно, если бы использовалась хэш-карта.

main.cpp

#include <cassert>
#include <set>

int main() {
    std::set<int> s;
    s.insert(1);
    s.insert(2);
    assert(s.find(1) != s.end());
    assert(s.find(2) != s.end());
    assert(s.find(3) == s3.end());
}

Компиляция и отладка:

g++ -g -std=c++11 -O0 -o main.out main.cpp
gdb -ex 'start' -q --args main.out

Теперь, если вы войдете в s.insert(1), вы сразу дойдете до /usr/include/c++/6/bits/stl_set.h:

487 #if __cplusplus >= 201103L
488       std::pair<iterator, bool>
489       insert(value_type&& __x)
490       {
491     std::pair<typename _Rep_type::iterator, bool> __p =
492       _M_t._M_insert_unique(std::move(__x));
493     return std::pair<iterator, bool>(__p.first, __p.second);
494       }
495 #endif

который явно пересылается на _M_t._M_insert_unique.

Итак, мы открываем исходный файл в vim и находим определение _M_t:

      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
           key_compare, _Key_alloc_type> _Rep_type;
       _Rep_type _M_t;  // Red-black tree representing set.

Итак, _M_t относится к типу _Rep_type, а _Rep_type - к _Rb_tree.

Хорошо, теперь для меня достаточно доказательств. Если вы не верите, что _Rb_tree является черно-красным деревом, сделайте шаг вперед и прочтите алгоритм.

unordered_set использует хеш-таблицу

Та же процедура, но замените set на unordered_set в коде.

Это имеет смысл, поскольку std::unordered_set не может быть пройден по порядку, поэтому стандартная библиотека выбрала хэш-карту вместо красно-черного дерева, поскольку хеш-карта имеет лучшую амортизированную временную сложность вставки.

Переход в insert приводит к /usr/include/c++/6/bits/unordered_set.h:

415       std::pair<iterator, bool>
416       insert(value_type&& __x)
417       { return _M_h.insert(std::move(__x)); }

Итак, мы открываем исходный файл в vim и ищем _M_h:

      typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

Итак, хеш-таблица.

std::map и std::unordered_map

Аналогично std::set vs std:unordered_set: Какая структура данных находится внутри std :: map в C ++?

Тактико-технические характеристики

Вы также можете определить используемую структуру данных, рассчитав их:

Процедура создания графика и анализ кучи и BST и по адресу: Куча против двоичного дерева поиска (BST)

Мы ясно видим:

• std::set, логарифмическое время вставки

• std::unordered_set, более сложный шаблон хэш-карты:

  • on the non-zoomed plot, we clearly see the backing dynamic array doubling on huge one off linearly increasing spikes

  • на увеличенном графике мы видим, что время в основном постоянное и приближается к 250 нс, поэтому намного быстрее, чем std::map, за исключением очень маленьких размеров карты

    Отчетливо видны несколько полос, и их наклон становится меньше, когда массив удваивается.

    Я считаю, что это происходит из-за среднего линейно возрастающего обхода связанного списка в каждой корзине. Затем, когда массив удваивается, у нас появляется больше ящиков, поэтому прогулки короче.

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

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

Кроме того, как insert () работает для набора?

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

Как набор проверяет, существует ли в нем элемент?

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

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

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

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

cppreference говорит:

Наборы обычно реализуются в виде красно-черных деревьев.

Я проверил, и libc++, и libstdc++ действительно используют красно-черные деревья для std::set.

std::unordered_set был реализован с хеш-таблицей в libc++, и я предполагаю то же самое для libstdc++, но не проверял.

Изменить: По-видимому, мое слово недостаточно хорошее.

• libc++: 1 2
• libstdc++: 1

Подключаюсь к этому, потому что я не видел, чтобы кто-то явно упоминал об этом ... Стандарт C ++ не определяет структуру данных для использования для std :: set и std :: map. Однако он указывает на сложность выполнения различных операций. Требования к вычислительной сложности для операций вставки, удаления и поиска более или менее вынуждают реализацию использовать алгоритм сбалансированного дерева.

Существует два распространенных алгоритма реализации сбалансированных бинарных деревьев: красно-черный и AVL. Из этих двух Red-Black немного проще в реализации, требуя на 1 бит памяти меньше на каждый узел дерева (что вряд ли имеет значение, так как вы в любом случае собираетесь записать на нем байт в простой реализации) и является немного быстрее, чем AVL при удалении узлов (это связано с более мягкими требованиями к балансировке дерева).

Все это в сочетании с требованием std :: map о том, что ключ и данные хранятся в std :: pair, навязывают вам все это без явного указания структуры данных, которую вы должны использовать для контейнера.

Все это, в свою очередь, дополняется дополнительными функциями С ++ 14/17 для контейнера, которые позволяют объединять узлы из одного дерева в другое.