std::set has a huge constant factor because it implements a binary search tree. The constant factor is not to be underestimated. Never use set when it is not strictly necessary. Consider reading this article: http://lafstern.org/matt/col1.pdf
Edit: same applies to map.