ダイナミックテーブルとC++vector
6280 ワード
ダイナミックテーブルとC++vector
最近の授業では、表の要素の挿入と削除に基づいて表のサイズを動的に調整できるダイナミックテーブル(dynamic table)を習ったばかりで、実際の応用を見てみたいと思っています.最初に思い出したのはC++のvectorで、直感的にはダイナミックテーブルの特性に最も合っています(事前にサイズを宣言する必要はありません.もちろん、宣言したいなら問題ありません.ダイナミック挿入と削除).しかし、次の記事では、vectorは完全なダイナミックテーブルではないことを示しています.なぜなら、メモリ占有量は要素の挿入と削除に伴って増加し、解放されないからです.
ソース:https://blog.csdn.net/qq_30835655/article/details/60762196
最近C++をもっと深く勉強するようになり、以前は気づかなかったことがたくさんありますが、重要な知識点を発見しました.この文章は主にvectorメモリのメカニズムと効率の問題を話します. vectorメモリ成長vectorすべてのメモリ関連の問題は、そのメモリ成長ポリシーに帰結することができます.vectorには、メモリ容量が増加するだけで減少しないという特徴があります.vectorには2つの関数があります.1つはcapacity()で、オブジェクトバッファ(vectorメンテナンスメモリ領域)が実際に申請した空間サイズを返し、もう1つのsize()で、現在のオブジェクトバッファに格納されているデータの個数を返します.vectorにとって、capacityは永遠にsize以上であり、アーカイブcapacityとsizeが等しい場合、vectorは拡張され、capacityは大きくなる.
例えばvectorで最もよく使われるpush_back操作、その全体の過程はどのようなメカニズムですか?この問題は面接でよく出ます.
この問題は実は簡単で、pushを呼び出しています.backの場合、現在の容量に心得要素(capacity=size)が入れられない場合、vectorはメモリを再申請し、前のメモリの要素を新しいメモリにコピーし、push_backの要素は新しいメモリにコピーされ、最後に元のvectorを解析し、元のメモリを解放します.したがって、このプロセスの効率は極めて低く、頻繁なメモリの割り当てを避けるために、C++は申請するたびにメモリが2倍に増加します.例えば、前が4だった場合、再申請後は8になります.もちろん、必ずしも倍増しているわけではありません.例えば、私のコンパイラ環境では、実測では0.5倍増加し、前は4で、再申請後は6です.
次に,この過程を簡単なプログラム例で観察した.
コンパイル環境:visual studio 2015
プログラム実行結果
プログラムの実行結果は簡単明瞭ですが、vectorの元の空間の分析は意外にも新しい要素のpush_です.backの前で発生し、ネット上の検索資料とは異なります.検証が必要で、読者が自分の環境でテストして、結果を観察することを望んでいます.メモリ解放前述したようにvectorのメモリ領域は増加するだけで減少しません.clear()とerase()をよく使う操作ですが、実際にはsize()を減少させただけで、データを消去してもcapacityを減少させることはありませんので、メモリ領域は減少しません.では、メモリスペースをどのように解放するか、正しい方法はswap()操作です.
標準テンプレートは次のとおりです.
以下の操作vector()を簡単に使用することもできる.swap(pointVec);//あるいはpointVec.swap(vector ())
swap交換テクニックはメモリ解放思想を実現する:vector()はvectorのデフォルト構造関数を使用して一時vectorオブジェクトを確立し、その一時オブジェクト上でswapメンバーを呼び出す.swap呼び出し後、元のvectorが占有した空間はデフォルト構造のオブジェクトの大きさに等しく、一時オブジェクトは元のオブジェクトvの大きさを持ち、その一時オブジェクトはすぐに分析される.これにより、その占有空間も解放される.std::vector ().swap(X)作用は{std::vectortemp(X);temp.swap(X);}に相当する.
交換後、tempは析出されます.
3.まとめてみると、vectorは動的配列ですが、本質的に配列と変わらず、頻繁に破棄して新築し、効率が低いので、正しいやり方はvectorを新築するときに適当な大きさを初期化し(笑)、配列の古い道に戻ります.しかし、その後もダイナミックに変化するのは便利で、使いやすい関数もたくさんあります.————————————————本文はCSDNブロガー「尹小贱」のオリジナル文章で、CC 4.0 BY-SAの著作権協定に従い、原文の出典リンクと本声明を転載してください.テキストリンク:https://blog.csdn.net/qq_30835655/article/details/60762196
したがってvectorのサイズは増加し、減少することはできません.vectorが使用するメモリ領域を解放するには、vectorコンテンツを交換する関数swapを使用する必要があります.空のコードブロック内のオブジェクトまたは匿名のオブジェクトと交換すると、一時的なオブジェクトが自動的に破棄され、ダイナミックテーブルの要件に完全に合致しません.もちろん、swapを手動で使用して回収スペースを使用しない場合、vectorオブジェクトは対応する関数の実行が完了した後も回収されます(上記のtempオブジェクトを参照).しかし、いくつかの再帰プロセスではスタックが爆発する可能性が高い場合や、他のメモリの使用が比較的大きい場合は、この問題を考慮する必要があります.
だから、これもなぜvectorにサイズを宣言しておけばvectorを使う効率が高いのかを説明しています.結局、宣言しなければ、要素が加わるにつれて、データがより大きな空間に移動するのも良い方法ではありません.
ダイナミックテーブルを実現したのはdeque、double-ended queue、両端キューで、私は多くの中国語のインターネット上の資料を調べて、本当ですか、それともC++中国語のドキュメントの上で最も簡潔で明瞭ですか.
ソース:https://zh.cppreference.com/w/cpp/container/deque
std::vectorとは逆にdequeの要素は接続されて格納されていない:典型的には、vectorの下付きアクセスは、単一に割り当てられた固定サイズ配列のシーケンスで追加の登録が追加され、これは、下付きアクセスが二次ポインタ解参照を行わなければならないことを示し、それに比べてvectorの下付きアクセスは1回のみ行われる.
dequeのストレージは、必要に応じて自動的に拡張および縮小されます.拡張dequeは拡張std::vectorより安いです.既存の要素を新しいメモリ位置にコピーすることはありません.一方、dequeは典型的には、より大きな最小メモリオーバーヘッドを有する.1つの要素のみを保持するdequeは、その内部配列全体(例えば、64ビットlibstdc++がオブジェクトサイズの8倍、64ビットlibc++がオブジェクトサイズの16倍または4096バイトの大きいもの)を割り当てる必要があります.
Dequeでよく見られる操作の複雑さ(効率)は、次のとおりです.ランダムアクセス-定数O(1) 最後または最初に要素を挿入または除去する-定数O(1) .要素の挿入または除去--線形O(n)
STLは面白いですが、最近ちょっと緊張しているので、ここまで検討しておきましょう.
最近の授業では、表の要素の挿入と削除に基づいて表のサイズを動的に調整できるダイナミックテーブル(dynamic table)を習ったばかりで、実際の応用を見てみたいと思っています.最初に思い出したのはC++のvectorで、直感的にはダイナミックテーブルの特性に最も合っています(事前にサイズを宣言する必要はありません.もちろん、宣言したいなら問題ありません.ダイナミック挿入と削除).しかし、次の記事では、vectorは完全なダイナミックテーブルではないことを示しています.なぜなら、メモリ占有量は要素の挿入と削除に伴って増加し、解放されないからです.
ソース:https://blog.csdn.net/qq_30835655/article/details/60762196
最近C++をもっと深く勉強するようになり、以前は気づかなかったことがたくさんありますが、重要な知識点を発見しました.この文章は主にvectorメモリのメカニズムと効率の問題を話します.
例えばvectorで最もよく使われるpush_back操作、その全体の過程はどのようなメカニズムですか?この問題は面接でよく出ます.
この問題は実は簡単で、pushを呼び出しています.backの場合、現在の容量に心得要素(capacity=size)が入れられない場合、vectorはメモリを再申請し、前のメモリの要素を新しいメモリにコピーし、push_backの要素は新しいメモリにコピーされ、最後に元のvectorを解析し、元のメモリを解放します.したがって、このプロセスの効率は極めて低く、頻繁なメモリの割り当てを避けるために、C++は申請するたびにメモリが2倍に増加します.例えば、前が4だった場合、再申請後は8になります.もちろん、必ずしも倍増しているわけではありません.例えば、私のコンパイラ環境では、実測では0.5倍増加し、前は4で、再申請後は6です.
次に,この過程を簡単なプログラム例で観察した.
コンパイル環境:visual studio 2015
#include
#include
using namespace std;
class Point
{
public:
Point()
{
cout << "construction" << endl;
}
Point(const Point& p)
{
cout << "copy construction" << endl;
}
~Point()
{
cout << "destruction" << endl;
}
};
int main()
{
Point test[10];
cout << "**************************" << endl;
vector arr;
for (int i = 0; i < 10; i++)
{
arr.push_back(test[i]);
cout << "capacity=" << arr.capacity() << ",size=" << arr.size() << endl;
cout << "--------------------------" << endl;
}
system("pause");
} プログラム実行結果
construction
construction
construction
construction
construction
construction
construction
construction
construction
construction
**************************
copy construction
capacity=1,size=1
--------------------------
copy construction
destruction
copy construction
capacity=2,size=2
--------------------------
copy construction
copy construction
destruction
destruction
copy construction
capacity=3,size=3
--------------------------
copy construction
copy construction
copy construction
destruction
destruction
destruction
copy construction
capacity=4,size=4
--------------------------
copy construction
copy construction
copy construction
copy construction
destruction
destruction
destruction
destruction
copy construction
capacity=6,size=5
--------------------------
copy construction
capacity=6,size=6
--------------------------
copy construction
copy construction
copy construction
copy construction
copy construction
copy construction
destruction
destruction
destruction
destruction
destruction
destruction
copy construction
capacity=9,size=7
--------------------------
copy construction
capacity=9,size=8
--------------------------
copy construction
capacity=9,size=9
--------------------------
copy construction
copy construction
copy construction
copy construction
copy construction
copy construction
copy construction
copy construction
copy construction
destruction
destruction
destruction
destruction
destruction
destruction
destruction
destruction
destruction
copy construction
capacity=13,size=10
--------------------------
プログラムの実行結果は簡単明瞭ですが、vectorの元の空間の分析は意外にも新しい要素のpush_です.backの前で発生し、ネット上の検索資料とは異なります.検証が必要で、読者が自分の環境でテストして、結果を観察することを望んでいます.
標準テンプレートは次のとおりです.
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}以下の操作vector()を簡単に使用することもできる.swap(pointVec);//あるいはpointVec.swap(vector ())
swap交換テクニックはメモリ解放思想を実現する:vector()はvectorのデフォルト構造関数を使用して一時vectorオブジェクトを確立し、その一時オブジェクト上でswapメンバーを呼び出す.swap呼び出し後、元のvectorが占有した空間はデフォルト構造のオブジェクトの大きさに等しく、一時オブジェクトは元のオブジェクトvの大きさを持ち、その一時オブジェクトはすぐに分析される.これにより、その占有空間も解放される.std::vector ().swap(X)作用は{std::vectortemp(X);temp.swap(X);}に相当する.
交換後、tempは析出されます.
3.まとめてみると、vectorは動的配列ですが、本質的に配列と変わらず、頻繁に破棄して新築し、効率が低いので、正しいやり方はvectorを新築するときに適当な大きさを初期化し(笑)、配列の古い道に戻ります.しかし、その後もダイナミックに変化するのは便利で、使いやすい関数もたくさんあります.————————————————本文はCSDNブロガー「尹小贱」のオリジナル文章で、CC 4.0 BY-SAの著作権協定に従い、原文の出典リンクと本声明を転載してください.テキストリンク:https://blog.csdn.net/qq_30835655/article/details/60762196
したがってvectorのサイズは増加し、減少することはできません.vectorが使用するメモリ領域を解放するには、vectorコンテンツを交換する関数swapを使用する必要があります.空のコードブロック内のオブジェクトまたは匿名のオブジェクトと交換すると、一時的なオブジェクトが自動的に破棄され、ダイナミックテーブルの要件に完全に合致しません.もちろん、swapを手動で使用して回収スペースを使用しない場合、vectorオブジェクトは対応する関数の実行が完了した後も回収されます(上記のtempオブジェクトを参照).しかし、いくつかの再帰プロセスではスタックが爆発する可能性が高い場合や、他のメモリの使用が比較的大きい場合は、この問題を考慮する必要があります.
だから、これもなぜvectorにサイズを宣言しておけばvectorを使う効率が高いのかを説明しています.結局、宣言しなければ、要素が加わるにつれて、データがより大きな空間に移動するのも良い方法ではありません.
ダイナミックテーブルを実現したのはdeque、double-ended queue、両端キューで、私は多くの中国語のインターネット上の資料を調べて、本当ですか、それともC++中国語のドキュメントの上で最も簡潔で明瞭ですか.
ソース:https://zh.cppreference.com/w/cpp/container/deque
std::deque(double-ended queue、両端キュー)は、最初と最後の2つのセグメントの迅速な挿入と削除を可能にする下付き順序コンテナです.また、dequeのいずれかの端に挿入または削除しても、残りの要素へのポインタまたは参照は不正化されません.std::vectorとは逆にdequeの要素は接続されて格納されていない:典型的には、vectorの下付きアクセスは、単一に割り当てられた固定サイズ配列のシーケンスで追加の登録が追加され、これは、下付きアクセスが二次ポインタ解参照を行わなければならないことを示し、それに比べてvectorの下付きアクセスは1回のみ行われる.
dequeのストレージは、必要に応じて自動的に拡張および縮小されます.拡張dequeは拡張std::vectorより安いです.既存の要素を新しいメモリ位置にコピーすることはありません.一方、dequeは典型的には、より大きな最小メモリオーバーヘッドを有する.1つの要素のみを保持するdequeは、その内部配列全体(例えば、64ビットlibstdc++がオブジェクトサイズの8倍、64ビットlibc++がオブジェクトサイズの16倍または4096バイトの大きいもの)を割り当てる必要があります.
Dequeでよく見られる操作の複雑さ(効率)は、次のとおりです.
std::dequeは、容器(Container)、ディスペンサ容器(AllocatorAwareContainer)、シーケンス容器(SequenceContainer)、および可逆容器(ReversibleContainer)の要件を満たす.STLは面白いですが、最近ちょっと緊張しているので、ここまで検討しておきましょう.