| 4890 | } |
| 4891 | |
| 4892 | template <typename I, typename Pred, typename T> void insertion_sort(I begin, I end, const Pred& pred, T*) |
| 4893 | { |
| 4894 | assert(begin != end); |
| 4895 | |
| 4896 | for (I it = begin + 1; it != end; ++it) |
| 4897 | { |
| 4898 | T val = *it; |
| 4899 | |
| 4900 | if (pred(val, *begin)) |
| 4901 | { |
| 4902 | // move to front |
| 4903 | copy_backwards(begin, it, it + 1); |
| 4904 | *begin = val; |
| 4905 | } |
| 4906 | else |
| 4907 | { |
| 4908 | I hole = it; |
| 4909 | |
| 4910 | // move hole backwards |
| 4911 | while (pred(val, *(hole - 1))) |
| 4912 | { |
| 4913 | *hole = *(hole - 1); |
| 4914 | hole--; |
| 4915 | } |
| 4916 | |
| 4917 | // fill hole with element |
| 4918 | *hole = val; |
| 4919 | } |
| 4920 | } |
| 4921 | } |
| 4922 | |
| 4923 | // std variant for elements with == |
| 4924 | template <typename I, typename Pred> void partition(I begin, I middle, I end, const Pred& pred, I* out_eqbeg, I* out_eqend) |
no test coverage detected