0

アセンブラー言語の経験が豊富で、古い習慣を失う人として、私は最近、c++03 と c++11 が提供しなければならない多くの機能を使用して C++ でプロジェクトを行いました (ほとんどはコンテナー クラスで、いくつかはブースト）。それは驚くほど簡単だった。コードのレビューとパフォーマンスのテストに移るにつれて、すべてのバイトがどのように操作されているかを正確に把握できていない経験豊富な担当者の中には、神経症を患う人もいると思います。

インスタンス メンバーが複数のベクトルとマップを含むクラスを定義しました。ベクトルやマップへの「ポインタ」ではありません。そして、オブジェクトがどれだけの連続したスペースを占めるか、またはこれらのコンテナを頻繁にクリアして再投入することでパフォーマンスにどのような影響があるかについて、まったくわからないことに気付きました。

インスタンス化されると、そのようなオブジェクトはどのように見えるでしょうか?

4

5 に答える 5

4

正式には、インターフェイスと複雑さに関して、標準で指定されている以外の実装上の制約はありません。実際には、すべてではないにしてもほとんどの実装は同じコード ベースから派生しており、かなり似ています。

vector の基本的な実装は 3 つのポインターです。ベクトル内のオブジェクトの実際のメモリは動的に割り当てられます。ベクターがどのように「成長」したかによって、動的領域に追加のメモリーが含まれる場合があります。3 つのポインタは、メモリの先頭、現在使用されている最後のバイトの後のバイト、および割り当てられた最後のバイトの後のバイトを指します。おそらく、実装の最も重要な側面は、割り当てと初期化が分離されていることです。ベクターは、多くの場合、オブジェクトを構築せずに必要以上のメモリを割り当て、必要な場合にのみオブジェクトを構築します。さらに、オブジェクトを削除したり、ベクトルをクリアしたりしても、メモリは解放されません。オブジェクトを破棄するだけで、これを反映するために使用済みメモリの末尾へのポインターを変更します。後で、

割り当てられたスペースの量を超えてオブジェクトを追加すると、ベクターは新しいより大きな領域を割り当てます。そこにオブジェクトをコピーし、古いスペースのオブジェクトを破棄して削除します。複雑さの制約のため、ベクトルは、サイズを固定量でインクリメントするのではなく、サイズに固定定数 (1.5 と 2 が最も一般的な係数) を掛けることによって、指数関数的に領域を拡大する必要があります。その結果、 を使用して空からベクターを拡張するpush_backと、再割り当てとコピーがあまり発生しなくなります。もう 1 つの結果は、ベクトルを空から大きくすると、最終的に必要なメモリのほぼ 2 倍を使用することになります。を使用して事前割り当てを行うと、これらの問題を回避できますstd::vector<>::reserve()。

マップに関しては、複雑さの制約と順序付けが必要であるという事実は、ある種のバランスの取れたツリーを使用する必要があることを意味します。私が知っているすべての実装では、これは古典的な赤黒ツリーです。各エントリは、データに加えて、2 つまたは 3 つのポインターとおそらくブール値を含むノードに個別に割り当てられます。

上記がコンテナの最適化されたバージョンに適用されることを付け加えるかもしれません。通常の実装では、最適化されていない場合、すべてのイテレーターをコンテナーにリンクするための追加のポインターが追加されます。これにより、コンテナーがイテレーターを無効にする何かを行ったときにマークを付けることができ、境界チェックを行うことができます。

最後に、これらのクラスはテンプレートであるため、実際にはソースにアクセスして見ることができます。(例外の安全性などの問題により、実装が私たちが望むよりも単純でなくなることがありますが、g++ または VC++ を使用した実装は、それほど理解しにくいものではありません。)

于 2013-08-24T23:18:26.793 に答える
3

Amapは二分木です (いくつかの種類がありますが、通常は赤黒木だと思います)、それmap自体にはおそらくポインタといくつかのハウスキーピング データ (要素数など) しか含まれていません。

他のバイナリ ツリーと同様に、各ノードには 2 つまたは 3 つのポインターが含まれます (「左右」ノード用に 2 つ、おそらく上の前のノードへのポインターが 1 つあり、前のノードの場所を見つけるためにツリー全体をトラバースする必要がなくなります)。 ） それは）。

一般にvector、通常の配列よりも著しく遅くなることはなく、ポインターを使用した可変サイズの配列の独自の実装よりも悪いことはありません。

于 2013-08-24T23:01:15.843 に答える
1

他の人の答えに、私が重要だと思ういくつかのことを追加したかっただけです.

まず、(私が見た実装では) デフォルトsizeof(std::vector<T>)は定数であり、3 つのポインターで構成されています。以下は、GCC 4.7.2 STL ヘッダーの関連部分からの抜粋です。

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
 ...
 struct _Vector_impl : public _Tp_alloc_type
 {
  pointer _M_start;
  pointer _M_finish;
  pointer _M_end_of_storage;
  ...
 };
 ...
 _Vector_impl _M_impl;
 ...
};

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
 ...
};

それが、3 つのポインターの由来です。彼らの名前は自明だと思います。しかし、アロケーターという基底クラスもあります。これで 2 番目のポイントに進みます。

次に、std::vector< T, Allocator = std::allocator<T>>メモリ操作を処理するクラスである 2 番目のテンプレート パラメーターを取ります。このクラス vector の関数を介してメモリ管理を行います。デフォルトの STL アロケータがありますstd::allocator<T>>。allocateなどの関数のみがあり、データメンバーはありません。destroyメモリ処理は に基づいていますnew/delete。ただし、独自のアロケーターを作成してstd::vector、2 番目のテンプレート パラメーターとして指定することはできます。std::vector提供する機能などの特定のルールに準拠する必要がありますが、メモリ管理が内部でどのように行われるかは、依存のロジックに違反しない限り、あなた次第です。sizeof(std::vector)上記の継承によってに追加されるいくつかのデータ メンバーが導入される可能性があります。また、「各ビットの制御」も提供します。

于 2013-08-24T23:46:09.357 に答える
0

基本的に、 avectorは、その容量 (割り当てられたメモリの合計) とサイズ (実際に使用される要素) と共に、配列への単なるポインタです。

struct vector {
    Item* elements;
    size_t capacity;
    size_t size;
};

もちろん、カプセル化のおかげで、これらすべてがうまく隠され、ユーザーは面倒な詳細 (再割り当て、必要に応じてコンストラクター/デストラクタを呼び出すなど) を直接処理することはありません。

クリアに関するパフォーマンスの問題については、ベクトルをクリアする方法によって異なります。

  • 一時的な空のベクトル (通常のイディオム) と交換すると、古い配列が削除されます。std::vector<int>().swap(myVector);
  • clear()またはを使用resize(0)すると、すべてのアイテムが消去され、割り当てられたメモリと容量は変更されません。

効率が気になる場合、考慮すべき主なポイントはreserve()、配列を事前に割り当て、無駄な再割り当てとコピー (または C++ 11 での移動) を回避するために (可能であれば) 事前に呼び出すことです。ベクトルに多くの項目を追加すると、大きな違いが生じる可能性があります (ご存知のように、動的割り当ては非常にコストがかかるため、削減するとパフォーマンスが大幅に向上します)。

これについてはまだまだ言いたいことがたくさんありますが、基本的な詳細を説明したと思います。特定の点についてさらに情報が必要な場合は、遠慮なくお尋ねください。

マップに関しては、通常、赤黒木を使用して実装されます。ただし、標準はこれを義務付けていません。機能と複雑さの要件のみを示しているため、法案に適合する他のデータ構造は問題ありません。RB ツリーがどのように実装されているかはわかりませんが、マップには少なくともポインターとサイズが含まれていると思います。

そしてもちろん、すべてのコンテナー タイプは異なります (たとえば、順序付けられていないマップは通常、ハッシュ テーブルです)。

于 2013-08-24T22:55:56.960 に答える