Another test, this time using a larger storage on the heap: void test_speed_heap() { typedef monotonic::map<int, monotonic::list<int> > map_with_list; monotonic::inline_storage<10000000> *storage = new monotonic::inline_storage<10000000>; map_with_list m(*storage); size_t count = 100000; boost::timer timer; for (size_t i = 0; i < count; ++i) { int random = rand() % 100; map_with_list::iterator iter = m.find(random); if (iter == m.end()) m.insert(make_pair(random, monotonic::list<int>(*storage))); else iter->second.push_back(i); } double elapsed = timer.elapsed(); cout << "monotonic: " << elapsed << endl; delete storage; // do the same thing, with std::containers { typedef std::map<int, std::list<int> > map_with_list; map_with_list m; boost::timer timer; for (size_t i = 0; i < count; ++i) { int random = rand() % 100; map_with_list::iterator iter = m.find(random); if (iter == m.end()) m[random] = std::list<int>(); else iter->second.push_back(i); } double elapsed = timer.elapsed(); cout << "std: " << elapsed << endl; } } monotonic: 0.011 std: 1.130