В чем разница между list.sort и std :: sort? - PullRequest
Новая
       10

В чем разница между list.sort и std :: sort?

9 голосов
/ 05 ноября 2011

Я пытаюсь скомпилировать следующий код, используя clang, но получил следующую ошибку.

Мне интересно, почему бы использовать sort из класса list, но не 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: ошибка: недействительная операнды к бинарному выражению ('iterator_type' (он же 'std :: _ List_iterator>') и 'iterator_type') {return __y.base () - __x.base (); } * +1010 *

1 Ответ

13 голосов
/ 05 ноября 2011

std::sort требует произвольного доступа итераторов, которые std::list не предоставляет. Следовательно, std::list и std::forward_list реализуют свои собственные функции-члены для сортировки, которые работают со своими более слабыми итераторами. Гарантии сложности этих функций-членов хуже, чем у более эффективного общего алгоритма. [К сожалению: см. Комментарии.]

Более того, функции-члены могут воспользоваться преимуществом особого характера структуры данных списка, просто перекомпоновав узлы списка, в то время как стандартный алгоритм должен выполнить что-то вроде swap (или что-то в этом роде), что требует объекта строительство, назначение и удаление.

Обратите внимание, что remove() является аналогичным случаем: стандартный алгоритм представляет собой просто некоторую перестановку, возвращающую итератор, тогда как функция-член list выполняет поиск и фактическое удаление всего за один раз; снова благодаря возможности воспользоваться знанием внутренней структуры списка.

...