>>755
ベクタ/リストをソートするのに計算量的な差は特にない。
ソート済みのものに要素を挿入するのは一長一短あるが一般にはリストが有利な場合が多いな。
挿入自体のパフォーマンスに特化するなら場合はヒープのような木構造を使うのがベストだろうが。