I think that for it to take that long he would have to be sorting it after every push_back.
If you only sort it once, after the data is all loaded in, then perform many binary_searches, then the overhead of the sorting becomes less and less significant to the point that the binary_search will be faster. Still wont beat hashing, but it should be good enough.