edit: I am specifically comparing `std::vector`'s *linear* search operations to the `std::map` *binary* search operations because that is what Herb's claim seemed to relate to. I know that using a binary search will move the performance from O(N) to O(log N) but that would not be testing Herb's claim

Bjarne Stroustrup and Herb Sutter have both recently talked about how awesome `std::vector` is in situations one would expect `std::list` to be used, owing to the cost of cache misses during linked list traversal. (see <http://channel9.msdn.com/Events/Build/2014/2-661> at the 48 minute mark)

Herb made a further statement however that operations on an ordered vector were even faster than `std::map`, (see <http://i.imgur.com/zX07TZR.png> taken from the 51:30 mark of the above channel9 video) which I found difficult to fathom. So I created a small test to demonstrate this and had difficulty reproducing these results: <https://ideone.com/MN7DYK>

This is the test code:

```
template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

```

Notice how the **`std::vector` performs an order of magnitude slower than `std::set`** . Of course this is the result I expected, but I am confused about the claim that Herb was trying to make.

What am I doing wrong? Or am I misunderstanding Herb's claim?

Notes on my test app:

* it must use linear operations - the whole point of the exercise is to demonstrate CPU cache magic, these are the constraints Herb and Bjarne put on the exercise
* I didn't try any tricky loop-unravelling for my vector iteration, but I believe that the iteration isn't affecting performance much anyway
* I limited the loop to 10K items because ideone times out on larger sets, but increasing the size doesn't change the results

edit: see <https://ideone.com/916fVd> for a modified example that only compares the performance of lookups. Linear searching exhibits the same performance.