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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

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

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

Ответ 4

Шаг отладки в источник g++ 6.4 stdlibc++

Знаете ли вы, что в Ubuntu 16.04 по умолчанию в g++-6 или в сборке 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) в 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 - это черно-красное дерево, _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++?

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

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

Процедура генерации графа и анализ Heap против BST, а также по адресу: Heap vs Binary Search Tree (BST)

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

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

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

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

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

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

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

Ответ 5

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

Ответ 6

cppreference говорит:

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

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

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

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

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