『STLソース剖析』読書ノート
6021 ワード
前言
この本は古いながらも古典的だ.STLの下位実装メカニズムを詳細に理解するとともに、一般的なデータ構造、C++メモリ管理をより深く理解することができます.特に、仕事を探しているC++ソフトウェア開発エンジニアには役立ちます.
しかし、個人的にはこの本を読む過程で詳しく理解できると思います.大体理解するだけで、細かく噛んでゆっくり飲む必要があります.この文章は私がこの本を読む過程で印象的な知識点を記録している.
第一章、STL概論
1、STLは6大コンポーネントを提供し、互いに組み合わせて使用することができる.
(1)容器
(2)アルゴリズム
(3)反復器
(4)擬似関数:operator()のclassまたはclass templateを再ロード
(5)アダプタ:コンテナや擬似関数や反復器を修飾するもの.例えばqueueやstackは、容器のように見えますが、実際にはdequeの包装です.
(6)コンフィギュレーション:スペースの構成と管理を担当する.
第二章、空間配置器
1、STL定義の中で空間構成に関連する3つの部分がある:
(1)
(2)
(3)
2、構造と分析の基本ツール:contruct()とdestroy()
STLオブジェクトを構築および解析するには、オブジェクトタイプに応じて最適な方法が選択されます.
3、空間の配置と解放
(1)小型ブロックによるメモリ破損の問題を考慮して、SGIは二層配置器を設計し、第1段配置器は直接mallocとfreeを使用し、第2四半期配置器は状況によって異なる策略を採用する.
(2)第1段コンフィギュレータはC関数を直接呼び出して実際のメモリ操作を実行し,C++new handlerのようなメカニズムを実現する.
(3)ブロックが128 bytesを超えると、十分な大きさとして第1段コンフィギュレータが呼び出される.コンフィギュレーションが128 bytes未満の場合、メモリプールは小さすぎるとみなされます.大きなメモリを構成し、対応するフリーチェーンテーブルを維持するたびに、次回同じサイズのメモリ要件があればfree-listから直接抜きます.ゲスト解放が小額ブロックを返すと、プロファイルによってfree-listに回収されます.管理を容易にするために、SGI第2四半期のコンフィギュレーションは、任意の小額ブロックのメモリ需要量を8の倍数(例えば、ゲストが30 bytesを要求すると、自動的に32 bytesに調整される)に引き上げ、8,16個のfree-listを維持し、サイズはそれぞれ8,16,24,32,40,48,56,72,80,88,961041212121128 bytesである.
(4)メモリプール
水量が十分であれば、直接20個のブロックを呼び出してfree-listに戻し、20未満であれば実際の個数未満を返す.1つも取り出せない場合は、mallocを呼び出して40個のブロックの空間を構成し、そのうち20個はfree-listに与え、残りの20個はメモリプールに残る.malloc割り当てに失敗した場合は、第1レベルのコンフィギュレータが呼び出されます.第1段コンフィギュレータにはnew-handlerメカニズムがあるので、余分なスペースを整理できるように取得します.
(5)メモリ基本処理ツール
uninitialized_copy,uninitialized_fill,uninitialized_fill_n,メモリ構成とオブジェクト構造挙動を分離できる.また、POD(すなわち、スカラー型または従来のC struct)オブジェクトに対して最も効率的な初期値記入手法を採用し、non-POD型に対して最も安全な方法を採用する.
第三章、反復器の概念とtraitsプログラミング技法
1、反復器定義
iteratorモードの定義は、ポリマーの内部表現を露出することなく、ポリマーに含まれる各元素を順次巡回できる方法を提供する.
2、Traitsプログラミング技法
反復器は、埋め込み型別宣言によって実際のパラメータのタイプにプッシュされます.
最も一般的な反復器の対応するタイプは5種類あります.
(1)value_type、オブジェクトの型別です
(2)difference typeは、2つの反復器間の距離を表すため、1つの容器の最大容量を表すために使用することができる.
(3)reference type,関数が左に戻る必要がある場合はby referenceで行う.
(4)pointer typeは、左の値を返し、指すものを代表させる.
(5)iterator_category
これは重要です.5つのタイプに分けられます.input iterator、output iterator、fowared iterator、bidirectional iterator、random access iteratorです.その意味は言うまでもありません.
3、std::iteratorの保証
STLはIterators classを提供し、新しく設計された各反復器がそれを継承すれば、STLに必要な仕様に合致することを保証します.
第四章、シーケンス式容器
この章は前に読んだことがありますが、参考にしてください.https://blog.csdn.net/luchengtao11/article/details/76849570
1.vector
動的成長メカニズム:GCCは2の指数速度で成長し,vsは1.5倍の速度で成長した.
絶え間ないpopの過程で、元の割り当てられた空間がどんなに大きくても、動的に減少しません.
反復器のプロパティ:通常のポインタで反復器を作成できます.空間再構成を引き起こすとvectorを指すすべての反復器が無効になります.
2.List
Listは双方向チェーンテーブルに基づいて実現
Listの挿入、削除、または結合操作によって、既存の反復器が無効になることはありません.
ListはSTLのsort関数でソートするのではなく,自身のsort関数でソートする.Listはランダムアクセス反復器のみをサポートし、Listは双方向反復器である.
3.deque
双方向キューです
データを複数の記憶領域に分割し、記憶領域のポインタをmap記憶領域に格納し、map領域が大きくない場合に動的に増加することができる.したがってdequeは定数時間で先頭と末尾でアクセス操作を行い、ランダムアクセスもサポートすることができる.
しかし、代価は複雑な反復器であり、vectorよりも多くの面で表現されている.
dequeの反復器には、次の要素があります.
dequeの反復器の++操作はvectorの複雑さよりはるかに複雑です.
4.stack
statckは複数のコンテナに基づいて実装できますが、デフォルトはdequeに基づいています.
statckは末尾でのみ要素にアクセスでき、遍歴動作は許可されず、反復器は提供されません.
STLでデフォルトのstackがvectorではなくdequeに基づいている理由を考えたことがありますが、個人的にはどちらを選ぶかは具体的なアプリケーションシーン次第だと思います.dequeは様々な場合に一般的に表現されていますが、悪くありません.たとえば、クレイジーpush()の場合、dequeはバッファを増やすだけでよいが、vectorはより大きなメモリ領域を要求し、すべての要素を新しい領域に移動し、元の領域を解放する必要がある.明らかに、この場合、dequeの性能はより優れている.
5.queue
複数のコンテナに基づいて実装できます.デフォルトはdequeです.
値は、末尾に要素を追加したり、最初に要素を削除したり、遍歴動作を許可したり、反復器を提供したりすることはできません.
6.heap
vectorでツリーを格納する場合.v[1]がルートノードである場合、v[i]の親ノードはv[i/2]、v[i]の子ノードはv[2*i]およびv[2*i+1]である.偶然ですね
挿入:末尾に追加し、親ノードと比較して上昇します.
削除:ルートノードを最後のノードと位置を交換し、最後のノード(元のルートノード)をポップアップしてから、ルートノード(元の最後のノード)が下がり続けます.
初期化:初期化には2つの方法があります.1つ目は挿入法、2つ目は調整法です.参考にしてください.https://blog.csdn.net/chen_lin111/article/details/50477642
第五章、関連式容器
この章は干物がいっぱいですね.
1、二叉検索ツリー
任意のノードのキー値は、左サブツリーの各ノードのキー値よりも大きく、右サブツリーの各ノードのキー値よりも小さいに違いありません.その添削はすべて簡単です.
2、AVL-tree
二叉探索ツリーに基づいて,任意のノードの左右のサブツリーの高さの差が最大1であることが要求される.
新しいノードを挿入すると、バランス状態が変化する可能性があります.この場合、再調整が必要です.「挿入点はルートノードを指す」パス上で、バランス状態が破壊された各ノードの中で最も深いものを調整するだけで、この点がXであると仮定すると、4つのケースに分けられます.挿入点Xの左サブノードにある左サブツリー--左 挿入点Xの左サブノードにある右サブツリー--左右 挿入点Xの右サブノードにある左サブツリー--右左 挿入点Xの右サブノードにある右サブツリー--右 1,4の場合は,単回転操作調整で解決でき,2,3の場合は,二回転操作調整で解決できる.
3、赤と黒の木
赤と黒のツリーは、二叉検索ツリーに基づいて、次のルールを満たす必要があります.各ノードは黒ではなく赤 である.ノードが黒 ノードが赤の場合、そのサブノードは黒の である必要があります.ノードからNULLまでの任意のパスで、黒いノードの点数は同じでなければなりません.
STLはなぜAVL-treeではなく赤と黒の木を選んだのですか?
赤黒樹の平衡性はAVL−treeより弱いが探索効率はほぼ等しい.両者の挿入と削除はO(logn)であるが,回転操作ではAVL−treeはO(n)であり,赤黒樹はO(1)である.
4.set
赤と黒の木に基づいて実現します.
反復器で要素値を変更することはできません.(変えると赤黒い木の構造が破壊されます).
挿入と削除の操作は、以前の反復器が無効になります.
関連コンテナの場合、STLのfind()を使用するよりも、独自のfind()関数を使用する方が効果的です.
5.map
反復器でkey値を変更することはできませんが、value値を変更することができます.削除および挿入操作では、以前の反復器が無効になりません.Insert操作はpairを返し、firstは挿入された要素の反復器であり、secondはboolであり、挿入に成功したかどうかを示すMulimap、mulitsetは通常のmap、setと差が少なく、重複値が許容されているにすぎない.
6.hash_table
線形プローブ:f(value)=value%length+i;
二次プローブ:f(value)=value%length+i^2
開鎖:同じkey値のvalueはチェーンテーブルで同じバケツに保存されます.エレメントの個数がバケツの個数より大きい場合は再構築し、再構築後の対応する位置を挿入します.
hash_mapとhash_setはすべてhash_に基づいていますtable.
vsはhash_と言いますmapとhash_setはもう時代遅れだunordered_map,unorder_set、性能が最適です.
この本は古いながらも古典的だ.STLの下位実装メカニズムを詳細に理解するとともに、一般的なデータ構造、C++メモリ管理をより深く理解することができます.特に、仕事を探しているC++ソフトウェア開発エンジニアには役立ちます.
しかし、個人的にはこの本を読む過程で詳しく理解できると思います.大体理解するだけで、細かく噛んでゆっくり飲む必要があります.この文章は私がこの本を読む過程で印象的な知識点を記録している.
第一章、STL概論
1、STLは6大コンポーネントを提供し、互いに組み合わせて使用することができる.
(1)容器
(2)アルゴリズム
(3)反復器
(4)擬似関数:operator()のclassまたはclass templateを再ロード
(5)アダプタ:コンテナや擬似関数や反復器を修飾するもの.例えばqueueやstackは、容器のように見えますが、実際にはdequeの包装です.
(6)コンフィギュレーション:スペースの構成と管理を担当する.
第二章、空間配置器
1、STL定義の中で空間構成に関連する3つの部分がある:
(1)
(2)
(3)
2、構造と分析の基本ツール:contruct()とdestroy()
STLオブジェクトを構築および解析するには、オブジェクトタイプに応じて最適な方法が選択されます.
3、空間の配置と解放
(1)小型ブロックによるメモリ破損の問題を考慮して、SGIは二層配置器を設計し、第1段配置器は直接mallocとfreeを使用し、第2四半期配置器は状況によって異なる策略を採用する.
(2)第1段コンフィギュレータはC関数を直接呼び出して実際のメモリ操作を実行し,C++new handlerのようなメカニズムを実現する.
(3)ブロックが128 bytesを超えると、十分な大きさとして第1段コンフィギュレータが呼び出される.コンフィギュレーションが128 bytes未満の場合、メモリプールは小さすぎるとみなされます.大きなメモリを構成し、対応するフリーチェーンテーブルを維持するたびに、次回同じサイズのメモリ要件があればfree-listから直接抜きます.ゲスト解放が小額ブロックを返すと、プロファイルによってfree-listに回収されます.管理を容易にするために、SGI第2四半期のコンフィギュレーションは、任意の小額ブロックのメモリ需要量を8の倍数(例えば、ゲストが30 bytesを要求すると、自動的に32 bytesに調整される)に引き上げ、8,16個のfree-listを維持し、サイズはそれぞれ8,16,24,32,40,48,56,72,80,88,961041212121128 bytesである.
(4)メモリプール
水量が十分であれば、直接20個のブロックを呼び出してfree-listに戻し、20未満であれば実際の個数未満を返す.1つも取り出せない場合は、mallocを呼び出して40個のブロックの空間を構成し、そのうち20個はfree-listに与え、残りの20個はメモリプールに残る.malloc割り当てに失敗した場合は、第1レベルのコンフィギュレータが呼び出されます.第1段コンフィギュレータにはnew-handlerメカニズムがあるので、余分なスペースを整理できるように取得します.
(5)メモリ基本処理ツール
uninitialized_copy,uninitialized_fill,uninitialized_fill_n,メモリ構成とオブジェクト構造挙動を分離できる.また、POD(すなわち、スカラー型または従来のC struct)オブジェクトに対して最も効率的な初期値記入手法を採用し、non-POD型に対して最も安全な方法を採用する.
第三章、反復器の概念とtraitsプログラミング技法
1、反復器定義
iteratorモードの定義は、ポリマーの内部表現を露出することなく、ポリマーに含まれる各元素を順次巡回できる方法を提供する.
2、Traitsプログラミング技法
反復器は、埋め込み型別宣言によって実際のパラメータのタイプにプッシュされます.
最も一般的な反復器の対応するタイプは5種類あります.
(1)value_type、オブジェクトの型別です
(2)difference typeは、2つの反復器間の距離を表すため、1つの容器の最大容量を表すために使用することができる.
(3)reference type,関数が左に戻る必要がある場合はby referenceで行う.
(4)pointer typeは、左の値を返し、指すものを代表させる.
(5)iterator_category
これは重要です.5つのタイプに分けられます.input iterator、output iterator、fowared iterator、bidirectional iterator、random access iteratorです.その意味は言うまでもありません.
3、std::iteratorの保証
STLはIterators classを提供し、新しく設計された各反復器がそれを継承すれば、STLに必要な仕様に合致することを保証します.
第四章、シーケンス式容器
この章は前に読んだことがありますが、参考にしてください.https://blog.csdn.net/luchengtao11/article/details/76849570
1.vector
動的成長メカニズム:GCCは2の指数速度で成長し,vsは1.5倍の速度で成長した.
絶え間ないpopの過程で、元の割り当てられた空間がどんなに大きくても、動的に減少しません.
反復器のプロパティ:通常のポインタで反復器を作成できます.空間再構成を引き起こすとvectorを指すすべての反復器が無効になります.
2.List
Listは双方向チェーンテーブルに基づいて実現
Listの挿入、削除、または結合操作によって、既存の反復器が無効になることはありません.
ListはSTLのsort関数でソートするのではなく,自身のsort関数でソートする.Listはランダムアクセス反復器のみをサポートし、Listは双方向反復器である.
3.deque
双方向キューです
データを複数の記憶領域に分割し、記憶領域のポインタをmap記憶領域に格納し、map領域が大きくない場合に動的に増加することができる.したがってdequeは定数時間で先頭と末尾でアクセス操作を行い、ランダムアクセスもサポートすることができる.
しかし、代価は複雑な反復器であり、vectorよりも多くの面で表現されている.
dequeの反復器には、次の要素があります.
T *cur; //
T *first; //
T *last; // （ last ， ， ）
map_pointer node; // dequeの反復器の++操作はvectorの複雑さよりはるかに複雑です.
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node;//
last = first + difference_type(buffer_size); //
}
self& opertator++()
{
++cur; //
if (cur == last) //
{
set_node(node+1); //
cur = first; //
}
return *this;
}4.stack
statckは複数のコンテナに基づいて実装できますが、デフォルトはdequeに基づいています.
statckは末尾でのみ要素にアクセスでき、遍歴動作は許可されず、反復器は提供されません.
STLでデフォルトのstackがvectorではなくdequeに基づいている理由を考えたことがありますが、個人的にはどちらを選ぶかは具体的なアプリケーションシーン次第だと思います.dequeは様々な場合に一般的に表現されていますが、悪くありません.たとえば、クレイジーpush()の場合、dequeはバッファを増やすだけでよいが、vectorはより大きなメモリ領域を要求し、すべての要素を新しい領域に移動し、元の領域を解放する必要がある.明らかに、この場合、dequeの性能はより優れている.
5.queue
複数のコンテナに基づいて実装できます.デフォルトはdequeです.
値は、末尾に要素を追加したり、最初に要素を削除したり、遍歴動作を許可したり、反復器を提供したりすることはできません.
6.heap
vectorでツリーを格納する場合.v[1]がルートノードである場合、v[i]の親ノードはv[i/2]、v[i]の子ノードはv[2*i]およびv[2*i+1]である.偶然ですね
挿入:末尾に追加し、親ノードと比較して上昇します.
削除:ルートノードを最後のノードと位置を交換し、最後のノード(元のルートノード)をポップアップしてから、ルートノード(元の最後のノード)が下がり続けます.
初期化:初期化には2つの方法があります.1つ目は挿入法、2つ目は調整法です.参考にしてください.https://blog.csdn.net/chen_lin111/article/details/50477642
第五章、関連式容器
この章は干物がいっぱいですね.
1、二叉検索ツリー
任意のノードのキー値は、左サブツリーの各ノードのキー値よりも大きく、右サブツリーの各ノードのキー値よりも小さいに違いありません.その添削はすべて簡単です.
2、AVL-tree
二叉探索ツリーに基づいて,任意のノードの左右のサブツリーの高さの差が最大1であることが要求される.
新しいノードを挿入すると、バランス状態が変化する可能性があります.この場合、再調整が必要です.「挿入点はルートノードを指す」パス上で、バランス状態が破壊された各ノードの中で最も深いものを調整するだけで、この点がXであると仮定すると、4つのケースに分けられます.
3、赤と黒の木
赤と黒のツリーは、二叉検索ツリーに基づいて、次のルールを満たす必要があります.
STLはなぜAVL-treeではなく赤と黒の木を選んだのですか?
赤黒樹の平衡性はAVL−treeより弱いが探索効率はほぼ等しい.両者の挿入と削除はO(logn)であるが,回転操作ではAVL−treeはO(n)であり,赤黒樹はO(1)である.
4.set
赤と黒の木に基づいて実現します.
反復器で要素値を変更することはできません.(変えると赤黒い木の構造が破壊されます).
挿入と削除の操作は、以前の反復器が無効になります.
関連コンテナの場合、STLのfind()を使用するよりも、独自のfind()関数を使用する方が効果的です.
5.map
反復器でkey値を変更することはできませんが、value値を変更することができます.削除および挿入操作では、以前の反復器が無効になりません.Insert操作はpairを返し、firstは挿入された要素の反復器であり、secondはboolであり、挿入に成功したかどうかを示すMulimap、mulitsetは通常のmap、setと差が少なく、重複値が許容されているにすぎない.
6.hash_table
線形プローブ:f(value)=value%length+i;
二次プローブ:f(value)=value%length+i^2
開鎖:同じkey値のvalueはチェーンテーブルで同じバケツに保存されます.エレメントの個数がバケツの個数より大きい場合は再構築し、再構築後の対応する位置を挿入します.
hash_mapとhash_setはすべてhash_に基づいていますtable.
vsはhash_と言いますmapとhash_setはもう時代遅れだunordered_map,unorder_set、性能が最適です.