C++ 双方向リストクラス std::list 入門

双方向リストクラス std::list とは std::list とは C++ で標準に使用できる便利な双方向リストクラスでござるぞ。 「双方向リスト」とは、要素を格納するノードが前後のノードへのポインタを持ち、どの位置への挿入・削除でも O(1) と高速に処理できるコンテナクラスだぞ。 ※ 「コンテナクラス」とは、単一タイプ・データ構造の複数のデータを取り扱うためのクラスのことだぞ std::list と対比されるのは std::vector である。 vector は末尾への挿入・削除は O(1) と高速だが、それ以外の位置への挿入・削除は O(N) で、データ数に比例した処理時間を要してしまう。 その半面、どの位置のデータへも O(1) と高速にアクセス（参照・代入）することができる。 任意の位置へのアクセスをランダム・アクセスと呼ぶので、vector はランダム・アクセスが O(1