I have a need for a container where I can store 10^6 elements of type T (PODs) , a small number of which (say 100) can be invalid elements (ie special value of T)

The 100 elements can be randomly distributed throughout the 10^6 elements.

The container should be as close to a sequence container as possible.

The required usages:

0. invalid elements can be set   = 10^6 - 100

1. get number of valid elements in O(1)

2. get the max/min element of all valid elements

3. have a bidrectional iterator that iterators only over valid elements

On a separate note, is there a version of multi_array where the number of dimensions is known at runtime?

regards,