title: associative / random access container
body: <p>I'm looking for a data structure to hold an unordered collection of unique elements, which would support the following operations</p>
  
  <ol>
  <li>insertions/deletions of elements anywhere in the collection</li>
  <li>querying if an element is present</li>
  <li>access to a random element</li>
  </ol>
  
  <p>Naively, 1 and 2 suggest using an associative container, e.g. <code>unordered_set</code>, but then 3 is linear in number of elements. Using a random access container, e.g. <code>vector</code>, makes 3 easy, 1 can be done in O(1), but then 2 is again O(N). </p>
  
  <p>The question is if there's a known way around this linear complexity? </p>
  
  <p>EDIT: By a random element in 3 I mean: given an arbitrary ordering of N elements, retrieve an element number <code>j</code> where <code>j</code> is between 0 and N-1. For an <code>std::vector</code> it's just subscripting, for an <code>std::list</code> or an <code>std::set</code> it's incrementing the list/set iterator j times starting from <code>begin()</code> etc. </p>