Re: [Boost-users] complexity problem using multi_index insert()

And the problem is that inserting those few elements into the multi_index container takes almost 9 minutes. <...>

In addition to Joaquín's advice: ensure your benchmarks are done in "release mode", i.e. with full optimization. Besides, if you compile in MSVC and stl containers are somehow related to this operation, you might also want to disabe so called "secured stl", which has enormous impact on the performance: #define _SECURE_SCL 0