I hoped it would attach to https://gcc.gnu.org/ml/libstdc++/2019-05/msg00107.html but it didn't happen :(
ср, 10 июл. 2019 г. в 01:39, Alexander Kulkov <adamant....@gmail.com>: > Hi there! I hope, this message will go to where it's expected to go, since > I'm not really familiar with e-mail threads. > > I was the one who brought > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806 issue about > sub-optimal implementation of split function in pbds. The reason why I did > so is clearly described on this comment: > https://codeforces.com/blog/entry/10355?#comment-157883 > > So, a bit of story and context. Five years ago at codeforces.com > (competitive programming website) someone eventually pointed out that there > is order-statistics tree in SGI library. It turned out to be very useful in > competitions since it is quite common type of queries to count number of > elements less than k in set and unfortunately regular std::set doesn't > provide such possibility although it would be extremely useful in > competitions. > > I made two posts about pbds on codeforces to introduce them to community: > https://codeforces.com/blog/entry/11080 and > https://codeforces.com/blog/entry/13279. First one introduces structures > in general and second one describes how to modify them so they support > custom queries. Second one was not quite as popular, perhaps because it's > not much easier to comprehend and remember concept than simply write > something like cartesian tree on live contest. But the first one is pretty > much alive, most recent comment was only 8 days ago. > > There was also another post (https://codeforces.com/blog/entry/60737) > considering hash_map from pb_ds as a replacement for unordered_map since > hash_map clearly outperform unordered_map. This one is also quite popular > and well-known in competitive programming community. > > So speaking about "Do you actually use these containers?" I would say that > I often use tree_order_statistics_node_update in competitions, and in > general specifically tree_order_statistics_node_update and hash_map are > pretty popular in competitive programming community. > > Deprecating policy based data structures will deal much pain to some > competitors because problems in which it's possible to use pbds instead of > custom balanced binary trees occur quite often and so now we'll have to > implement bbst instead of using something out of the box. > > Not sure if you would consider this usage case as something "serious", but > well, I was asked, so I answered. > > Regards, > Oleksandr Kulkov >
