欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《STL源码剖析》-序列式容器(一)vector容器

程序员文章站 2024-02-11 21:29:46
...

对于STL而言,其中最重要的就是容器了,容器也是许多人对STL的第一印象。STL跟据容器的不同,分为序列式容器(array, vector, heap, priority-queue, list, slist, deque, stack, queue)和关联式容器(set, map, multiset, multimap, hashtable, hash_set, hash_map, hash_multiset, hash_multimap)。

首先我们先来看序列式容器vector。

vector的数据结构: 线性连续空间。以两个迭代器start和finish分别指向配置的来的来内需空间中目前已经被使用的范围,并且以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端。

template<class T, class Alloc = alloc>
class vector{
...
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
...
}

为了降低配置空间时的速度成本,vector实际配置的大小可能比客户端需求的量更大一些,以备将来的扩充,这便是容量(capacity)的概念。
有了以上三个三个迭代器,我们便可轻松的得到容器的首尾标、大小、容量、空容器判断、最前端元素。。。等机能。

template<class T, class Alloc = alloc>
class vector{
...
public:
    iterator begin() {return start;}
    iterator end() {return finish;}
    iterator size() const {
        return size_type(end() - begin());
    }
    iterator capacity() const {
        return size_type(end_of_storage - begin());
    }
    iterator empty() const {
        return end() == begin();
    }
    reference operator[](size_type n) {
        return *(begin() + n);
    }

    reference front() {return *begin();}
    reference back() {return *(end() - 1);}
...
}

《STL源码剖析》-序列式容器(一)vector容器

vector的构造与内存管理:constructor,push_back:
vector缺省使用alloc作为空间适配器,并据此另外定义了一个data_allocator,方便以元素大小为配置单位

template<class T, class Alloc = alloc>
class vector{
    protectedtypedef simple_alloc<value_type, Alloc> data_allocator;
}

因此data_allocate(n)表示配置n个元素空间。

vector提供了许多constructors,其中之一允许我们指定空间大小以及初值。

//构造函数,允许指定vector大小n和初值value
vector(size_type n, const T& value)
{
    fill_initialize(n ,value);
}

//填充并予以初始化
void fill_initialize(size_type n, const T& value)
{
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

//配置而后填充
iterator allocate_and_fill(size_type n, const T& x)
{
    iterator result = data_allocator::allocate(n); //配置n个元素空间
    uninitialized_fill_n(result, n, x); //全局函数

    return result;
}

uninitialized_fill_n( )会根据第一个参数的型别特性(type traits),决定使用算法fill_n()或反复调用construct( )来完成任务。

当我们以push_back()将新元素插入vector尾端时,则该函数首先检查是否还有备用空间,有的话就直接在备用空间上构造元素,并调整迭代器finish。如果没有备用空间,就扩充空间(重新配置、移动数据、释放原有空间):

void push_back(const T& x)
{
    if(finish != end_of_storage){  //还有备用空间
        construct(finish,x);   //全局函数
        ++finish;               //调整水位高度
    }
    else
        insert_aux(end(), x);   //vector成员函数
}
template<class T, class Alloc = alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {

}

注意:动态不是在原有空间后接续新的空间(因无法保证原空间之后有可供配置的内存),而是以原有空间的两倍另外配置一块较大空间,然后将原有数据拷贝过来。然后在原内容之后构造新元素,并释放原空间。因此对vector的任何操作,一旦引起空间重新配置,原指向vector的所有迭代器就会失效。

vectord的元素操作:pop_back, erase, clear, insert
vector提供的元素操作很多,这些操作都是根据空间配置来进行操作,我们不一一介绍,只是挑选几个。

//将尾端元素拿掉,并调整大小
void pop_back() {
    --finish;   //尾端标记向前移
    destory(finish);   //全局函数
}

//清除[first, last]中所有元素
iterator erase(iterator first, iterator last) {
    iterstor i = copy(last, finish, first); //全局函数
    destory(i, finish);
    finish = finish - (last - first);
    return first
}

//清除某个位置上的元素
iterator erase(iterator position) {
    if(position + 1 != end()) {
        cpoy(position+1, finish, position);
    }
    --finish;
    destory(finish);

    return position;
}

//清空vector
void clear() {
    erase(begin(), end());
}
![这里写图片描述](http://img.blog.csdn.net/20170812002132445?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcGVuZ19zaGFrYWxha2E=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

//从position开始,插入n个元素, 元素初值为x
template<class T, class Alloc = alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {

}

《STL源码剖析》-序列式容器(一)vector容器
《STL源码剖析》-序列式容器(一)vector容器
《STL源码剖析》-序列式容器(一)vector容器

相关标签: 源码 stl