12

I am trying to compile the following code using clang but got the following error.

I am wondering why using sort from the list class would work, but not std::sort.

#include <list>
#include <iostream>

int main(){
    std::string strings[] = {"hello", "nihao", "byebye", "yo"};
    std::list<std::string> cars(strings, strings+sizeof(strings) / sizeof(char **));

    // cars.sort(std::less<std::string>()); // compiles fine and produce a sorted list

    std::sort(cars.rbegin(), cars.rend(), std::less<std::string>() ); // this one won't compile

    for (std::list<std::string>::iterator it = cars.begin(); it != cars.end(); ++it)
        std::cout << *it << " - ";

    std::cout << std::endl;
    return 0;
}

/usr/include/c++/4.2.1/bits/stl_iterator.h:320:25: error: invalid operands to binary expression ('iterator_type' (aka 'std::_List_iterator >') and 'iterator_type') { return __y.base() - __x.base(); }

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
Negative Zero
  • 215
  • 2
  • 8

1 Answers1

18

std::sort requires random access iterators, which std::list does not provide. Consequently, std::list and std::forward_list implement their own member functions for sorting which work with their weaker iterators. The complexity guarantees of those member functions are worse than those of the more efficient general algorithm.[Whoops: see comments.]

Moreover, the member functions can take advantage of the special nature of the list data structure by simply relinking the list nodes, while the standard algorithm has to perform something like swap (or something to that effect), which requires object construction, assignment and deletion.

Note that remove() is a similar case: The standard algorithm is merely some iterator-returning rearrangement, while the list member function performs the lookup and actual removal all in one go; again thanks to being able to take advantage of the knowledge of the list's internal structure.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • The complexity guarantees are not worse. The member functions are "approximately N log N comparisons", whereas the algorithm is "O(N log N) comparisons". This is as you'd expect considering that the member functions are going to use merge sort, and `std::sort` is likely to use some kind of intro-sort, falling back to heapsort. – Steve Jessop Nov 05 '11 at 00:35
  • @Steve: Ah, indeed, a flat-out misconception on my part. The standard does say though that the list function uses N log N comparisons, while the standard algorithm is "O(N log N)". Same asymptotics, but I suppose the constants are worse for the list version. – Kerrek SB Nov 05 '11 at 00:51
  • Maybe the constants are worse, but remember that the standard complexity guarantees only care about number of comparisons, whereas one of the major performance factors when comparing merge/quick/heapsorts is locality of reference. So the constants applied to the comparison part of it aren't necessarily the major performance issue. I don't know what the worst-case number of comparisons is for heapsort, whether it's more or less than N log N, but N log N is the worst case for mergesort. And of course the expected case of introsort is overall faster runtime than the expected case of heapsort. – Steve Jessop Nov 05 '11 at 01:02
  • @SteveJessop: I'd imagine that simply because you need to walk the iterators one by one you'll have a greater overall overhead factor, no matter which specific algorithm -- though perhaps I'm now confusing binary searching with sorting. Maybe the advantage of random access iterators isn't actually that great after all... – Kerrek SB Nov 05 '11 at 01:04
  • 1
    Merge sort also does approximately N log N iterator increment operations (in fact, it does one increment per comparison, for fairly simple reasons), which is fine, although the locality depends entirely on how the list was constructed and vagaries of the allocator. The reason merge sort is so terrific for linked lists is just that it requires no extra memory, whereas merging arrays does. As with any sorting algorithm, to get a feel for it perform it manually on a deck of cards - you don't feel that you're missing random-access iterators :-) – Steve Jessop Nov 05 '11 at 01:10
  • @SteveJessop: That's a great suggestion, especially since it fits very nicely into an entirely independent problem I was after concerning educational use of a deck of cards! But let me clarify: Is the specialness of `list` implementation in the fact that nodes can be relinked without moving objects? That would be a much more useful explanation! – Kerrek SB Nov 05 '11 at 01:16
  • 1
    Oops, hang on, I'm only thinking of the actual merge, sorry, which does `2*k` increments to merge two blocks of size `k`. There's some extra incrementing needed to divide the data into "halves". And yes, re-linking nodes helps when the elements are large. Observe that *insertion sort*, with a binary search for the insertion point, only requires O(N log N) comparisons, it's the element-copying that's the killer ;-) – Steve Jessop Nov 05 '11 at 01:19
  • Sorry, in case this is becoming unclear, I mean that insertion sort of an array requires only O(N log N) comparisons, and hence meets the complexity requirement stated in the standard, provided you perversely choose to read it "O(N log N) comparisons plus unspecified additional time", rather than as I think it was intended: "O(N log N) comparisons *is the bounding factor on time*". Insertion sort of a linked list can be weaselled the same way, come to think of it, it's just that binary search on a linked list is clearly a farce... – Steve Jessop Nov 05 '11 at 01:28
  • @SteveJessop: Well, most notably, you shouldn't get *any* element constructor/destructor calls in the list algorithm, while you should get plenty in the standard algorithm! – Kerrek SB Nov 05 '11 at 01:28
  • Btw, `swap` doesn't necessarily require *much* object construction, assignment and deletion. You'd hope that for any type we care about, the user has implemented an efficient swap. So normally we're constructing a few temporary pointers and other built-in types, not expensive allocated resources. But that efficiency is of course limited if the size of the object is big. – Steve Jessop Nov 05 '11 at 01:39
  • @SteveJessop: I just made some tests with my trusted test class that prints out everything that's done to it, and it appears that GCC 4.6.1 doesn't use `swap` during `std::sort` and `std::remove`. It's just move-construct and move-assign everywhere. (And completely silent in `list::sort()`, and destruction only in `list::remove()`.) – Kerrek SB Nov 05 '11 at 01:44
  • @TomalakGeret'kal: thanks :-) And no complaints about semicolon abuse? – Kerrek SB Nov 05 '11 at 01:51
  • @KerrekSB: No abuse detected in your answer (though I didn't check the comments yet!) – Lightness Races in Orbit Nov 05 '11 at 01:53
  • @TomalakGeret'kal: It'd be in the question, final sentence -- I'm happy I pass your muster :-) Bedtime now! – Kerrek SB Nov 05 '11 at 01:56
  • @KerrekSB: Oh, god, there it is >. – Lightness Races in Orbit Nov 05 '11 at 01:59