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(); }
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With