> What is the best way to combine "order" with "quick lookup" 
> in a single Collection without keeping essentially two pointers
> to each element?

There is none. "quick lookup" means re-ordering elements for faster access
no matter how you do it (hashes, binary search etc). So there's simply no
way to prevent a second structure. However, I *think* that it might be
advantageous to store indexes into the ordered sequence rather than pointers
to objects (this may allow some faster inserts and removals). 

Geesh, Richard is the guy who knows all about this - care to comment?

Cheers,
  - Andreas