g中基于策略的数据结构++-yiteyi-C++库

G+编译器还支持一些不是C++标准库的一部分的数据结构。这种结构称为基于策略的数据结构。这些数据结构旨在实现高性能、灵活性、语义安全性以及与std中相应容器的一致性。要使用这些结构，必须在代码中添加以下行：

null

C++

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

例如，下面的代码显示了一个基于策略的数据结构，类似于set，它可以添加/删除元素，可以在O（logn）时间内找到小于x的元素数、第k个最小元素等。它也可以像数组一样索引。这个集合的特点是我们可以访问排序数组中元素的索引。如果元素没有出现在集合中，我们得到元素在集合中的位置。

C++

                         // Program showing a policy-based data structure.                       
                         #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;                       
           
                         // a new data structure defined. Please refer below                       
                         // GNU link :                           https://goo.gl/WVDL6g                                    
                         typedef                                     tree<                                     int                                     , null_type, less<                                     int                                     >, rb_tree_tag,                       
                                                 tree_order_statistics_node_update>                       
                                                 ordered_set;                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 ordered_set p;                       
                                                 p.insert(5);                       
                                                 p.insert(2);                       
                                                 p.insert(6);                       
                                                 p.insert(4);                       
           
                                                 // value at 3rd index in sorted array.                       
                                                 cout <<                                     "The value at 3rd index ::"                       
                                                 << *p.find_by_order(3) << endl;                       
           
                                                 // index of number 6                       
                                                 cout <<                                     "The index of number 6::"                                     << p.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 <<                                     "The index of number seven ::"                       
                                                 << p.order_of_key(7) << endl;                       
           
                                                 return                                     0;                       
                         }                       

输出：

The value at 3rd index ::6The index of number 6::3The index of number seven ::4

注：这两个函数对_键的_进行排序和按_顺序查找都在对数时间内工作。

为了在有序集合中插入同一元素的多个副本，请替换以下行，

typedef tree ，rb_tree_标记，tree_order_statistics_node_update>ordered_set；

具有

typedef tree ，rb_tree_标记，tree_order_statistics_node_update>ordered_multiset；

C++

                         // Program showing a policy-based data structure.                       
                         #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;                       
           
                         // a new data structure defined. Please refer below                       
                         // GNU link :                           https://goo.gl/WVDL6g                                    
                         typedef                                     tree<                                     int                                     , null_type, less_equal<                                     int                                     >, rb_tree_tag,                       
                                                 tree_order_statistics_node_update>                       
                                                 ordered_multiset;                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 ordered_multiset p;                       
                                                 p.insert(5);                       
                                                 p.insert(5);                       
                                                 p.insert(5);                       
                                                 p.insert(2);                       
                                                 p.insert(2);                       
                                                 p.insert(6);                       
                                                 p.insert(4);                       
           
                                                 for                                     (                                     int                                     i = 0; i < (                                     int                                     )p.size(); i++) {                       
           
                                                 cout <<                                     "The element present at the index "                                     << i                       
                                                 <<                                     " is "                                     ;                       
           
                                                 // Print element present at the ith index                       
                                                 cout << *p.find_by_order(i) <<                                     ' '                                     ;                       
                                                 cout <<                                     ''                                     ;                       
                                                 }                       
           
                                                 return                                     0;                       
                         }                       

输出

The element present at the index 0 is 2 The element present at the index 1 is 2 The element present at the index 2 is 4 The element present at the index 3 is 5 The element present at the index 4 is 5 The element present at the index 5 is 5 The element present at the index 6 is 6

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

THE END

技术文章