The Boost C++ library in competitive programming

This post was originally written as a feature request for Codeforces; some relevant discussion can be found here.

I believe that adding the Boost library on Codeforces would be a great addition for C++ competitive programmers. AtCoder already supports it (alongside GMP and Eigen, but Boost has replacements/wrappers for those: Boost.Multiprecision and Boost.uBLAS). CodeChef supports it too (or at least used to support it at some point, not sure now). I’ve seen at least 3 posts by people trying to use Boost on Codeforces and failing, and on thinking about it, I couldn’t really come up with a good reason (in my opinion) that Boost should not be supported on Codeforces.

Some might argue against adding a library on Codeforces, but for them, I recommend viewing this post as an educational resource on some of the library’s features that I find cool.

There are a lot of things in the STL in the newer C++ standards, whose implementations were originally inspired from Boost, so you could be able to use some features that might not be available until the next few C++ standards.

As of now, the latest version of Boost is 1.83.0, and its documentation can be found here.

Here are a few features from Boost that are pretty useful for competitive programming:

1. Algorithms from Boost.Algorithms — this includes algorithms like KMP and binary exponentiation (power for arbitrary associative operations) as well. It also makes for much cleaner code and with significantly less effort. It also includes some “mini” algorithms that are annoying to write, that one might use in some technical contexts (for example, gather is an algorithm like this, and gets used a lot in divide and conquer problems). There are some algorithms that ended up in the STL, like partition_point for doing binary search.

2. Containers from Boost.Container — this includes a multitude of containers that are not in the C++ standard yet. My personal favourites among these containers are the flat_map and flat_set containers, which are much better implementations for the corresponding associative data structures than the STL ones, and small_vector, which does similar optimizations as the basic_string STL container, but has less stringent conditions on the type of things it can contain.

3. Better bitsets using the dynamic_bitset library — there was a recent post about dynamic bitsets in Python, but I mentioned a way of getting there using a hack with C++ STL bitsets. However, dynamic bitsets are supported in Boost. In fact, the Boost implementation also exposes functions like find_first, find_next, range set, range flip and so on.

4. Graph algorithms from the Boost Graph Library — it contains practically every useful graph algorithm that we encounter in competitive programming.

5. Different kinds of heaps with Boost.Heap — this contains multiple types of heaps with a lot of useful specialized functions. Ever wanted to try out a Fibonacci heap? Or just any heap with decrease-min or deletion operations? This library will cater to all your needs.

6. Interval handling using Boost.Icl — often we want to handle ranges of integers in competitive programming problems. This library gives us ready-made data structures to solve such problems, without having to think about corner cases that arise with interval sets. This solution is a prime example that would be much easier to implement with this library.

7. Intrusive containers using Boost.Intrusive — there are times when we want to implement a list manually, with some additional information inside the node. For example, there is an implementation of adjacency lists that is quite popular in China, which makes an array of nodes, and inside those nodes, it stores pointers/index of next/previous edges. Doing that using an std::list would be quite painful, and there is a reasonable compromise using intrusive lists. In general, intrusive containers tend to be faster, so if you like constant optimization, this library is pretty nice to know about.

8. Boost.Math — this contains a ton of useful math features. Unfortunately, the polynomial library they provide doesn’t have fast operations (polynomial multiplication is quadratic for example), but the rest of the functionality is pretty good. It has things like continued fractions, root finding and quaternions, all of which I have seen in competitive programming contests.

9. BigInt using Boost.Multiprecision — self-explanatory.

10. Linear algebra using Boost uBLAS — this is a linear algebra library that has pretty much all the functionality one would ever need on a competitive programming problem. However, this library is quite old, and it is usually recommended to use other libraries just for that reason (though I don’t find this to be off-putting). The one thing you need to squeeze out performance is to define the macro BOOST_UBLAS_NDEBUG.

Hopefully this was enough to convince some people that Boost is quite a handy library, that might be worth putting effort into learning, and that it convinces MikeMirzayanov to add it on Codeforces.