Re: Proposal: containers: add indexing operations for Set

On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka 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