ゲーム中でSTLのlistをdequeにしたところで詰まっていたら、GRAMさんにdequeは名前は同じ関数だけどlistと違って要素を追加するとイテレーターが死ぬのだと教えていただきました。
なんかすごい重要なことなのになぜか手持ちの分厚い参考書には載っていないという孔明の罠。
GRAMさん曰く、イメージが重要なのだそうで、各コンテナのイメージや特徴を教えていただきました。
自分のためのメモや、他の誰かの助けになればと思ってここに載せます。

vectorはnewででっかい領域を確保しておいて、先頭から要素​を順番に足していく。
だから最初に確保した領域を超えて追加しようとすると、全要素を移動​させる羽目になることがある。
よってpush_backをした後は全イテレーターが無効になる。

dequeは小さな領域にいくつかの要素をまとめて入れておく。
こうすることで、一定時間で先頭に足すこともできるようになったが、
追加とさらに削除の時にもイテレーターが死ぬようになってしまう

listは一つの要素ごとに領域が確保されてる感じ。
だから一つ一つは削除してもほかのものに影響しないけれど、バラバラ​に保存されてるからアクセスは先頭か末尾からめぐっていくか、イテレーターで直接場所を記録しておくしかない

mapとかsetはvectorとlistの中間をとったような感じ​ですかね？
一定時間の削除も一定時間のアクセスも捨てる代わりに、双方が苦手と​してるところは完全に補い合ってます
一定時間の追加もできませんけど、どの操作も比較的高速です。（要素​数NとしてlogNに比例して時間が伸びる）

h2so5さんによる追加情報
そういえば、vectorは最終的な要素数が分かっていてreser​veすれば、push_backしてもイテレータは死にませんよね