This is picked up from http://gcc.gnu.org/ml/gcc/2007-07/msg00681.html , apologises if it has already been dealt with. Both std::string and std::list do not compare lengths before comparing elements in operator==. In std::string this increases the chances of quitting early and produces a small improvement even for equal length strings. For std::list this produces a much larger gain. I believe the operator== for list should simply be replaced implementation used for all the other containers: { return (__x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin())); } Which is efficent as list has a O(1) size.
Well, in our current, C++03, implementation, definitely list::size is O(N). The issue is thorny, as you know well. For C++0x, Howard has a proposal related to the additional splice overload, I'm not sure which is the progress on that...
Ah, woops, many apologises. Too long since I've looked at list::size, I forgot which way around libstdc++ differed from the rest of the world :)
Subject: Bug 32907 Author: paolo Date: Fri Jul 27 17:25:04 2007 New Revision: 126988 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=126988 Log: 2007-07-27 Paolo Carlini <pcarlini@suse.de> PR libstdc++/32907 * include/bits/basic_string.h (operator==(const basic_string<_CharT>&, const basic_string<_CharT>&)): Add. (operator!=): Forward to operator==. * include/ext/vstring.h(operator==(const __versa_string<_CharT, std::char_traits<_CharT>, std::allocator<_CharT>, _Base>&, const __versa_string<_CharT, std::char_traits<_CharT>, std::allocator<_CharT>, _Base>&)): Add. (operator!=): Forward to operator==. * include/ext/sso_string_base.h (_M_compare): Remove. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/basic_string.h trunk/libstdc++-v3/include/ext/sso_string_base.h trunk/libstdc++-v3/include/ext/vstring.h
Fixed for 4.3.0.