The g++ compiler also supports some data structures that are not part of the C++ standard library. Such structures are called policy-based data structures.
These data structures are designed for high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std.
To use these structures, the following lines must be added to the code:
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
Example
// 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 ::6
// The index of number 6::3
// The index of number seven ::4
NOTE: Both the functions order_of_key
and find_by_order
work in logarithmic time.
Try the following example in the editor below.
You are given an ordered_set X, answer the queries asked in the comment in the editor below.