[解決済み] std::list::reverse の計算量が O(n) であるのはなぜですか？

質問

の逆機能はなぜですか？ std::list のクラスは線形実行時間なのでしょうか？2重リンクリストの場合、逆関数はO(1)であるべきだったと思うのですが。

2重リンクリストの反転は、先頭と末尾のポインタを入れ替えるだけでよいはずです。

どのように解決するのですか？

仮の話です。 reverse は、もしかしたら O(1) . また、リンクリストの方向が現在、リストが作成された元の方向と同じか反対かを示すブール値のリストメンバーがあったかもしれません（再び仮定的に）。

残念ながら、その場合、基本的に他のすべての操作のパフォーマンスが低下します（漸近的な実行時間は変わらないとはいえ）。各操作において、リンクの "next"または "prev"のポインターに従うかどうかを考慮するために、ブール値を参照する必要があります。

これは比較的まれな操作と考えられていたため、規格（実装を指示するのではなく、複雑さのみを指示する）は、複雑さを線形にすることができると指定しました。これにより、"next"ポインターは常に同じ方向を明確に意味するようになり、一般的なケースの操作が高速化されました。