http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57885
--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> --- A few notes. First, lately the std containers, which have different complexity requirements, share zero code with the tr1 version. In general we should redo the measurements for 4.9 which has further changes. In my opinion, in these measurements 4.8.1 was pretty good for Insertion, but Lookup got worse, that seems to me the most important issue. I would ask Francois to check why, profile where the additional time is going (assuming it's still the case for 4.9!)