C + + STLアルゴリズムに関するNicolai Josuttisの本を読んでいます。 stable_sort（）のような多くのアルゴリズムでは、十分なメモリが利用可能であれば、アルゴリズムn * log（n）の複雑さを言います。そうでなければn * log（n）* log（n）です。私の質問は、どのようにメモリの使用量が複雑さに影響を与えますか？ STLはこのような状況をどのように検出しますか？アルゴリズムの複雑さにおけるメモリ使用の影響
gccのSTLを見るとinplace_mergeはstl_algo.hにあります。これは、入力と同じサイズのバッファを使用して、O（N）を使用したマージソートの従来のマージ実装です。このバッファは_Temporary_buffer、stl_tempbuf.hから割り当てられます。これによりget_temporary_bufferが呼び出され、最終的に新しいものが呼び出されます。例外がスローされると、例外が捕捉され、バッファはNULLになります。これは「十分でないメモリ」の場合です。その場合、マージは__merge_without_bufferで動作します。これはO（N lg N）です。再帰深度マージソートはO（lg N）であるため、バッファなしのバージョンでは "従来の" mergesort（バッファ付き）の場合はO（N lg N）、バージョンがない場合はO 。
+1。この標準は、十分なメモリと不十分なメモリの両方の場合の複雑さを25.3.4/7に保証しているため、すべての実装では何らかのメモリが十分にあるかどうかを判断する必要があります。彼らは 'new 'によって投げられた例外をキャッチすることによってそうするように拘束されていませんが、それはそれを実行する賢明な方法のようです。 :) –