昨日言った通り、今日はvectorのpush_backについてわかったことでも書きます
void push_back(const _Ty& _Val)
{ // insert element at end
if (_Inside(_STD addressof(_Val)))
{ // push back an element
size_type _Idx = _STD addressof(_Val) - this->_Myfirst;
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
_Cons_val(this->_Alval,
this->_Mylast,
this->_Myfirst[_Idx]);
++this->_Mylast;
}else{ // push back a non-element
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
_Cons_val(this->_Alval,
this->_Mylast,
_Val);
+this->_Mylast;
}
}
まず引数、constで参照なのはコピー元を絶対に傷つけない為です
コメントで「insert element at end」とありますが、これはそのまま、vectorの末尾に要素を入れるという意味です
push_backは中身を2つに分けることができます
最初に出てくるif分で分けられるよってだけなんですが(^_^;
「_Inside(_STD addressof(_Val))」
まず「_STD_addressof(_Val)」です
_STDというのはstd::という意味です
つまり名前空間stdのaddressofという関数を呼んでます
じゃあこのaddressofは何かというと、名前の通り引数のアドレスを返す関数です
なんで&_Valではなくaddressof(_Val)かというと、気づいてるかもしれませんが_Valは参照だからです(それだけです)
なので簡単にすると
「_Inside(コピー元のアドレス)」ということになります
_Inside関数の中を見てみると
bool _Inside(const _Ty *_Ptr) const
{ // test if _Ptr points inside vector
return (_Ptr < this->_Mylast && this->_Myfirst <= _Ptr);
}
とあります
コメントがすべて説明してくれてるんですが、if文を使って、コピー元がvectorの要素なのか、vectorと関係ないものなのかを判定してます
どうしてこんなどうでもいいことを判定してるかは自分もよくわかっていないんですが、
このif文が通った時と通らなかったとき(else文)のコードを見比べてみると
this->_Myfirst[_Idx]となっているか_Valとなっているかだけです
先にいうとthis->Myfirst[_Idx]も_Valもコピー元をさしているということは同じです
つまりthis->Myfirst[_Idx]を_Valにしても動きます(多分)
stdのvectorのことなので、処理速度が上がる仕掛けでもあるのかもしれません
とりあえずifを通った時の処理を見ていきます
「size_type _Idx = _STD addressof(_Val) - this->_Myfirst;」
size_type型は突き詰めるとunsigned intです
サイズに関することならこの型を使っとけってレベルです
さっき出てきたaddressofでコピー元(vectorの要素)のアドレスを出して、this->_Myfirst(vectorの先頭アドレス)で引いてます
つまりコピー元がvectorのどこにあるか、indexを取得してるんですね
_Idxはindexの略だと思います
「if(this->_Mylast == this->_Myend)」
_Mylastと_Myendって何が違うんだ?このif文意味なくね?
ってなりますが、一応違いはあります
vectorはなるべく処理が速くなるよう設計されてるので、あらゆる工夫がされてます
push_backするたびにnewを使うんじゃあ遅いですよね?
なのでvectorはあらかじめnewである程度の大きさのメモリを確保しておいて、
placement newを使って要素を確保するようになっています
「メモリプール」で調べればこれについてよくわかると思います
で、_Mylastは要素の末尾なのに対し、_Myendはメモリプールの末尾ということになります
なので、メモリがあまっていたら_Mylast < _Myendになりますし
メモリを使い切ってたら_Mylast == _Myendというわけです
「if(this->_Mylast == this->_Myend)」というのはメモリを使い切ってるかとうかのif文ということになります
では使い切っていたとして、そのしたの
「_Reserve(1);」
なんとなくわかると思いますが、メモリを確保してます
void _Reserve(size_type _Count)
{ // ensure room for _Count new elements, grow exponentially
size_type _Size = size();
if (max_size() - _Count < _Size)
_Xlen();
else if*1
;
else
reserve(_Grow_to(_Size));
}
コメントは多分「_Countだけ新しく要素を確保して、指数関数的に増える」です
翻訳とか使ったんでよくわかりません
指数関数的っていったら、2,4,8,16・・・とかかな?
まずsize関数で_Sizeに要素数を渡す
最初のif文は「max_size() - _Count < _Size)」
つまり確保できる最大量を超えているかの判定です
max_size()は調べてみるとわかりますが、vectorが使っているアロケーターのほうの関数です
Xlen()というのはエラーを吐く関数です
見てみるとふつうに文章でエラー吐いてます
次のif文は「if*2」
capacity関数がmax_size関数と違いがよくわからなくなりますが、中身は
size_type capacity() const
{ // return current length of allocated storage
return (this->_Myend - this->_Myfirst);
}
これだけです
要素数がsize関数なのに対し、メモリプールの大きさはcapacity関数です
多分push_backでこのif文に引っかかるのは、メモリプールをぴったり使い切った時だけでしょうね、条件的に
ただ、このif文をよく見るとわかりますが、
「(_Size += _Count)」になっています!!
仮にこのif文を通過しなかったとしても”_Sizeの値は要素数+欲しい量”
になっています!!
これはこのあとの関数を考えるときに重要なことなので、意識しておいてください!
で、どのif文も引っかからなかったときにくるのが「reserve(_Grow_to(_Size))」
・・・アンダーバーが・・・抜けた・・・?!
これがめんどくさいポイントその1
reserveの前に_Grow_toについて説明します
簡単に役割をいうと、どれだけメモリ増やせばいいかってだけです
size_type _Grow_to(size_type _Count) const
{ // grow by 50% or at least to _Count
size_type _Capacity = capacity();
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%
if (_Capacity < _Count)
_Capacity = _Count;
return (_Capacity);
}
size_type _Capacityのあたりは大丈夫だと思います
メモリプールの大きさを取得してるだけです
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%
ここの部分が読みにくいかと思いますが、これは三項演算子ってやつです
「 A ? B : C」だったら
「if(A) B else C」と同じです
つまりこれを当てはめると
_Capacityに入れる値が
if(max_size() - _Capacity / 2 < _Capacity)
0;
else
_Capacity / 2 + _Capacity;
ということです
日本語で言うと「今のメモリプールの50%増しが確保できる最大量を超えてたら0、超えてなかったらそのまま50%増し」ということです
たいていは50%増しのほうでしょう
さらに、そのあとのif文で、
「50%増ししても、”必要なメモリプールの大きさ”(さっきの赤字が生きてきます)より小さかったら、仕方なく”必要なメモリプールの大きさ”にする」
ということをやってます
複雑ですね~(^q^)
で、最後は返り値として、結果的に新しく欲しいメモリプールの大きさが返され、
reserve関数に渡すことで、実際に取得する
となってます
では、reserve関数を見てみます
void reserve(size_type _Count)
{ // determine new minimum length of allocated storage
if (max_size() < _Count)
_Xlen(); // result too long
else if (capacity() < _Count)
{ // not enough room, reallocate
pointer _Ptr = this->_Alval.allocate(_Count);
_TRY_BEGIN
_Umove(this->_Myfirst, this->_Mylast, _Ptr);
_CATCH_ALL
this->_Alval.deallocate(_Ptr, _Count);
_RERAISE;
_CATCH_END
size_type _Size = size();
if (this->_Myfirst != 0)
{ // destroy and deallocate old array
_Destroy(this->_Myfirst, this->_Mylast);
this->_Alval.deallocate(this->_Myfirst,
this->_Myend - this->_Myfirst);
}
this->_Orphan_all();
this->_Myend = _Ptr + _Count;
this->_Mylast = _Ptr + _Size;
this->_Myfirst = _Ptr;
}
}
ここらへんはアロケーターのすることに近づいてます
最初のif文はもうわかると思いますが、欲しいメモリ量がそもそも確保できる最大量を超えてたらなにもできないので、普通にエラーとして流す
次のif文からが本番です
このif文は欲しいメモリプールの大きさが、今のメモリプールより大きいかを判断し、もし大きかったら新しくメモリプールを取得し、データを引越しさせます
新しくメモリプールを取得するのは案外簡単です
「pointer _Ptr = this->_Alval.allocate(_Count);」
この1行で終わりです
pointer型というのは、vector
this->_Alvalはアロケーターで、allocateでアロケートしてます(適当
問題はそのあとで、データのお引越しです
_TRY_BEGIN
_Umove(this->_Myfirst, this->_Mylast, _Ptr);
_CATCH_ALL
this->_Alval.deallocate(_Ptr, _Count);
_RERAISE;
_CATCH_END
ここがお引越しの部分なんですが・・・
_TRY_BEGIN
_CATCH_ALL
_RERAISE
_CATCH_END
は例外処理です、名前的にも
なんでコピーだけなのに、
_Umove(this->_Myfirst, this->_Mylast, _Ptr);
を呼び出してるのかな~・・・と思ってました・・・が、
ここがvectorの最速所以であり、C++11の力(昨日の記事)であります(多分)
まず、上で「なんでコピーだけなのに(ry」って言いましたが、これはコピーというより「お引越し」です!!!
_Umove
↓
_Uninitialized_move
↓
_Uninit_move
↓
_Cons_val
_Dest_val
に行きつきます(多分)
_Cons_valはvectorとかで、引越し作業をするときに使われます
_Dest_valは多分デストラクタを呼ぶために呼ばれてます
_Dest_valはどうでもいいです
_Cons_valですが、これをさらに覗いてみると
void _Cons_val(_Alloc& _Alval, _Ty1 *_Pdest, _Ty2&& _Src)
{ // construct using allocator
_Alval.construct(_Pdest, _STD forward<_Ty2>(_Src));
}
に行きつきます
じゃあ_Alval.constructは~ってあれ?void construct(pointer _Ptr, _Ty&& _Val)?
引数の_Ty&&ってなんだ?、2重参照???(すまし顔
2重参照じゃなくて、r-value referenceです、右辺値参照、やっと昨日書いた内容にたどり着きました
さて、r-value referenceとはなんぞ、となると僕は説明が下手なので、サイトを無断でお借りします
http://cpplover.blogspot.jp/2009/11/rvalue-reference_23.html
http://cpplover.blogspot.jp/2009/11/rvalue-reference_25.html
このサイトがわかりやすいです
要するに、l-valueは変数とかに入れられてて、名前があるんですが、
r-valueは名前のない、その場限りの命であるものです
適当なプロジェクトを作成して、実験してみればわかると思います
vactor
を作って、
void construct(pointer _Ptr, _Ty& _Val)と
void construct(pointer _Ptr, _Ty&& _Val)にブレークポイント置いてから
テスト①
int a = 5;
intV.push_back(a);
テスト②
intV.push_back(5);
の2通りで実行してみてください
多分、
テスト①ではvoid construct(pointer _Ptr, _Ty& _Val)が反応して
テスト②ではvoid construct(pointer _Ptr, _Ty&& _Val)が反応したと思います
なぜなら、テスト①は名前のある値(l-value)をpush_backして
テスト②では名前のないその場限りの値(r-value)をpush_backしたからです
C++11でl-valueとr-valueは明確な差が生まれたので、いろいろできることにも差が生まれたんですが、
r-valueの1番の利点がさっき言った「引越し」にあります
詳しくは上で紹介したサイトを見るのがベストだと思いますけど、簡単に説明しておくと
普通の変数Aを引数で受け取って、その関数内でほかの変数Bにデータをまるごと「引越し」させるとします(コピーじゃないです)
そうすると、関数から抜けて、変数Aを使おうとすると、中身は全部ほかの場所に移されたのでエラーになりますよね
それに対し、その場限りであるr-valueだと、データをほかの場所に「引越し」させても、どうせその場限りの参照なのでエラーにならないわけです
この「引越し」はコピーよりはるかに速い、これがr-valueの利点です(なんども言いますが詳しくはググるのがいいと思います(^_^;)
多分vectorで、memcpyを使ってコピーするのではなく、r-value referenceを使ってるのは、このためだと思います・・・
_STD forawrdとか説明してませんが、これもググるのが吉です
長くなりました、
this->_Orphan_all();
this->_Myend = _Ptr + _Count;
this->_Mylast = _Ptr + _Size;
this->_Myfirst = _Ptr;
を見ていきましょう
this->_Ophan_allですが、中で_Myproxyというのが出てきて、多分これを説明するとvector全部を説明することになりそうなので、役割だけいうと、多分初期化です(Orphanで検索したら孤児と出てきたので、よくわかりません・・・)
そのあとは簡単ですね(^_^
_Myendに新しく作ったメモリプールのアドレス+メモリプールの大きさを入れ、
_Mylastに新しく作ったメモリプールのアドレス+要素数を入れ、
_Myfirstに新しく作ったメモリプールのアドレスを入れる、と・・・
これでやっと_Reserve関数の説明は終わりです!!!
長かったorz
この関数のおかげで、メモリがなくなったときは対処をしてくれるわけです!
じゃあ次の関数を見ていきましょう・・・ってこれも面倒なポイントorz
「_Orphan_range(this->_Mylast, this->_Mylast)」
だからOrphanってなんだよおお!!!!って言いたくなります
この関数については深くは説明しません
実際に見てもらえればわかりますが、なんだかC++入門の問題みたいなプログラムです
図で表しましょう
引数の_FirstをF、_LastをL、使われてる要素を■、使われてない要素を□として
F L
■■■■□■■■■■■■□□
となっているのが
F L
■■■■■■■■■■■□□□
こうなる関数です(適当
要するにF~Lに1こ空白があったら要素をずらす関数です
言い方悪かったかな?関数名であるOrphanに無理やり結びつけた考え方をすると、
要素列をぶった切った時、あまりの要素列をOrphanっていって、この関数はそのOrphanの範囲をしていすると、要素列をつなげてくれるということですかね
なんかめんどそうな関数だけど、最速の為なんでしょう
これ、本当に謎なんですが、なんで引数を_Firstも_Lastも同じ_Mylastにしているんでしょうか
中をのぞけばわかりますが、(*_Pnext)->_Clrcont();っていう初期化?かなんかをしてる場所があって、それの為なんでしょうか、それともこれを使うべき場合があるのか、マルチスレッドに対応するためでしょうか・・・
説明まったくしてませんけど、この関数の中にある_Lockit _Lock(_LOCK_DEBUG);というのは多分マルチスレッド用です
あと、この関数が本領発揮するのはeraseをした時です
途中にある要素を削除したあと、流れをぶった切ってしまったのでそれを修復するためにこれを呼んでました
この関数についてはほとんどわかりませんでした、ほんとすみません
「_Cons_val(this->_Alval, this->_Mylast, this->_Myfirst[_Idx])」
この関数自体はさっきもでてきてましたね
第1引数でアロケーターを渡し、第2引数で場所を指定、第3引数でコピー元を渡すことで、コピーが行われます
これで、コピーも完了したので、最後に新しく1個要素が足されたので、_Mylastをインクリメントすることで終わりとなります!!!
これでvectorの流れは一応終わりです!
え?else文をやってない?こっちもほとんど変わりません
最後、_Cons_val関数の第3引数が、コピー元がvector内の要素ではなくなったので、そのまま引数の_Valを渡してます
くう~w、疲れました!自分が忘れないようにメモしておこうと思ったらこんな長くなった・・・
多分いろんなところが間違ってると思うので、もしvectorを勉強したくて検索してるうちにこのサイトに来てしまった方にはすいませんorz
わかったこと
vectorの基本的な流れをしってるから簡単だろ!そんなふうに考えていた時期が俺にもありました!!!