首先是vector的定義
template <typename T>
class vector
{
};
讓我們先來(lái)看看vector中的一些別名
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef const T* const_iterator;
typedef reverse_iterator<const_iterator, value_type, size_type, difference_type> const_reverse_iterator;
typedef T* iterator;
typedef reverse_iterator<iterator, value_type, size_type, difference_type> reverse_iterator;
由上可見(jiàn)，正如
上一篇所說(shuō)，vector的迭代器是由原生的指針來(lái)實(shí)現(xiàn)的。
下面是其內(nèi)部的成員變量
protected:
typedef vector<T> self;
typedef allocator<T> Alloc;
iterator start;
iterator finish;
iterator end_of_element;
start：指向vector的起始地址
finish：指向最后一個(gè)元素的后一個(gè)元素的地址
end_of_element：指向已申請(qǐng)內(nèi)存塊的結(jié)束位置（finish總是小于或等于end_of_element）
在STL中從begin到end總是以一個(gè)前閉后開(kāi)的形式來(lái)表示的，形如[begin,end)，這樣做的好處是可以使代碼寫(xiě)的更簡(jiǎn)潔：
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& value)
{
while(first != last && *first != value) ++first;
return first;
}
下面來(lái)看看vector中最基本的構(gòu)造函數(shù)和析構(gòu)函數(shù)
vector() : start(0), finish(0), end_of_element(0)
{
}
~vector()
{
destruct(start, end_of_element);
if (start != 0) Alloc::deallocate(start, end_of_element - start);
}
這里將其中的3個(gè)成員變量都填充為0。
如
上一篇所說(shuō)，在STL中是將內(nèi)存分配與對(duì)象初始化分開(kāi)的，同樣對(duì)象析構(gòu)與內(nèi)存釋放也是被分開(kāi)的。
然后是其begin和end方法，用來(lái)獲取第一個(gè)元素和最后一個(gè)元素的后一個(gè)元素的迭代器。
inline iterator begin()
{
return start;
}
inline const_iterator begin()const
{
return start;
}
inline iterator end()
{
return finish;
}
inline const_iterator end()const
{
return finish;
}
front和back分別被用來(lái)獲取第一個(gè)元素和最后一個(gè)元素
inline reference front()
{
return *begin();
}
inline const_reference front()const
{
return *begin();
}
inline reference back()
{
return *(end() - 1);
}
inline const_reference back()const
{
return *(end() - 1);
}
empty、size、capacity分別被用來(lái)判別容器是否為空、容器內(nèi)元素的個(gè)數(shù)和容器的大小
inline bool empty()const
{
return begin() == end();
}
inline const size_type size()const
{
return size_type(end() - begin());
}
inline const size_type capacity()const
{
return size_type(end_of_element - begin());
}
由于在vector的頭部插入元素會(huì)使所有元素后移，應(yīng)此它被設(shè)計(jì)為單向的，只能由尾部插入或移除數(shù)據(jù)
void push_back(const T& x)
{
if (end_of_element != finish)
{
construct(&*finish, x);
++finish;
}
else
{
insert_aux(end(), x);
}
}
inline void pop_back()
{
--finish;
destruct<T>(finish, has_destruct(*finish));
}
當(dāng)然從頭部移除數(shù)據(jù)也并非不可以，可以使用erase方法來(lái)移除頭部的數(shù)據(jù)，erase方法將會(huì)在后面的部分作出說(shuō)明。
我們先來(lái)看一下insert_aux這個(gè)方法，在插入元素時(shí)幾乎都使用到了這個(gè)方法。
void insert_aux(const iterator position, const T& x)
{
if(finish != end_of_element)
{
construct(&*finish, *(finish - 1));
T x_copy = x;
copy_backward(position, finish - 1, finish);
*position = x_copy;
++finish;
}
else
{
const size_type old_size = size();
const size_type new_size = old_size == 0 ? 2 : old_size * 2;
iterator tmp = Alloc::allocate(new_size);
uninitialized_copy(begin(), position, tmp);
iterator new_position = tmp + (position - begin());
construct(&*new_position, x);
uninitialized_copy(position, end(), new_position + 1);
destruct(begin(), end());
Alloc::deallocate(begin(), old_size);
end_of_element = tmp + new_size;
finish = tmp + old_size + 1;
start = tmp;
}
}
在容器還有足夠的空間時(shí)，首先將從position位置到finish位置的元素整體后移一個(gè)位置，最后將要被插入的元素寫(xiě)入到原position的位置同時(shí)改變finish指針的值。
若空間不足時(shí)，首先根據(jù)原有空間的大小的一倍來(lái)申請(qǐng)內(nèi)存，然后將元素從原有位置的begin到position拷貝到新申請(qǐng)的內(nèi)存中，然后在新申請(qǐng)內(nèi)存的指定位置插入要插入的元素值，最后將余下的部分也拷貝過(guò)來(lái)。然后將原有元素析構(gòu)掉并把內(nèi)存釋放掉。
為何不使用reallocate?
reallocate的本意并不是在原有內(nèi)存的位置增加或減少內(nèi)存，reallocate首先會(huì)試圖在原有的內(nèi)存位置增加或減少內(nèi)存，
若失敗則會(huì)重新申請(qǐng)一塊新的內(nèi)存并把原有的數(shù)據(jù)拷貝過(guò)去，這種操作本質(zhì)上等價(jià)于重新申請(qǐng)一塊內(nèi)存，應(yīng)此這里使用的是allocate而并非reallocate。
然后讓我們來(lái)看一下insert和erase方法
inline iterator insert(iterator position, const T& x)
{
const size_type pos = position - begin();
if(finish != end_of_element && position == end())
{
construct(&*finish, x);
++finish;
}
else insert_aux(position, x);
return begin() + pos;
}
iterator erase(iterator position)
{
destruct(position, has_destruct(*position));
if (position + 1 != end())
{
copy(position + 1, end(), position);
}
--finish;
return position;
}
若是要在最后插入一個(gè)元素且容器的剩余空間還足夠的話，直接將元素插入到finish的位置，并將finish指針后移一位即可。若容器空間不夠或不是插在最后一個(gè)的位置，則調(diào)用insert_aux重新分配內(nèi)存或插入。
刪除時(shí)首先析構(gòu)掉原有元素，若被刪元素不是最后一個(gè)元素，則將后面的所有元素拷貝過(guò)來(lái)，最后將finish指針前移一個(gè)位置。
最后讓我們來(lái)看一下其中重載的運(yùn)算符
self& operator=(const self& x)
{
if(&x == this) return *this;
size_type const other_size = x.size();
if(other_size > capacity())
{
destruct(start, finish);
Alloc::deallocate(start, capacity());
start = Alloc::allocate(other_size);
finish = uninitialized_copy(x.begin(), x.end(), start);
end_of_element = start + other_size;
}
else
{
finish = uninitialized_copy(x.begin(), x.end(), start);
}
return *this;
}
inline reference operator[](size_type n)
{
return *(begin() + n);
}
inline value_type at(size_type n)
{
return *(begin() + n);
}
由于vector內(nèi)部用的是原生的指針，應(yīng)此這些運(yùn)算符的使用方式和原生指針的并無(wú)差異。
值得注意的是在做賦值操作時(shí)會(huì)產(chǎn)生內(nèi)存的重新分配與拷貝操作。
至此，vector的講解已完成，完整的代碼請(qǐng)到
http://qlanguage.codeplex.com下載
posted on 2012-06-17 17:08
lwch 閱讀(3608)
評(píng)論(3) 編輯 收藏 引用 所屬分類(lèi):
STL