有序集与GNU C++ PBDS

先决条件 : STL的基本知识 和 设置数据结构 .

关于有序集

有序集是一个 g中基于策略的数据结构++ 这就保持了 唯一的 按排序的元素。它以日志（n）复杂度执行STL中集合数据结构执行的所有操作，并以日志（n）复杂度执行另外两个操作。

• 钥匙（k）的顺序 ：严格小于k的项目数。
• 按顺序查找（k） ：集合中的第K个元素（从零开始计数）。

实现有序集所需的头文件及其说明

为了实现OrrordEdStand和GNU C++库，我们需要包含其他基于策略的数据结构：

//公共文件 包括

//包括树_顺序_统计_节点_更新 包括

第一个用于包含关联容器或模板组，例如 如集合、多重映射、映射等。 我们将在下面使用的基于树的数据结构出现在这个头文件中。 第二个头文件用于包含 树\顺序\统计信息\节点更新 具体解释如下：

using namespace __gnu_pbds;

它是 基于GNU的基于策略的数据结构 .

基于树的容器有一个具体的结构，但有序集实现所需的结构是：

tree < int ,  null_type ,  less ,  rb_tree_tag ,  tree_order_statistics_node_update >

1. 智力 ：这是我们要插入的数据类型（键）。它可以是整数、浮点或整数对等。
2. 空_类型 ：这是映射的策略。将其用作一个集合在这里是空的。如果我们想得到map而不是set，那么第二个参数类型必须是mapped type。
3. 较少的 ：它是比较两种功能的基础。
4. rb_树_标签 ：使用的树的类型。它通常是红黑树，因为插入和删除需要log（n）时间，而其他树则需要线性时间，例如splay_树。
5. 树\顺序\统计信息\节点\更新 ：它包含在tree_策略中。hpp和包含用于更新基于树的容器的节点变量的各种操作，因此我们可以跟踪元数据，如子树中的节点数

有序集合中除集合之外的其他函数

与之前的集合操作一样，它支持 二 主要重要业务

• 按顺序查找（k） ：它返回到第k个元素的迭代器 （从零开始计数） 在设定的O（logn）时间内。要找到第一个元素，k必须为零。 假设我们有一个集合s:{1,5,6,17,88}，然后： *（s.find_by_order（2））：集合中的第三个元素，即6 *（s.find_by_order（4））：集合中的第五个元素，即88

• 钥匙（k）的顺序 ：它返回所需的项目数 严格地 在O（logn）时间内小于我们的物品k。 假设我们有一个集合s:{1,5,6,17,88}，然后： s、 _键的顺序（6）：元素计数 严格地 小于6等于2。 s、 _键的顺序（25）：元素计数 严格地 小于25等于4。

集合与有序集合的区别 集合和有序集合之间没有太大区别，尽管有序集合可以被假定为集合的扩展版本，能够执行一些更高级的功能（如上所述），这些功能在竞争性编程中广泛使用。

笔记 有序集合 tree 。 宏

实际应用： 假设我们在一个数组中一个接一个地插入元素，在每次插入之后，我们得到一个范围[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。

Input :     1
            1 2
            2
            3 5
            5
            1 4
Output :    1
            0
            2

最初，数组是空的

• 插入1。
• 大于等于1且小于等于2的元素计数为1，即1。
• 插入2。
• 大于等于3且小于等于5的元素计数为0。
• 插入5。
• 大于等于1且小于等于4的元素计数为2，即1，2。

  如果我们在STL find upper_bound on set中使用set，它只给出元素的地址，我们只能通过使用解引用运算符（*）来找到该地址处的值。

  假设我们有一个集合{0，1，2，7，8，20}，我们找到了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 i.e. 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之间的元素计数可以通过以下方式找到： 好的。_键（r+1）的顺序–o_设置。钥匙的顺序（l）

  笔记 ：因为集合只包含 唯一的 元素，所以要在具有重复元素的数组上执行操作，我们可以将密钥作为一对元素，而不是整数，其中第一个元素是数组的必需元素，并且只有该对中的第二个元素必须是唯一的，以便整对元素都是唯一的。

  有关更多详细信息，请参阅： https://gcc.gnu.org/onlinedocs/libstdc++/手动/政策数据结构。html