Always measure! In a realistic application (with cache pressure) you may find an array performs even better because the CPU can trivially predict and pipeline

Always measure! In a realistic application (with cache pressure) you may find an array performs even better because the CPU can trivially predict and pipeline the entire operation vs jumping around to random locations in memory. Another approach is a B-tree with lots of nodes stored at the leaves. This can get you the array's linear performance for small datasets, while preserving other big-O benefits of sets/trees (eg insertion time). As the side of your dataset grows, there is a performance cliff at L1, L2, and L3 cache size. For very large datasets, creating data structures with predictable access patterns often trumps Big-O entirely. If following a linked list thrashes the cache it turns out the constant factor can and does dominate. So again, always measure with your application on your intended hardware. Be sure you measure with realistic loads and access patterns.