stl--vector的实现

vector简介

vector是一个动态数组模板类，用户无需关注vector的大小，由其内部自动拓展空间。

vector的主要接口

iterator begin();          //返回当前使用空间的头
iterator end();            //返回当前使用空间的尾
size_type size();          //返回当前使用的空间
size_type capacity();      //返回vector所有的空间，包括未使用的。
bool empty();;             //判断vector是否为空
reference operator[](size_type n);    //返回下标对应元素的引用
reference front();                    //返回第一个元素的引用
reference back();                     //返回最后一个元素的引用
void push_back();                     //将元素插入到尾部
void pop_back();                      //删除尾部的元素
iterator erase(iterator position);    //清除position对应的元素
void resize(size_type new_size, const T& x); //改变vector的大小，如果是扩充大小，x为初值
void resize(size_type new_size);      //改变vector的大小
void clear();                        //清除掉所有元素

详细设计

类的设计

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T                value_type;
    typedef value_type *     pointer;
    typedef value_type*      iterator;
    typedef value_type&      reference;
    typedef size_t           size_type;
    typedef ptrdiff_t        difference_type;

protected:
    typedef simple_alloc<value_type, Alloc> data_allocator;
    iterator start;
    iterator finish;
    iterator end_of_storage;

    void insert_aux(iterator position, const T& x);
    void deallocate() {
        if (start) {
            data_allocator::deallocate(start, end_of_storage - start);
        }
    }
    void fill_initialize(size_type n, const T& value) {
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    iterator size() const { return size_type(end() - begin()); }
    size_type capacity() const {
        return size_type(end_of_storage - begin());
    }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }

    vector() : start(0), finish(0), end_of_storage(0) {}
    vector(size_type n, const T& value) { fill_initialize(n, value); }
    vector(int n, const T& value) { fill_initialize(n, value); }
    vector(long n, const T& value) { fill_initialize(n, value); }
    explicit vector(size_type n) { fill_initialize(n, T()); }

    ~vector() {
        destroy(start, finish);
        deallocate();
    }

    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
    void push_back(const T& x) {
        if (finish != end_of_storage) {
            costruct(finish, x);  //在指定的内存构造
            ++finish;
        } else {
            insert_aux(end(), x);
        }
    }

    void pop_back()    {
    
        --finish();
        destroy(finish);  //在指定的内存销毁
    }
    //销毁掉数据
    iterator erase(iterator position) {
        if (position + 1 != end()) {
            copy(position + 1, finish, position);
        }
        --finish;
        destroy(finish);
        return position;
    }

    void resize(size_type new_size, const T& x) {
        if (new_size < size()) {
            erase(begin() + new_size, end());
        } else {
            insert(end(), new_size - size(), x);
        }
    }
    void resize(size_type new_size) { return (new_size, T()); }

protected:
    iterator allocate_and_fill(size_type, const T& x) {
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, x);
        return result;
    }
}

vector的构造函数

vector提供了多种构造方法分别是

//无参构造
vector() : start(0), finish(0), end_of_storage(0) {}
//接下来三种都是基本差不多,指定初始化的个数和初值
vector(size_type n, const T& value) { fill_initialize(n, value);}
vector(int n, const T& value) { fill_initialize(n, value);}
vector(long n, const T& value) { fill_initialize(n, value);}
//指定初始化的个数
vector(size_type n) { fill_initialize(n, T()); }

//拷贝构造
vector(vector<T, Alloc>& x) {
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());
    end_of_storage = finish;
}

//赋值构造
//重载=
template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
    if (&x != this) {
        if (x.size() > capacity()) {
            iterator tmp = allocate_and_copy(x.end() - x.begin,
                                            x.begin(), x.end());
            destroy(start, finish);
            deallocate();
            start = tmp;
            end_of_storage = start + (x.end() - x.begin());
        } else if (size() >= x.size()) {
            //直接拷贝
            iterator i = copy(x.begin(), x.end(), begin());
            destroy(i, finish);
        } else {
        //先拷贝一部分，剩下的调用全局的初始化函数来完成
            copy(x.begin(), x.begin() + size(), start);
            uninitialized_copy(x.begin() + size(), x.end(), finish);
        }
        finish = start + x.size();
    }
    return *this;
}
//另外一种构造方式，传入两个迭代器
#ifdef __STL_MEMBER_TEMPLATES
    template <class InputIterator>
    vector(InputIterator first, InputIterator last) :
      start(0), finish(0), end_of_storage(0)
    {
        range_initialize(first, last, iterator_category(first));
    }
#else
    vector(const iterator first, const_iterator last) {
        size_type n = 0;
        distance(first, last, n);
        start = allocate_and_copy(n, first, last);
        finish = start + n;
        end_of_storage = finish;
    }
#endif

所以，主要是看 fill_initialize, copy_initialize是怎样实现的了

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);
    uninitialized_fill_n(result, n, x);   //从result开始，构造n个初值为x的对象
    return result;
}

#ifdef __STL_MEMBER_TEMPLATES
template <class ForwardIterator>
iterator allocate_and_copy(size_type n,                          ForwardIterator first, ForwardIterator last) {
                          ForwardIterator first, ForwardIterator last)
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
        uninitialized_copy(first, last, result);
        return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
}
#else
iterator allocate_and_copy(size_type n,                          const_iterator first, const_iterator last) {
                          const_iterator first, const_iterator last)
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
        uninitialized_copy(first, last, result);
        return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
}
#endif

#ifdef __STL_MEMBER_TEMPLATES
template<class InputIterator>
void range_initialize(InputIterator first, InputIterator last,                      input_iterator_tag) {
                      input_iterator_tag)
    for (; first != last; ++first) {
        push_back(*first);
    }
}
template <class ForwardIterator>
void range_initialize(ForwardIterator first, ForwardIterator last,                      forward_iterator_tag) {
                      forward_iterator_tag)
    size_type n = 0;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
}
#endif

vector的析构函数

~vector()
{
    destroy(start, finish);
    deallocate();
}

void deallocate(){

    if (start) {
        data_allocator::deallocate(start, end_of_storage - start);
    }
}

push_back

尾部插入元素

template <class T, class Alloc=alloc>

void vector<T, Alloc>::push_back(const T& x) {
    if (finish != end_of_storage) {
        construct(finish, x);
        ++finish;
    } else {
        insert_aux(end(), x);
    }
}

void vector<T, Alloc>::insert_aux(iterator position, const T&x)
{
    if (finish != end_of_storage) {
        //如果还有剩余空间
        construct(finish, *(finish - 1));  //以最后一个元素构造一个新的元素
        ++finish;
        T x_copy = x;
        //指定区间，从finish-1开始倒着拷贝
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;  //拷贝完之后刚好空一个，赋值x_copy
    } else {
        //没有剩余空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;

        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            new_finish = uninitialized_copy(start, position, new_start);
            //为新元素设定初值
            construct(new_finish, x);
            ++new_finish;
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //销毁原来的空间
        destroy(begin(), end());
        deallocate();
        //将迭代器指向新的vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

insert函数

在指定的位置插入元素

//在指定的位置插入一个元素
template <class T, class Alloc = alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::insert(iterator position, const T& x)
{
    size_type n = position - begin();
    if (finish != end_ofstorage && position == end()) {
        construct(finish, x);
        ++finish;
    } else {
        insert_aux(position, x);
    }
    return begin() + n;
}
template <class T, class Alloc = alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::insert(iterator position)
{
    return insert(position, T());
}
#ifdef __STL_MEMBER_TEMPLATES
template <class T, class Alloc = alloc>
void insert(iterator position, InputIterator first, InputIterator last) {
    range_insert(position, first, last, iterator_category(first));
}
#else
void insert(iterator position, const_iterator first, const_iterator last);
#endif

//插入n个值为x的数值
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x)
{
    if (n ! = 0) {
        if (size_type(end_of_storage - finish) >= n) {
            T x_copy = x;
            const size_type elems_after = finish - position;
            iterator old_finish = finish;
            if (elems_after > n) {
                uninitialized_copy(finish - n, finish, finish);
                finish += n;
                copy_backward(position, old_finish - n, old_finish);
                fill(position, position + n, x_copy);
            } else {
                uninitialized_fill_n(finish, n - elems_afer, x_copy);
                finish += n - elems_after;
                fill(position, old_finish, x_copy);
            }
        } else {
            const size_type old_size = size();
            const size_type len = old_size + max(old_size, n);
            iterator new_start = data_allocator::allocate(len);
            iterator new_finish = new_start;
            __STL_TRY {
                new_finish = uninitialized_copy(start, position, new_start);
                new_finish = uninitialized_fill_n(new_finish, n, x);
                new_finish = uninitialized_copy(position, finish, new_finish);
            }
 #ifdef __STL_USE_EXCEPTIONS
            catch(...) {
                destroy(nwe_start, new_finish);
                data_allocator::deallocate(new_start, len);
                throw;
            }
 #endif
            destroy(start, finish);
            deallocate();
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }
}

clear函数

clear函数如下面所示，只是调用了erase函数，而erase函数则调用的是destroy函数，destroy只会
去销毁数据，并不会去销毁掉之前申请的空间。

template <class T, class Alloc>
void vector<T, Alloc>& clear()
{
    erase(begin(), end());
}
iterator erase(iterator first iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
}