[Bug libstdc++/81806] Split in pbds works in O(n) instead of O(log n)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806 Oleksandr Kulkov changed: What|Removed |Added CC||tadeus.prastowo at unitn dot it --- Comment #4 from Oleksandr Kulkov --- Hi. I'm not Zlobober, I'm adamant. 1. At least, Jonathan suggested to start with fixing this in https://gcc.gnu.org/ml/libstdc++/2019-07/msg00066.html , so it doesn't seem hopeless for now 2. I'm not sure one really needs to remove it or make it a nop. Because order_statistics_node_update has order_of_key and find_by_order functions which are not necessary in other policy tags 3. Well, Jonathan dropped his suggestion to deprecate pbds in https://gcc.gnu.org/ml/libstdc++/2019-07/msg00071.html so probably we should presume pb_ds won't be immediately removed after fix 4. Even so is better than having it non-fixed or even deprecated forever
[Bug libstdc++/81806] Split in pbds works in O(n) instead of O(log n)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806 --- Comment #5 from Oleksandr Kulkov --- Hi. I'm not Zlobober, I'm adamant. 1. At least, Jonathan suggested to start with fixing this in https://gcc.gnu.org/ml/libstdc++/2019-07/msg00066.html , so it doesn't seem hopeless for now 2. I'm not sure one really needs to remove it or make it a nop. Because order_statistics_node_update has order_of_key and find_by_order functions which are not necessary in other policy tags 3. Well, Jonathan dropped his suggestion to deprecate pbds in https://gcc.gnu.org/ml/libstdc++/2019-07/msg00071.html so probably we should presume pb_ds won't be immediately removed after fix 4. Even so is better than having it non-fixed or even deprecated forever
[Bug libgcc/81806] New: Split in pbds works in O(n) instead of O(log n)
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?
