2

Consider the following code:

#include <algorithm>
#include <iostream>
#include <vector>

struct A {
   int val;

   bool operator<(const A& other) const {
      std::cout << "operator\n";
      return val < other.val;
   }
};

void swap(A& a, A& b) {
   std::cout << "foo\n";
   std::swap(a.val, b.val);
}

int main()
{
   std::vector<A> a(2);
   a[0].val = 10;
   a[1].val = -1;

   std::sort(a.begin(), a.end());
}

C++11's std::sort places ValueSwappable requirements on the iterator arguments, move semantics and nothing else, implying that std::sort is "guaranteed" to perform a swap if elements need to be moved around. And 17.6.3.2/3 suggests that my overload definitely ought to be picked in this case.

  • Is this correct?

clang 3.1 SVN's libc++ picks my swap (that is, I see "foo"); GCC 4.6.3's libstdc++ does not.

  • Is this a GCC bug (assuming my standard interpretation is correct)? Or am I missing something?
Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • **Note:** I suppose [this way of `swap`ping is not recommended](http://stackoverflow.com/questions/11562/how-to-overload-stdswap), but I'd still like to know what's going on here. – Lightness Races in Orbit Mar 02 '12 at 19:14
  • Looks like ADL is not being used to find your overloaded version of `swap` with gcc, where-as clang is using ADL. There were some comments on the thread you pointed to that show that the use of ADL for the look-up of `swap` by `std::sort` is not a defined standard among compilers. – Jason Mar 02 '12 at 19:27
  • @Jason: Why would ADL be involved at all for a free function in the global namespace? – Lightness Races in Orbit Mar 02 '12 at 19:31
  • 1
    Howard Hinnant's and Dave Abrahams' answers are recommending exactly the method of overloading swap that you're using. I believe the accepted answer on that thread is not the best option. – bames53 Mar 02 '12 at 19:45
  • @LightnessRacesinOrbit the global namespace still counts as a namespace for ADL. – bames53 Mar 02 '12 at 19:46
  • @bames53: OK, but it shouldn't be _required_ to find a function in the global namespace, since they're all already in scope, no? – Lightness Races in Orbit Mar 02 '12 at 19:47
  • @LightnessRacesinOrbit No. In this case the template does overload resolution using the names available at template declaration time (not instantiation time) plus names found by ADL at instantiation time. http://ideone.com/Phah9 – bames53 Mar 02 '12 at 19:57

2 Answers2

6

C++11's std::sort places ValueSwappable requirements on the iterator arguments, move semantics and nothing else, implying that std::sort is "guaranteed" to perform a swap if elements need to be moved around.

I don't see that guarantee. Who says std::sort cannot use move semantics instead of swaps? In fact, after browsing the standard for the verbatim specification, I believe this is exactly what happens:

Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable (Table 22).

Note that the iterators shall be ValueSwappable, not the elements they point to.

fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • @FredOverlow: Well, the elements still have to be valid. So swaps have to come into it somehow, no? _[edit: and the range has to remain at its existing location in memory, IIRC]_ Though your answer has made me realise that the issue _might_ be that if `std::sort` is doing moves to swap, I should perhaps be taking rvalue refs into my `swap` function? – Lightness Races in Orbit Mar 02 '12 at 19:43
  • No, `swap` does not take rvalue references. You may be fooled into thinking that the basic operation of sorting algorithms is swapping elements, but if you look at the actual implementation of `std::sort`, chances are you won't find a single call to `swap`. (For example, heap sort is not based on swaps.) What happens when you provide a move constructor and move assignment operator that print to the console? They should be invoked, no matter if `sort` is implemented in terms of `swap` or not. – fredoverflow Mar 02 '12 at 19:49
  • I'm guess I'm confused as to how `std::sort` could possibly work at all, then. Where can values move to if not to some place else in the given range? Thus requiring a swap? – Lightness Races in Orbit Mar 02 '12 at 19:52
  • Values can simply move into (and out of) local variables. One phase of a heap sort could result in the following moves, for example: `T local_variable = std::move(a[1]); a[1] = std::move(a[2]); a[2] = std::move(a[4]); a[4] = std::move(a[8]); a[8] = std::move(local_variable);` – fredoverflow Mar 02 '12 at 19:59
  • Fair enough; I guess it's an "optimisation" on single-step swaps, when you have a chain to do. So are we concluding that `std::sort` needn't invoke `swap` after all? – Lightness Races in Orbit Mar 02 '12 at 20:01
  • Since 25.4.1.1 doesn't mention `swap` anywhere, I do conclude that it is not required to be called, yes. – fredoverflow Mar 02 '12 at 20:03
6

I'm posting this as an answer because I don't have reputation to comment.

As @FredOverflow pointed out, libstdc++ uses move constructors and assignment operators when sorting. However, I find it strange that it doesn't use ADL for pre c++11 code so people can plug optimized swapping functions.

Pedro
  • 113
  • 7
  • 2
    Get some rep and start commenting :) –  Mar 02 '12 at 20:13
  • Whether or not calling `swap` is faster than a series of assignments in C++03 depends on the type and whether or not it specializes `std::swap` (or provides a `swap` function in their own namespace). This is probably very hard or even impossible to figure out at compile time. For example, introsorting a list of ints will be a lot slower with swaps instead of a series of assignments. – fredoverflow Mar 02 '12 at 20:14
  • But ADL is built-in in the compiler and the library implementers already use swap overloading in every collection. Exposing a swap plug would greatly help people that what to use containers with value semantics while keeping the code fast. – Pedro Mar 02 '12 at 20:21
  • @Pedro Again, using `swap` does *not* guarantee faster performance in all cases. If you sort a vector of strings, swapping certainly is faster than simple assignments. But if you sort a vector of "flat" values types, swapping can incur a lot of unnecessary overhead. The C++11 solution of using moves is optimal. – fredoverflow Mar 02 '12 at 20:24
  • But FredOverflow, people only overload when they are sure it's faster than the default swap. – Pedro Mar 02 '12 at 20:25
  • And how is the compiler supposed to know if `std::swap` has been specialized for a certain type? – fredoverflow Mar 02 '12 at 20:26
  • It can look at the signature of the available swap overloads and choose the one with the most specific argument types that match. I guess. – Pedro Mar 02 '12 at 20:29
  • Sure, overload resolution. But the problem is that if there is no `std::swap` specialization, then using `swap` for sorting is wrong from an efficiency perspective! So really, `std::sort` would have to look like `if (is_swap_specialized::value) { sort with swaps } else { sort with assignments }`, and as far as I know, this is impossible in C++. – fredoverflow Mar 02 '12 at 20:34