std::set fast and slow, what is going on?

I cannot explain exactly why this is happening but I could propose a solution. I've been able to reproduce this on my PC when I run the release build under the debugger (with F5). When I run the build from the command line or with Ctrl-F5 I don't get that kind of behavior.

This has something to do with the debug heap which is on by default when you launch under the debugger. It's described in great detail here. To prevent this from happening either

1. Run from the command line or with Ctrl-F5 (Debug -> Start Without Debugging).
2. Go to Project -> Properties -> Debugging -> Environment and add _NO_DEBUG_HEAP=1.

If I had to guess I would say that it has something to do with the implementation of the memory allocation tracking in Windows/VS runtime. Probably some internal lists fill up and reallocate or something else along these lines.

I think std::set is implemented as a binary search tree. Since you are increasing i by 1 every time you are essentially creating an adversarial (worst case) scenario for this type of datastructure (rebalancing of the tree is required on almost every insert).

Also, it is 50 million inserts, so some time is expected, though I wouldn't think it would be 5 ms.

Also, I would do your "clear" after you print your time, as I don't see the reason you would benchmark both inserting and removing items.