This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libgcc/81806] New: Split in pbds works in O(n) instead of O(log n)
- From: "aleksandr.kulkov at phystech dot edu" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Thu, 10 Aug 2017 17:37:46 +0000
- Subject: [Bug libgcc/81806] New: Split in pbds works in O(n) instead of O(log n)
- Auto-submitted: auto-generated
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
Bug ID: 81806
Summary: Split in pbds works in O(n) instead of O(log n)
Product: gcc
Version: 6.4.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libgcc
Assignee: unassigned at gcc dot gnu.org
Reporter: aleksandr.kulkov at phystech dot edu
Target Milestone: ---
In the end of the split in policy based data structures extension function
split finish is called
(https://code.woboq.org/gcc/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp.html#__gnu_pbds::detail::PB_DS_BIN_TREE_NAME::split_finish)
which works in O(n) due to call of std::distance of two iterators. In the
official documentation it is said to be O(log n) though. This problem can be
resolved by keeping subtree sizes in metadata like it is done in
tree_order_statistics_node_update. Is it possible to fix the bug?