title: Data structure with unique elements and fast add and remove
body: <p>I need a data structure with the following properties:</p>
  
  <ul>
  <li>Each element of the structure must be unique.</li>
  <li>Add: Adds one element to the data structure unless the element already
  exists.</li>
  <li>Pop: Removes one element from the data structure and returns the element
  removed.  It's unimportant which element is removed.</li>
  </ul>
  
  <p>No other operations are required for this structure.  A naive implementation with a list will require almost O(1) time for  Pop and O(N) time for Add (since the entire list must be checked to ensure
  uniqueness). I am currently using a red-black tree to fulfill the needs of this data structure, but I am wondering if I can use something less complicated to achieve almost the same performance.</p>
  
  <p>I prefer answers in C#, but Java, Javascript, and C++ are also acceptable.</p>
  
  <p>My question is similar to <a href="https://stackoverflow.com/questions/5207741/data-structure-for-fast-insertion-deletion-with-sorting">this question</a>, however I have no need to lookup or remove the maximum or minimum value (or indeed any particular kind of value), so I was hoping there would be improvements in that respect.  If any of the structures in that question are appropriate here, however, let me know.</p>
  
  <p>So, what data structure allows only unique elements, supports fast add and remove, and is less complicated than a red-black tree?</p>