55

別の質問が次の考えに影響を与えました。

容量を増やすときにすべての要素を移動する必要がありますstd::vector<T> か?

私が理解している限り、標準的な動作は、基礎となるアロケーターが新しいサイズのチャンク全体を要求し、次に古い要素をすべて移動し、古い要素を破棄してから古いメモリの割り当てを解除することです。

この動作は、標準のアロケータ インターフェイスを考えると、唯一可能な正しい解決策のようです。しかし、アロケーターを修正して、 a を返し、基になる にマップできるreallocate(std::size_t)関数を提供することは理にかなっているのでしょうか? これの利点は、OS が割り当てられたメモリを実際に拡張できる場合、移動がまったく発生しないことです。ブール値は、メモリが移動したかどうかを示します。pair<pointer, bool>realloc()

(std::realloc()拡張できない場合はデータをコピーする必要がないため、最良の選択ではない可能性があります。したがって、実際には のようなものが必要ですextend_or_malloc_new()。編集:おそらくis_pod-trait ベースの特殊化により、実際のrealloc,そのビット単位のコピーを含みます。一般的にはそうではありません。)

チャンスを逃したようです。最悪の場合、常にreallocate(size_t n)asを実装できるreturn make_pair(allocate(n), true);ため、ペナルティはありません。

この機能を C++ にとって不適切または望ましくないものにする問題はありますか?

おそらく、これを利用できる唯一のコンテナは ですがstd::vector、これも非常に便利なコンテナです。

更新: 明確にするための小さな例。現在resize()：

pointer p = alloc.allocate(new_size);

for (size_t i = 0; i != old_size; ++i)
{
  alloc.construct(p + i, T(std::move(buf[i])))
  alloc.destroy(buf[i]);
}
for (size_t i = old_size; i < new_size; ++i)
{
  alloc.construct(p + i, T());
}

alloc.deallocate(buf);
buf = p;

新しい実装:

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);

if (pp.second) { /* as before */ }
else           { /* only construct new elements */ }
4

3 に答える 3

45

std::vector<T>容量が不足すると、新しいブロックを割り当てる必要があります。理由を正しく説明しました。

IMOアロケータ インターフェイスを拡張することは理にかなっています。私たちのうち 2 人が C++11 に対応しようとしましたが、サポートを得ることができませんでした: [1] [2]

これを機能させるには、追加の C レベル API が必要になると確信しました。私もそれに対するサポートを得ることができませんでした: [3]

于 2011-11-03T23:49:22.043 に答える
10

ほとんどの場合、メモリを拡張するreallocのではなく、別のブロックを割り当ててコンテンツを移動します。これは、最初に C++ を定義するときに考慮されたものであり、現在のインターフェイスはより単純であり、一般的なケースでは効率が低下しないと判断されました。

実生活では、実際に成長reallocできるケースはほとんどありません。プール サイズが異なる実装では、新しいサイズ (サイズは幾何学的に大きくなる必要があることに注意してください) が別のプールに分類される可能性があります。どのメモリ プールからも割り当てられていない大きなチャンクの場合でも、より大きなサイズの仮想アドレスが空いている場合にのみ拡大できます。mallocvector

whileを移動せずにメモリを拡張reallocできる場合もありますが、完了するまでに、メモリが既に移動(ビット単位の移動) している可能性があり、そのバイナリ移動により、POD 以外のすべての型で未定義の動作が発生することに注意してください。アロケーターの実装 (POSIX、*NIX、Windows) で、システムが成長できるかどうかをシステムに問い合わせることができるかどうかはわかりませんが、移動が必要な場合は失敗します。realloc

于 2011-11-03T23:36:43.647 に答える
0

はい、その通りです。標準のアロケータインターフェイスでは、memcpy'ableタイプの最適化は提供されていません。

ブースト型特性ライブラリを使用して型をmemcpyできるかどうかを判断することは可能です（それらがそのまま提供するのか、ブースト型に基づいて複合型弁別器を構築する必要があるのか​​はわかりません）。

とにかく、realloc()1つを利用するには、おそらくこの最適化を明示的に利用できる新しいコンテナタイプを作成します。現在の標準的なアロケータインターフェースでは、それは不可能のようです。

于 2011-11-03T23:42:09.263 に答える