Proposal: containers: add indexing operations for Set

Johan Tibell johan.tibell at gmail.com
Mon Jul 9 19:59:58 CEST 2012


On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka <fox at ucw.cz> wrote:
> Any balanced tree can support indexing API, as long as every subtree
> stores its size. That is obviously trivially true for size-balanced
> trees, as the subtree sizes are used for balancing. If for example AVL
> trees were used, sizes would have to be stored explicitly in every node
> for indexing API to work fast.

There might be some other benefits to adding the size as well. IIRC
union is faster if the first set is smaller than the second set. If we
can look up the sizes in O(1) time we can rearrange the arguments to
make sure this is the case.

-- Johan



More information about the Libraries mailing list