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

Reply via email to