musingstudio

I learnt recently that in the C++11 Standard, std::sort is required to have complexity O(N * log N) – not “on average N * log N with a worst case O(n^2)”, but guaranteed O(N * log N). This follows David Musser’s paper on Introspective Sorting and Selection.

Musser’s IntroSort uses QuickSort, but also monitors the number of partitions that have occurred. For example, one might use “median-of-3” to pick each pivot, but that could cause the O(N^2) behaviour if pathological sequence is encountered. In the paper, such a sequence is described by construction. IntroSort switches to HeapSort (which guarantees O(N * log N) performance) once the number of QuickSort partitions reaches 2 * log N. Musser proves that the overall algorithm performance remains O(N * log N).

As pointed out on StackOverflow, std::nth_element could be re-implemented with similar benefits:

Ideally exactly the same should apply std::nth_element but the ISO C++ 2011 standard has not tightened up the complexity requirements. So std::nth_element could be O(N * N) in the worst case.

A StackOverflow question asks why it is necessary to call std::move on a parameter when implementing a move constructor, given that the parameter is already declared T&&?

Named rvalue references are lvalues. Unnamed rvalue references are rvalues.

In other words, if you don’t explicitly move a into b X b = std::move(a); then you haven’t declared that you’ve finished with a, which is a named variable – so the compiler will call X’s copy constructor instead of X’s move constructor.

Chris Sharpe blogged an example of how marking operator bool() explicit neededn’t necessitate any overhead when using that type in a simple if condition:

An expression e can be implicitly converted to a type T if and only if the declaration T t=e; is well-formed, for some invented temporary variable t (8.5). Certain language constructs require that an expression be converted to a Boolean value. An expression e appearing in such a context is said to be contextually converted to bool and is well-formed if and only if the declaration bool t(e); is well-formed, for some invented temporary variable t (8.5). The effect of either implicit conversion is the same as performing the declaration and initialization and then using the temporary variable as the result of the conversion.

ISOCpp linked to a StackOverflow question about universal memorisation.