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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

Шаг отладки в g++ 6.4 stdlibc ++ source

Знаете ли вы, что в пакете g++-6 Ubuntu по умолчанию 16.04 или в сборке GCC 6.4 из источника вы можете войти в библиотеку 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 против std:unordered_set: Какая структура данных находится внутри std :: map в C ++?

Характеристики производительности

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

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

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

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

• std::unordered_set, более сложный шаблон шаблона hashmap:

  • на не масштабированном графике мы ясно видим, что динамический массив поддержки удваивается на огромном от линейно увеличивающихся шипов

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

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

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

Answer 6

cppreference говорит :

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

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

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

Редактировать: Видимо мое слово недостаточно хорошо.

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