C++中的OpKy（）命令-yiteyi-C++库

_key（）的顺序是有序集这是一个基于策略的数据结构在C++中。基于策略的数据结构不是C++标准库的一部分，但G++编译器支持它们。

null

Ordered set是g++中一种基于策略的数据结构，它将唯一元素保持在有序状态。它以日志（n）复杂度执行STL中集合数据结构执行的所有操作，并以日志（n）复杂度执行另外两个操作。

我们可以在这些数据结构中执行两个重要操作：

钥匙的顺序： 集合中严格小于k的项数

按顺序查找： 它返回一个迭代器到第i个最大的元素

这个 钥匙的顺序（） 函数接受一个键并返回有序集中严格小于作为参数传递给它的键的元素数。

例如

假设我们有一个集合s:{1,5,6,17,88}，然后： s、 _键（6）的顺序：严格小于6的元素数为2。 s、 _键（25）的顺序：严格小于25的元素数为4。

与下限（）和距离（）的比较

在C++中，我们有距离它需要两个迭代器并计算它们之间的距离。i、 e它们之间的元素数。它可以作为按顺序查找的替代方法，但对于有序集，它的时间复杂度为O（n）。
下界也是一个选项，需要花费log（n）的时间。它向不小于k的第一个元素返回一个迭代器。但由于它返回一个迭代器，我们永远无法知道小于k的元素的索引或数量。
对于向量和线性数据结构，可以执行以下操作：

索引=下限（k）–myvector。begin（）；

但由于set是基于树的数据结构，我们无法执行此操作。

下面的程序演示了_key（）的顺序_的实现：

                     // CPP program to illustrate order_of_key()                   
                     // for policy based data structures                   
                             
                     #include <iostream>                   
                     using                               namespace                               std;                   
                             
                     // Important header files                   
                     #include <ext/pb_ds/assoc_container.hpp> // Common file                   
                     #include <ext/pb_ds/tree_policy.hpp>                   
                     #include <functional> // for less                   
                     #include <iostream>                   
                     using                               namespace                               __gnu_pbds;                   
                     using                               namespace                               std;                   
                             
                     // Declaring ordered_set                   
                     typedef                               tree<                               int                               , null_type, less<                               int                               >, rb_tree_tag,                   
                                         tree_order_statistics_node_update>                   
                                         ordered_set;                   
                             
                             
                     // Driver code                   
                     int                               main()                   
                     {                   
                                         ordered_set mySet;                   
                             
                                         // Inserting elements to ordered_set                   
                                         mySet.insert(5);                   
                                         mySet.insert(2);                   
                                         mySet.insert(6);                   
                                         mySet.insert(4);                   
                             
                                         // count of elements less than 6                   
                                         cout <<                               "Count of elements less than 6::"                   
                                         << mySet.order_of_key(6) << endl;                   
                             
                                         // number 7 not in the set but it will show the                   
                                         // index number if it was there in sorted array.                   
                                         cout <<                               "Count of elements less than 7 ::"                   
                                         << mySet.order_of_key(7) << endl;                   
                             
                                         return                               0;                   
                     }                   

输出：

Count of elements less than 6::3
Count of elements less than 7 ::4

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章