« 今日の日記 | Main | C++の例外ってすごい »

2007.08.20

std::vector見てみた

STLportsのvectorのソースを読んでみる。

とりあえず、簡単な所から確認して自信をつけたかったので、[]の実装から。
reference operator[](size_type __n) { return *(begin() + __n); }

referenceはこんな感じでtypedef。
typedef _Tp value_type;
typedef value_type& reference;

at()の実装はこう
reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }

_M_range_check()の中で範囲の確認をして、OKなら[]でアクセス、NGなら例外の送出。

void _M_range_check(size_type __n) const {
if (__n >= size_type(this->_M_finish - this->_M_start))
this->_M_throw_out_of_range();
}

納得。

続いてpush_back()。
ifdefは適当に読み飛ばすと、

void push_back(const _Tp& __x) {
if (this->_M_finish != this->_M_end_of_storage._M_data) {
_Copy_Construct(this->_M_finish, __x);
++this->_M_finish;
}
else
_M_insert_overflow(this->_M_finish, __x, _TrivialCopy(), 1UL, true);
}

範囲に入っていれば、_Copy_Construct()、そうでなければ、_M_insert_overflow()を呼ぶ。_Copy_Construct()は、ただのmemset。

_M_insert_overflowからちょっと手強い。

template
void vector<_Tp, _Alloc>::_M_insert_overflow(pointer __pos, const _Tp& __x, const __true_type& /*_TrivialCopy*/,
size_type __fill_len, bool __atend ) {

//ここで、引数の__fill_lenと、今のサイズ__old_sizeの大きい方を新しいサイズにしている。
//push_backの時は__fill_lenは1で呼ばれているから、サイズは倍になる。
//必要な領域だけ確保するんじゃなくて、倍々で確保していく。(STLPortsの実装)
const size_type __old_size = size();
size_type __len = __old_size + (max)(__old_size, __fill_len);

//ここから、
pointer __new_start = this->_M_end_of_storage.allocate(__len, __len);
pointer __new_finish = __STATIC_CAST(pointer, _STLP_PRIV __copy_trivial(this->_M_start, __pos, __new_start));
// handle insertion
__new_finish = _STLP_PRIV __fill_n(__new_finish, __fill_len, __x);
if (!__atend)
__new_finish = __STATIC_CAST(pointer, _STLP_PRIV __copy_trivial(__pos, this->_M_finish, __new_finish)); // copy remainder
_M_clear();

//ここまでがわからなくて、最後に新しい値を設定している。
_M_set(__new_start, __new_finish, __new_start + __len);
}

続きは明日。 _AllocProxy _M_end_of_storageの_M_end_of_storage.allocate()から。

|

« 今日の日記 | Main | C++の例外ってすごい »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/16181584

Listed below are links to weblogs that reference std::vector見てみた:

« 今日の日記 | Main | C++の例外ってすごい »