pb_ds gp_hash_table resize strategy

[Jonathan Wakely]

On Wed, 26 Jun 2024, 07:16 CH HC, <i2333o@outlook.com> wrote:

> Pb_ds codes still have their uses, and it would be great if minor changes
> to the codes (or at least to the documentations) could keep them in
> libstdc++ without potential bugs.
> Without considering introducing other libraries like absl::flat_hash_map,
> the pb_ds gp_hash_table might be the only built-in choice of fast hash map
> (as std::unordered_map is unbearably slow). Considering that
> std::unorded_map is limited by stl restrictions and it is difficult to
> improve its efficiency in the foreseeable future, (re-)maintaining pb_ds
> lib might be a good option.
>

But nobody is willing to do that work.

Unless somebody actually *does* maintain it, the code should be removed
from libstdc++. It could be moved to a separate project that isn't part of
libstdc++ so would still be available, but not our problem.

People keep saying they want to use it, but nobody invests the time to
maintain it. That's not good enough to keep it.





> ------------------------------
> *发件人:* Jonathan Wakely <jwakely.gcc@gmail.com>
> *发送时间:* 2024年6月21日 16:10
> *收件人:* CH HC <i2333o@outlook.com>
> *抄送:* gcc@gcc.gnu.org <gcc@gcc.gnu.org>; libstdc++ <libstdc++@gcc.gnu.org>
> *主题:* Re: pb_ds gp_hash_table resize strategy
>
>
> On Fri, 21 Jun 2024, 02:28 CH HC via Gcc, <gcc@gcc.gnu.org> wrote:
>
> Hi there,
> In libstdc++/ext/pb_ds , I noticed that the (automatic) resize function
> for gp_hash_table does copy-and-destruct operations on old key-value pair
> (from the line resize_no_store_hash_fn_imps.hpp:58). Meanwhile,
> cc_hash_table simply moves the old pair as expected.
> So for gp_hash_table, this strategy makes it impossible to have
> non-copyable values, e.g. __gnu_pbds::gp_hash_table<int,
> std::unique_ptr<int>>. And there exists potential bugs for scenarios like,
> keeping a gp_hash_table<int, std::list<int>> and saving some iterators of
> those lists elsewhere for quick access to specific elements in lists.
> There could be some workarounds like using std::shared_ptr<T> as value
> type, but not so perfect.
> I wonder if this is caused by some implementation difficulty or just a
> small bug?
> Yours,
> chhc
>
>
> Hi, this question would be more appropriate on the libstdc++@gcc.gnu.org
> making list. I've Cc'd that list. Please take the gcc list out of any
> future replies, thanks.
>
> The pb_ds code was written pre-C++11 and not updated for move semantics.
> All that code is completely unmaintained and my preference would be to
> remove it completely.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20240626/7c886783/attachment.htm>