Extensions of GNU

Here are some extensions that I have found. Some of them are more useful than others.

1. indexed set
2. power(x,y)
3. rope

indexed set is just like a set. You can do lower bound (find the index) and find the index of the kth biggest element. With STL set, you cannot find the index. All functionalities of indexed set is in log(the size of container). To use it, you need to include the following lines :

#include <ext/pb_ds/assoc_container.hpp> // includes some countainers
using namespace __gnu_pbds;

Exercises :

ORDERSET

Little Artem and Time Machine

DNA Evolution

2 ) power(x.y)

This is a precise log(n) complexity function to do powers. To use it, include these lines :

#include <ext/numerics>

3 ) rope

This is a data structure that can handle concatenations in O(1) and can extract very fast a substring, insert and delete a substring quickly. You can use operator [] on rope. Reverse function of rope is very slow. How to use it :

#include <ext/rope>

using namespace __gnu_cxx;

// how to use

string s = "AABB";

rope<char> r = c_str(s); // add string to r

r += r.substr(1,3); // from pos 1 with length 3

r.erase(1,3);  // from pos 1 with length 3 erase

Exercises for rope :

AROPE

AROPE2

AROPE3

Thank You for reading and please comment below if you have other extensions to share : )