Почему std :: list :: reverse имеет сложность O (n)?

Question

Почему обратная функция для класса std::list в стандартной библиотеке C++ имеет линейное время выполнения? Я бы подумал, что для двусвязных списков обратная функция должна быть O (1).

Обращение к двусвязному списку должно включать в себя включение головы и хвостовых указателей.

Answer 1

Гипотетически, reverse могло бы быть O (1). Там (опять же гипотетически) мог быть логическим членом списка, указывающим, является ли направление связанного списка в настоящее время тем же или противоположным, что и исходное, в котором был создан список.

К сожалению, это снизит производительность практически любой другой операции (хотя и без изменения асимптотического времени выполнения). В каждой операции необходимо проконсультироваться с булевым, чтобы рассмотреть вопрос о том, следует ли следовать указателю «next» или «prev» ссылки.

Поскольку это, по-видимому, считалось относительно редкой операцией, стандарт (который не диктует реализацию, только сложность), указывает, что сложность может быть линейной. Это позволяет «следующим» указателям всегда означать одно и то же направление однозначно, ускоряя обычные операции.

Answer 2

Потому что он должен пересекать каждый узел (n всего) и обновлять свои данные (шаг обновления действительно O(1)). Это делает всю операцию O(n*1) = O(n).

Answer 3

Это может быть O (1), если список будет хранить флаг, который позволяет подкачку смысл «prev» и «next» указатели каждый узел имеет. Если реверсирование списка будет частой операцией, такое добавление может быть действительно полезным, и я не знаю ни одной причины, по которой его реализация будет запрещена действующим стандартом. Однако, имея такой флаг сделал бы обычный обходом из списка более дорогих (если только постоянным множителем), потому что вместо

current = current->next; 

в operator++ из списка итератора, вы получите

if (reversed) 
    current = current->prev; 
else 
    current = current->next; 

, который вы не можете легко добавить. Учитывая, что списки обычно пересекаются гораздо чаще, чем они меняются, было бы очень неразумно для стандарта мандат этой техники. Поэтому для обратной работы допускается линейная сложность. Есть ли к сведению, однако, что т ∈ O (1) ⇒ т ∈ O ( п) так, как уже упоминалось ранее, реализации вашей «оптимизации» технически будет разрешено.

Если вы используете Java или аналогичный фон, вы можете задаться вопросом, почему итератору необходимо каждый раз проверять флаг. Можем ли мы вместо этого иметь два разных типа итератора, оба из которых основаны на общем базовом типе, и имеют std::list::begin и std::list::rbegin полиморфно возвращают соответствующий итератор? Хотя это возможно, это еще больше ухудшит ситуацию, потому что продвижение итератора теперь будет косвенным (трудно встроенным) вызовом функции.В Java вы платите эту цену в любом случае, но опять же, это одна из причин, по которой многие люди достигают C++, когда производительность критическая.

Как отметили Benjamin Lindley в комментариях, поскольку reverse не допускается недействительной итераторы, единственный подход, разрешенный стандарт, кажется, чтобы хранить указатель обратно в список внутри итератора, который вызывает двойную косвенную память доступ.

Answer 4

Несомненно, поскольку все контейнеры, поддерживающие двунаправленные итераторы, имеют понятие rbegin() и rend(), этот вопрос спорный?

Тривиально создавать прокси-сервер, который меняет итераторы и обеспечивает доступ к контейнеру.

Это не-операция действительно O (1).

, такие как:

#include <iostream> 
#include <list> 
#include <string> 
#include <iterator> 

template<class Container> 
struct reverse_proxy 
{ 
    reverse_proxy(Container& c) 
    : _c(c) 
    {} 

    auto begin() { return std::make_reverse_iterator(std::end(_c)); } 
    auto end() { return std::make_reverse_iterator(std::begin(_c)); } 

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); } 
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); } 

    Container& _c; 
}; 

template<class Container> 
auto reversed(Container& c) 
{ 
    return reverse_proxy<Container>(c); 
} 

int main() 
{ 
    using namespace std; 
    list<string> l { "the", "cat", "sat", "on", "the", "mat" }; 

    auto r = reversed(l); 
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n")); 

    return 0; 
} 

ожидается выход:

mat 
the 
on 
sat 
cat 
the 

Учитывая это, мне кажется, что комитет по стандартизации не потребовалось время, чтобы поручить O (1) обратного упорядочения контейнер, потому что это необязательно, а стандартная библиотека в значительной степени основана на принципе обязательности только того, что строго необходимо, избегая дублирования.

Только мой 2c.

Answer 5

Только описание алгоритма. Представьте, что у вас есть массив с элементами, тогда вам нужно его перевернуть. Основная идея состоит в том, чтобы перебирать каждый элемент, изменяя элемент на первое положение до последней позиции, элемент на втором месте в предпоследнем положении и т. Д. Когда вы достигнете середины массива, вы измените все элементы, таким образом, в (n/2) итерациях, которые считаются O (n).

Answer 6

Это O (n) просто потому, что ему нужно скопировать список в обратном порядке. Каждая операция отдельного элемента - O (1), но во всех списках их n.

Конечно, есть некоторые операции с постоянным временем, связанные с настройкой пространства для нового списка и последующим изменением указателей и т. Д. Обозначение O не учитывает отдельные константы после включения n-фактора первого порядка.

Answer 7

Он также свопирует предыдущий и следующий указатели для каждого узла. То почему он принимает Linear. Хотя это можно сделать в O (1), если функция, использующая этот LL, также берет информацию о LL как входную, как, например, обращается ли она нормально или наоборот.