Which of the following methods provides the fastes

Which of the following methods provides the fastest way to get a sorted container of int elements and find the given value (which is present in the container) using the binary search?


1. set<int> iset;
   iset.insert(...); 
   ....  // add several more values
   set<int>::iterator it = lower_bound(begin(iset), end(iset), value);


2. vector<int> ivect;
   ivect.reserve(...); // reserve memory for elements  
   ivect.push_back(...); 
   ....  // add several more values
   sort(begin(ivect), end(ivect));
   vector<int>::iterator it = lower_bound(begin(ivect), end(ivect), value);


3. set<int> iset;
   iset.insert(...); 
   ....  // add several more values
   set<int>::iterator it = iset.lower_bound(value);


4. unordered_set<int> iuset;
   iuset.insert(...); 
   ....  // add several more values
   sort(begin(iuset), end(iuset));
   unordered_set<int>::iterator it = lower_bound(begin(iuset), end(iuset), value);

Explanation

1. The lower_bound function requires random access iterators. set iterators are of bidirectional type, as a result, the complexity of search will be linear.

2. The correct answer. After adding the data, sort will sort the container using the quick sort algorithm, which usually works 30 to 40% faster than n*logn, and lower_bound(value) performs a binary search.

3. Uses set::lower_bound(), for binary search, however, adding data will take longer than in option 2: (n*logn).

4. unordered_set has bidirectional (forward) iterators. The sort function is not applicable because requires random access iterators.