title: std::unordered_map: multithreading insertions?
body: <p>I have a bunch of data (a giant list of integers between 0 and ULLONG_MAX) and I want to extract all unique values. My approach is to create an unordered_map, using the integer list values as the keys and a throwaway bool for the map values. I iterate the list and insert throwaway values for each key. At the end I iterate the map to get all unique keys. Pretty straight forward. </p>
  
  <p>However, my list is so large (100s of millions) that I'd like to multithread this process. I know a naive approach to threading won't work, because unordered_map insertions affect the underlying data structure and so it's not thread safe. And adding locks around each and every insertion will be slow and possibly negate any threading speedup.</p>
  
  <p>However, presumably not every insertion changes the data structure (only ones that can't fit in the existing allocated buckets?). Is there a way to check if an unordered_map re-allocation would be required for a particular insertion, prior to inserting? That way I could only lock threads when the map is getting changed, instead of locking during every insert. Then, prior to each insertion, the threads merely check if a lock exists...rather than doing a full lock/unlock. Is that possible?</p>