0

私は少なくともおおよその答えに興味があります：

int n;
...
std::vector<void*> vectorOfPointers;
vectorOfPointers.reserve(n);

上記のプログラムは、どの数nまでO（1）で実行されますか？

3ギガバイトのメモリを搭載した32ビットUbuntuを実行し、他のプログラムを実行していないラップトップについて考えてみましょう。それは数十、数千、数百万ですか？そのような質問を評価できるようにするために、どのような情報を知る必要がありますか？実験を行わずに調べる方法はありますか？

私はオペレーティングシステムについて何も勉強したことがありませんが、私の想像では、オペレーティングシステムはたった2つのステップでメモリを割り当てます。チャンクを開始するためのポインターとチャンクの終わりのポインターを決定します。十分な大きさのメモリを取得するためにシステムを整理する必要がある場合があるため、状況はさらに複雑になる可能性があります。しかし、システムがこの1つのプログラムだけを実行していると仮定すると、必要な時間をどのように見積もることができますか？記憶の断片化以外に、考慮すべき他の側面はありますか？

編集：

申し訳ありませんが、質問を明確にしませんでした。予約を呼び出す前にベクトルが空であるため、データをコピーする必要がないことを考慮することが重要です。

4

3 に答える 3

2

を使用する場合、O（1）の複雑さに依存することはできませんreserve()。

複雑

コンテナのサイズが線形

（cppreferenceを参照）

基本的に、新しいメモリの割り当ては一定時間ですが、古い要素を前のメモリから新しいメモリにコピーする必要もあります（したがって、線形の複雑さ）。

したがって、空のベクトルでは、予約はおそらく一定の時間になりますが、標準が明示的にそれを示しているかどうかはわかりません。したがって、それはおそらく基礎となる実装に依存します（それを行わない理由が見当たらない場合でも）。

于 2013-01-19T08:16:44.147 に答える
2

C ++の観点からは、コードには時間がかかります（コンテナーの現在のO(1)サイズでは線形であり、この場合は常にゼロです）。

さて、あなたの質問は本当にmメモリのバイトを割り当てることの複雑さについてであるように思われます。それは、私は恐れていますが、特定されていません。

詳細については、メモリ割り当ての時間計算量を参照してください。

他の質問ですでに述べたことに加えて、複雑さのいくつかの層があります：

  • まず、malloc()内部データ構造を維持する必要があります。それを行うことの複雑さは特定されていませんが、時間malloc(m)がかからないことを願ってΘ(m)います。ただし、複雑さは、メモリの断片化などの他の要因に大きく依存する可能性があります。
  • 次に、malloc()OSに追加のメモリを要求する必要がある場合があります。ここでは、OSが割り当てるすべてのメモリページで何かを実行することを期待するのは不合理ではありません（たとえば、他の人の機密データが表示されないようにワイプします）。これが発生した場合、操作は確かにになりますΘ(m)。
于 2013-01-19T08:17:01.077 に答える
1

O(1)私が考えることができるのは、それが何もしないことを意味するstd::vector::reserve()ときだけです。n <= capacity()reserve()

于 2013-01-19T08:21:02.593 に答える