Sorting a std::vector<std::pair<std::string, int> > is very slow because std::swap is not used for switching strings. std::swap for every std::pair should use two std::swap for the components of the pair. The following test program shows that this is currently not the case: #include <iostream> #include <algorithm> #include <vector> class A { public: A(int a) : val(a) { std::cout << "Constructing with: " << a << "\n"; } A(A const & a) : val(a.val) { std::cout << " Copy constructor from: " << a.val << "\n"; } A & operator=(A const & a) { val = a.val; std::cout << "Assignment from: " << a.val << "\n"; return *this; } ~A() { std::cout << "Destructing " << val << "\n";} public: int val; }; namespace std { void swap(A & a, A & b) { std::cout << "SWapping: " << a.val << "/" << b.val << "\n"; std::swap(a, b); } } int main() { std::pair<A, int> f(A(10), 2); std::pair<A, int> s(A(20), 3); std::swap(f, s); }
I agree with you, but unfortunatly the standard doesn't allow std::swap to be defined for std::pair. Stupid I know. C++0x does require that.
Could you point me to the part in the standard that forbids this? If this is really forbidden an additional level of indirection should help. Just call an swap_impl(a, b) from std::swap and define swap_impl for std::pair.
Sorry, I should have been clearer. the standard forbids this overload of swap by not listing it, unlike most other standard library types, which is lists an overload for. Personally, I'd be happy to just add the overload, but it wouldn't surprise me if it somehow broke someone's code, who had defined their own pair swap, or incorrectly defined swap on one of the members of their pair, although I don't have a good example on me. You can get pair swapping by the very heavy hammer of using a very recent release and -std=g++0x
Ok. But what is the reason for not using a __swap_impl within the current standard?
Created attachment 16874 [details] Proposed implementation of std::swap Here is a proposal on how std::swap could be improved for std::pair.
The __swap_impl idea makes sense but note that user code can tell it from the "standard" one when something throws. All in all, given that C++0x will be Ok wrt these issues, I'm not sure we want to attempt something in C++03 mode. By the way, as far as our specific implementation of std::string is concerned, typically I would not expect a huge performance improvement, thanks to copy-on-write. Do you have some numbers?
Agree, this is not a bug in the implementation, so think this is INVALID. Resolved in C++0x. We should document this known wart in C++03 std::pair (maybe add FAQ item?) Propose changing the Summary to: document std::pair vs. std::swap and mark as minor.
Ok...
Subject: Bug 38466 Author: paolo Date: Wed Jan 7 13:00:48 2009 New Revision: 143154 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=143154 Log: 2009-01-07 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/38466 * include/bits/stl_pair.h: Document C++03 pair vs swap. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/stl_pair.h
Done.