Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

Jonathan Wakely-4
Sorry for the late reply that wasn't "tomorrow".

On Tue, 9 Jul 2019 at 23:40, Alexander Kulkov wrote:

>
> 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.

Thanks for responding!

I don't really care about this use case, sorry. If the programming
competition community were providing fixes or improvements for this
code I might be more inclined to keep supported it, but it seems like
we're just carrying around a huge chunk of code because it saves
people some time in some competitions. Presumably the competition code
is not reused, so there's no backwards compatibility issue here
either.
Reply | Threaded
Open this post in threaded view
|

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

Alexander Kulkov
Sounds fair to me. Well, I personally might be interested in providing
fixes and improvements for the code. I might even try to find some other
people in community to contribute.

PBDS is very well-thought library which I admired since the moment I saw
it, and the possibility that it may completely go to waste kind of
disappoints me, so I might put considerable effort to save it if that's
possible. The major issue, though, is that I don't really know even how to
start since I'm completely new to libstdc++ and have little experience with
such huge projects. Any help and/or advice here in how I may contribute
would be much appreciated.

вт, 23 июл. 2019 г. в 19:21, Jonathan Wakely <[hidden email]>:

> Sorry for the late reply that wasn't "tomorrow".
>
> On Tue, 9 Jul 2019 at 23:40, Alexander Kulkov wrote:
> >
> > 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.
>
> Thanks for responding!
>
> I don't really care about this use case, sorry. If the programming
> competition community were providing fixes or improvements for this
> code I might be more inclined to keep supported it, but it seems like
> we're just carrying around a huge chunk of code because it saves
> people some time in some competitions. Presumably the competition code
> is not reused, so there's no backwards compatibility issue here
> either.
>