Std :: sort without copying

Question

Suppose I have a vector of objects, where:

• Copy design and appointments are expensive
• By default, building and replacing two objects is cheap.

This seems quite standard for objects with links to big data - for example, vector vectors.

Question Is there a way to sort this vector using std::sort or some other sorting procedure from the standard library so that there is no copy, but swap is used instead? I am looking for a solution before c++0x ( without moving semantics ).

Overloading std::swap seemed like the first natural attempt, and it helps a little, but it gets rid of only a small part of the copy.

Note : gcc behavior example

To sort 100 81 64 49 36 25 16 9 4 1 0 1 4 9 16 25 36 49 64 81 , my gcc std :: sort calls 19 copy constructors, 92 destinations and 6 swaps.

Answer 1

 // C++03 solution won't work with arrays and some other custom containers. // Mostly drop this block: #include <type_traits> #include <vector> #include <algorithm> #include <iostream> namespace aux { using std::begin; using std::end; template<typename C> auto adl_begin( C&& c )->decltype( begin(c) ); template<typename C> auto adl_end( C&& c )->decltype( end(c) ); template<typename C> struct container_traits: std::iterator_traits< typename std::decay< decltype( aux::adl_begin( *(C*)nullptr ) ) >::type > { typedef typename std::decay< decltype( adl_begin( *(C*)nullptr ) ) >::type iterator_type; }; } // C++03 solution won't work with arrays. Inside std::less, use Container::value_type: template< typename Container, typename Comparison = std::less< typename aux::container_traits<Container>::value_type > > void indirect_sort_then_swap( Container& c, Comparison&& comp = Comparison() ) { typedef aux::container_traits<Container> con_traits; typedef typename con_traits::value_type value_type; typedef typename con_traits::iterator_type iterator_type; std::vector< iterator_type > indirect; { // C++03 solution can use c.begin(), but will not work with arrays: using std::begin; using std::end; auto begin_ = begin(c); auto end_ = end(c); for( auto it = begin_; it != end_; ++it ) { indirect.push_back( it ); } } // In C++03, write a functor class that does this: auto indirect_sort = [&comp]( iterator_type const& left, iterator_type const& right )->bool { return comp(*left, *right); }; std::sort( indirect.begin(), indirect.end(), indirect_sort ); // at this point, indirect is a vector with the contents of c sorted by iterator: // a hard part remains, namely to take this information and sort c with minimal swaps // That is hard. I will instead create an easy approach, namely create an empty // copy of c full of empty elements, and directly swap the correct entry of c into // each slot, then I swap c with its copy. // the downside is that my container now needs to support push_back. Oh well. Container c2; // C++03 solution cannot use auto here. But we know the type of indirect: for (auto it = indirect.begin(); it != indirect.end(); ++it) { // See previous comment auto itv = *it; c2.push_back( value_type() ); using std::swap; swap( *itv, c2.back() ); } // by this point, the contents of c have been swap-moved to c2 // swap them back: { using std::swap; swap( c, c2 ); } } int main() { std::vector<int> foo; foo.push_back(7); foo.push_back(3); indirect_sort_then_swap(foo); for (auto i:foo) { std::cout << i << "\n"; } } 

something like the above is a viable approach. I wrote a bunch of this in C ++ 11, but included comments on how to cut out excess C ++ 11 stuff (in some cases this simplifies the code, but removes the ability to handle some container-like stuff).

The main idea is to sort the vector of iterator in the source container. Then we create a temporary container, add trivial value_type , swap those trivial value_type with the correct data from the original container (as determined by vector sorted iterator s), then swap this temporary container for our original container.

There are many suggestions, but hopefully from cheap things.

For this to work, the data you sort must be trivial. For this to be effective, the data you work with when trivially constructed must be cheap and swap must be efficient.

I tried to make it as ADL friendly as I can, because I think this is good practice.

Answer 2

Heap-sort is a sorting that is unstable (the order of equivalent elements may change during sorting). I answered another similar question , where I myself did a bunch of sorting ( PasteBin ), but you can find better and more flexible implementations there.

The conclusion was that g ++ std::sort used 35 copies, 19 jobs, 10 swap and 35 delete (a total of 99 operations) for 20 elements, my heap sorting had 62 swaps and nothing more.

I just came across a stable view that only uses swap https://stackoverflow.com/a/464832/232 . I did not look deeper into it.