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?
