std::sort does not always call std::swap

by

For small ranges, std::sort implementations in GCC’s stdlibc++ (and other standard library implementations) recurs to insertion sort for performance reasons (it’s faster than quicksort / introsort on small ranges).

GCC’s insertion sort implementation in turn doesn’t swap via std::swap – instead, it moves whole ranges of values at a time, instead of swapping individually, thus potentially saving performance. The relevant part is here (bits/stl_algo.h:2187, GCC 4.7.2):

typename iterator_traits<_RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);

_GLIBCXX_MOVE is the same as std::move from C++11 and _GLIBCXX_MOVE_BACKWARD3 is std::move_backward – however, this is only the case if __GXX_EXPERIMENTAL_CXX0X__ is defined; if not, then these operations resort to copying instead of moving!

What this does is move the value at the current position (__i) to a temporary storage, then move all previous values from __first to __i one up, and then re-insert the temporary value at __first. So this performs n swaps in one operation instead having to move n values to a temporary location:

  first           i
+---+---+---+---+---+---+
| b | c | d | e | a | f |
+---+---+---+---+---+---+
                  |
  <---------------+


  first           i
+---+---+---+---+---+---+
| --> b-> c-> d-> e-> f |
+---+---+---+---+---+---+


  first           i
+---+---+---+---+---+---+
| a | b | c | d | e | f |
+---+---+---+---+---+---+
  ^

More Related Contents:

  1. c++ push reference node to stl list
  2. Why can’t I make a vector of references?
  3. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  4. Why do I get the same sequence for every run with std::random_device with mingw gcc4.8.1?
  5. Using custom std::set comparator
  6. When vectors are allocated, do they use memory on the heap or the stack?
  7. Nice way to append a vector to itself
  8. In STL maps, is it better to use map::insert than []?
  9. Why use non-member begin and end functions in C++11?
  10. std::fstream doesn’t create file
  11. Where can I get a “useful” C++ binary search algorithm?
  12. Relative performance of std::vector vs. std::list vs. std::slist?
  13. Stack-buffer based STL allocator?
  14. std::vector, default construction, C++11 and breaking changes
  15. How to read a growing text file in C++?
  16. Initial capacity of vector in C++
  17. std::vector iterator invalidation
  18. Non-copyable elements in vector
  19. How to pretty-print STL containers in GDB?
  20. How to make elements of vector unique? (remove non adjacent duplicates)
  21. How does overloading of const and non-const functions work?
  22. How can I use Standard Library (STL) classes in my dll interface or ABI?
  23. Does boost have a datatype for set operations that is simpler than the STL?
  24. How can i estimate memory usage of std::map?
  25. Memory allocation and deallocation across dll boundaries
  26. STL deque accessing by index is O(1)?
  27. Can std::vector emplace_back copy construct from an element of the vector itself?
  28. “Proper” way to store binary data with C++/STL
  29. C++ template function compiles in header but not implementation
  30. Insert into an STL queue using std::copy

Leave a Comment