Упорядоченный набор и GNU C ++ PBDS

Предварительное условие : базовые знания STL и структуры данных наборов.

О заказанном наборе

Упорядоченный набор - это структура данных на основе политики в g ++, которая хранит уникальные элементы в отсортированном порядке. Он выполняет все операции, выполняемые заданной структурой данных в STL, со сложностью log (n) и выполняет две дополнительные операции также со сложностью log (n).

• order_of_key (k) : количество элементов строго меньше k.
• find_by_order (k) : K-й элемент в наборе (отсчет с нуля).

Необходимые файлы заголовков для реализации упорядоченного набора и их описание

Для реализации Order_set и GNU C ++ библиотека содержит другие структуры данных на основе политик, которые нам необходимо включить:

// Common file
include <ext/pb_ds/assoc_container.hpp>

// Including tree_order_statistics_node_update
include <ext/pb_ds/tree_policy.hpp>

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

используя пространство имен __gnu_pbds;

Это пространство имен, необходимое для структур данных на основе политик GNU .

Контейнер на основе дерева имеет конкретную структуру, но необходимая структура, необходимая для реализации упорядоченного набора:

дерево <int, null_type, less, rb_tree_tag, tree_order_statistics_node_update>

1. int : это тип данных, которые мы хотим вставить (KEY). Это может быть целое число, число с плавающей запятой, пара int и т. д.
2. null_type : это сопоставленная политика. Здесь пусто, чтобы использовать его как набор. Если мы хотим получить карту, но не набор, в качестве второго типа аргумента должен использоваться сопоставленный тип.
3. less : это основа для сравнения двух функций.
4. rb_tree_tag : тип используемого дерева. Обычно это красно-черные деревья, потому что для вставки и удаления требуется log (n) времени, в то время как для других требуется линейное время, например splay_tree.
5. tree_order_statistics_node__update : он включен в tree_policy.hpp и содержит различные операции для обновления вариантов узлов древовидного контейнера, поэтому мы можем отслеживать метаданные, такие как количество узлов в поддереве.

Дополнительные функции в заказанном наборе кроме набора

Наряду с предыдущими операциями набора, он поддерживает две основные важные операции.

• find_by_order (k) : он возвращает итератору к k-му элементу (считая с нуля) в наборе за время O (logn). Чтобы найти первый элемент, k должен быть равен нулю.
  Предположим, у нас есть набор s: {1, 5, 6, 17, 88}, тогда:
  * (s.find_by_order (2)): 3-й элемент в наборе, т.е. 6
  * (s.find_by_order (4)): 5-й элемент в наборе, т.е. 88

• order_of_key (k) : он возвращается к количеству элементов, которые строго меньше, чем наш элемент k, за время O (logn).
  Предположим, у нас есть набор s: {1, 5, 6, 17, 88}, тогда:
  s.order_of_key (6): количество элементов строго меньше 6 равно 2.
  s.order_of_key (25): Количество элементов строго меньше 25 равно 4.

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

Практическое применение:
Предположим, у нас есть ситуация, когда элементы вставляются один за другим в массив, и после каждой вставки нам дается диапазон [l, r], и мы должны определить количество элементов в массиве больше, чем равное l, и меньше чем равно r. Изначально массив пуст.
Примеры:

Input :    5
           1 2
           1
           2 5
           2
           1 5

Output :   0
           1
           3

Объяснение:

Изначально массив пуст
• 5 вставлен.
• Количество элементов больше 1 и меньше 2 равно 0.
• 1 вставлен.
• Количество элементов больше 2 и меньше 5 равно 1, т.е. 5.
• 2 вставлен.
• Количество элементов больше 1 и меньше 5 равно 3, т.е. 5, 1, 2.

Ввод: 1
            1 2
            2
            3 5
            5
            1 4
Выход: 1
            0
            2

Изначально массив пуст

• 1 вставлен.
• Количество элементов больше 1 и меньше 2 равно 1, т.е. 1.
• 2 вставлен.
• Количество элементов больше 3 и меньше 5 равно 0.
• 5 вставлен.
• Количество элементов больше 1 и меньше 4 равно 2, т.е. 1, 2.

  Если мы используем set в STL find upper_bound on set, он дает только адрес элемента, и мы можем найти значение по этому адресу только с помощью оператора разыменования (*).

  Предположим, что если у нас есть набор как {0, 1, 2, 7, 8, 20} и мы находим upper_bound равным 2, тогда он возвращает адрес, соответствующий позиции элемента (в данном случае 7) в наборе, и мы НЕВОЗМОЖНО вычесть начальный адрес набора (s.begin ()), чтобы найти количество элементов меньше 2, как в случае вектора.
  Итак, вот и необходимость заказанного набора.

  ПРИМЕЧАНИЕ . Вышеупомянутые функции могут быть реализованы с помощью некоторой другой логики и структуры данных, но использование упорядоченного набора делает код компактным и может быть реализован легко и быстро.

  Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

  Реализация заказанного набора

  // C++ program to demonstrate the // ordered set in GNU C++ #include <iostream> using namespace std; // Header files, namespaces, // macros as defined above #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> // Driver program to test above functions int main() { // Ordered set declared with name o_set ordered_set o_set; // insert function to insert in // ordered set same as SET STL o_set.insert(5); o_set.insert(1); o_set.insert(2); // Finding the second smallest element // in the set using * because // find_by_order returns an iterator cout << *(o_set.find_by_order(1)) << endl; // Finding the number of elements // strictly less than k=4 cout << o_set.order_of_key(4) << endl; // Finding the count of elements less // than or equal to 4 ie strictly less // than 5 if integers are present cout << o_set.order_of_key(5) << endl; // Deleting 2 from the set if it exists if (o_set.find(2) != o_set.end()) o_set.erase(o_set.find(2)); // Now after deleting 2 from the set // Finding the second smallest element in the set cout << *(o_set.find_by_order(1)) << endl; // Finding the number of // elements strictly less than k=4 cout << o_set.order_of_key(4) << endl; return 0; }

  Выход

  2
  2
  2
  5
  1
  

  Таким образом, теперь мы можем легко решить указанную выше проблему, т.е. количество элементов между l и r может быть найдено следующим образом:
  o_set.order_of_key (r + 1) - o_set.order_of_key (l)

  ПРИМЕЧАНИЕ : Поскольку набор содержит только элементы UNIQUE , поэтому для выполнения операций с массивом, имеющим повторяющиеся элементы, мы можем взять KEY как пару элементов вместо целого числа, в котором первый элемент является нашим обязательным элементом массива и только второй элемент пары должен быть уникальным, чтобы уникальна была вся пара.

  Для получения более подробной информации см .:
  https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

  Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

  Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.