C++ リストは連結リストです。したがって、要素は次のように配置されます。
head <--> 1 <--> 2 <--> 3 <--> 4 <--> 5
したがって、3 を削除したい場合は、ポインターをシャッフルするだけです。3 を消去したいので、2 のポインターを 4 に移動する必要があります。この場合、3 まで移動する必要があります (要素を見つけます)。二重にリンクされたリストであり、削除する要素をすでに特定しているため、時間の複雑さは最悪の場合 O(1) になります。
ただし、一方で c++ ベクトルは単なる配列です。したがって、ベクトル要素の削除は、配列からの要素の削除に続きます。この場合、O(1) の複雑さで消去する要素を見つけることができます。ただし、それを消去するには、すべての要素を左シフトして、作成されたボイドを削除する必要があります。したがって、複雑さは O(n) 最悪の場合です。口頭では、複雑さは「n - 削除する要素のインデックス」のようなものになります。
リストは、O(1) の削除の複雑さとベクトル O(n) 漸近を生成します。ただし、リストには、各要素のポインターを維持するための追加のオーバーヘッドがあります (全体的に O(2n) スペースが追加されます)。