I like to build my cp library. I am not aiming to fill it by each algo I have met, so content looks poor. Instead I am focusing on frequently used features or implement convenient api for powerful methods.
Also I like to rate cp libraries of others and currently I noticed that my lib have enough implementations which I never seen before, so I want to share it with community.
Hope it will inspire you to improve or rewrite your library and eventually rethink about some algorithms (which happens to me couple times).
#5 Centroid decomposition
graphs/trees/centriod_decomposition.cpp
This one is the perfect example of what I am calling convenient api. I've seen a lot of centroid decomposition snippets and almost all of them is template code or unfinished data structure with piece of code where you need to add your solution. I have snippet that doesn't need changes at all and I need to just call it.
centriod_decomposition(tree, [&](auto &g, size_t centroid, size_t sizeof_subtree) {
//g - is current subtree and I can freely traverse it from centroid by dfs
});
Once I've seen almost similar implementation but author passed to lambda original tree and vector of blocked vertices. I feel this uncomfortable to code: you still need to take in mind that vertex can be inaccessible.
It has little overhead from coping graph but I have never stubbed on this because overall running time is more crucial.
#4 Parallel binary search
misc/parallel_binary_search.cpp
Well, it is actually not general (can't solve this) but I am working on this. This one about "find first version of data where query is satisfied".
It rarely used but api is really sweet. Here I need to describe scope where I set predicate, implement evolution of data and just commit all changes — internally all queries will be executed in necessary moments.
auto res_bs = parallel_binary_search(qn, m, [&](auto vc) {
//usually create init data
vc.pred = [&](size_t qi) {
//check query in data and return true/false
};
//do changes of data and call vc.commit() on each
});
Some examples:
As bonus this implementation has very low time and memory overhead. It not uses map or vector of vectors: you can store all unfinished ranges sorted by left and very easy to split it to new groups in place.
#3 ilist<T>
Implicit splay tree with iterators (stl style). It has api close to std::vector
and not invalidating iterators like in std::set
.
ilist<int> a;
a.push_back(0);
a[0] = 10; //O(logn) access
a.assign(begin(vec), end(vec));
for(int &x : a) ++x; //traverse from begin to end
while(std::size(a) < 10) { //calls a.size()
a.insert(begin(a), 1); //O(logn) insertion
}
ilist<int> b = a; //makes copy
a.insert(begin(a), b.extract(begin(b) + 3, begin(b) + 6)); //O(logn) cut
a.insert(end(a), std::move(b)); //moving without coping
auto it = a.at(5); //iterator to 5th item
assert(begin(a) + 5 == it); //iterator advance in O(logn)
assert(it - begin(a) == 5); //iterators distance in O(logn)
assert(std::next(it) - begin(a) == 6); //also has ++it
assert(std::prev(it) - begin(a) == 4); //and --it
This snippet is biggest one but is not in final state. As TODO I want to implement reversible
option and build link-cut trees that use it as black box.
#2 NTT (with modulos calculated in compile time)
My ntt is very default and maybe slow but it have no hardcoded ntt-frendly modulos. Actually I can understand why you add 3-5 modulos in ntt snippet but what I do not is hardcoding attendant stuff for it like roots. Seriously all this can be calculated in runtime easily. But with power of c++ all modulos can be calculated too!
As result convolution receives parameters and compiler will generate modulos that satisfy them.
convolution<modint<998244353>>(a, b); //will recognise as ntt-mod
convolution<modint<786433>>(a, b); //same! check codeforces.com/gym/100341/problem/C
convolution<modint<1000000007>>(a, b); //will generate 3 modulos and combine result by CRT
convolution<uint64_t, 1<<20 ,5>(a, b); //will generate 5 modulos good for length at most 2**20
#1 Hashing
And finally my favorite... strings/hasher.cpp
My hashing snippet uses famous rolling hash with $$$mod = 2^{61}-1$$$ with magic bit multiplication which works really fast.
Lets define core usual primitives about hashing and just implement it:
hash_t
— wrapper of uint64_t
containing raw hash (special case of modint)
hashed
— what remains from string after it... hashed: hash_t and its length
hashed h = str; //from std::string
h.length() // length of hashed string
if(h1 == h2) // equality check in O(1)
h = h1 + h2; // concatenations in O(1)
h += 'a';
hasher
— hash array of string/vector, allows get hash on range in O(1)
hash_span
— reference to some range in hasher
hasher a(str), arev(rbegin(str), rend(str));
a.substr(start, length); // hashed
a.subhash(start, length); // hash_t
hash_span s = a(l, r);
assert(s.length() == r - l);
assert(a[s.start()] == s[0]);
hash_span
also have overloaded operator<
(in $$$O(\log len)$$$) which can be used in std::sort
or std::lower_bound
.
The codes are nice.
But this line is very sad.
Oh, its just reference :)