5. STL学习笔记--基础容器之vector

水深无声 2022-04-13 13:12 201阅读 0赞

一、实验内容

本次实验主要讲述 c++11 vector 容器的用法，vector 是 c++11 STL 中一个非常重要的成员，通过对它的使用，我们可以更加高效率的处理数据，通过本次实验你可以实现属于自己的 vector。

1.1 知识点

*  vector 基础
 *  vector 初始化
 *  vector 基本操作
 *  vector 成员函数

1.2 实验环境

*  g++
 *  ubuntu 16.04

1.3 代码获取

可以通过以下链接获取本课程的源码内容，本次实验内容主要包含在文件`Vector.h`，成员函数封装在 Detail 目录下 `Vector.impl.h`中。

//获取代码
    wget http://labfile.oss.aliyuncs.com/courses/1166/mySTL.zip
    
    //解压文件到Code目录
    unzip -q mySTL.zip -d ./Code/

本次实验需要用到的头文件包括： 可以在 `mySTL` 目录下查看

#include "TypeTraits.h"                    //类型库，抽象定义了一些类型
    #include "Allocator.h"                    //空间分配器，已经写好直接调用
    #include "Algorithm.h"                    //算法库
    #include "Iterator.h"                    //迭代器
    #include "ReverseIterator.h"            //逆向迭代器，重载了一些运算符，可以直接使用
    #include "UninitializedFunctions.h"        //初始化函数库，直接使用

二、vector详解

2.1 vector 介绍

vector 是 C++ 标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector 是向量类型，它可以容纳多种类型的数据，所以称之为容器。

首先在 `include` 目录下创建 `Vector.h`，在 `Detail` 目录下创建 `Vector.impl.h`,用于封装成员函数。便于理解，成员函数我们直接封装了。接口可以在 `Vector.h` 中查看。

2.2 vector 类基础

我们需要为 vector 定义四个私有成员:

*  `*start_`:表示使用空间的头
 *  `*finnish_`:表示使用空间的末尾
 *  `*endofStorage_`:表示可用空间的末尾
 *  `dataAllocator`:表示分配空间

private:
        T *start_;
        T *finish_;
        T *endofStorage_;
        typedef Alloc dataAllocator;

同时我们还需要声明一些类型，以便于与系统类型进行区别。

public:
            typedef T                                    value_type;//值类型
            typedef T*                                    iterator;//迭代器
            typedef const T*                            const_iterator;//常量迭代器
            typedef reverse_iterator_t<T*>                reverse_iterator;//反向迭代器
            typedef reverse_iterator_t<const T*>                           const_reverse_iterator;
            typedef iterator                            pointer;//操作结果类型
            typedef T&                                    reference;//解引用操作结果类型
            typedef const T&                            const_reference;
            typedef size_t                                size_type;
            typedef ptrdiff_t                            difference_type;//表示两个迭代器之间的距离 ,c++内置定义 typedef int ptrdiff_t;

三、vector初始化

和任何一种类类型一样，vector 模板控制着定义和初始化向量的方法。下面我们就讲讲 vector 的初始化。

3.1 不带参数的构造函数初始化(默认值为0)

vector():start_(0), finish_(0), endOfStorage_(0){}

3.2 带参数的构造函数初始化

*  构造 n 个 0

template<class T, class Alloc>
    vector<T, Alloc>::vector(const size_type n){
        allocateAndFillN(n, value_type());//调用成员函数，默认值为0
    }

*  构造n 个 value

template<class T, class Alloc>
    vector<T, Alloc>::vector(const size_type n, const value_type& value){
        allocateAndFillN(n, value);//调用成员函数
    }

*  把 fist 到 last 的所有元素放进 vector

template<class T, class Alloc>
    template<class InputIterator>
    vector<T, Alloc>::vector(InputIterator first, InputIterator last){
        //处理指针和数字间的区别的函数
        vector_aux(first, last, typename                 std::is_integral<InputIterator>::type());//需调用插入辅助函数
    }
    
    template<class T, class Alloc>
    template<class Integer>
    void vector<T, Alloc>::vector_aux(Integer n, const value_type& value, std::true_type){
        allocateAndFillN(n, value);//构造辅助函数
    }

*  拷贝赋值构造一个 vector

template<class T, class Alloc>
    vector<T, Alloc>::vector(const vector& v){
        allocateAndCopy(v.start_, v.finish_);//这里调用辅助成员函数完成
    }

*  赋值操作符

template<class T, class Alloc>
        vector<T, Alloc>& vector<T, Alloc>::operator = (const vector& v){
        if (this != &v){
            allocateAndCopy(v.start_, v.finish_);
        }
        return *this;
    }

*  析构函数

template<class T, class Alloc>
    vector<T, Alloc>::~vector(){
        destroyAndDeallocateAll();
    }

四、vector常规操作（添加、删除、访问、插入）

4.1 添加（添加到末尾）

vector 有自己的添加元素的方法，就是把元素添加到 vector 容器的末尾。这里我们命名为 push\_back()函数。我们需要考虑到空间问题，如果空间已满的情况下，需要申请更多的空间。

template<class T, class Alloc>
    void vector<T, Alloc>::push_back(const value_type& value){
        insert(end(), value);
    }

4.2 删除

删除需要根据具体情况来看，可以单纯只删除一个，也可以删除某指定元素或者某串元素，下面我们对这些问题具体分析。

*  尾部删除

尾部删除可以简单的执行删除操作。

template<class T, class Alloc>
    void vector<T, Alloc>::pop_back(){
        --finish_;
        dataAllocator::destroy(finish_);//辅助成员函数
    }

*  指定删除

简单的尾部删除肯定满足不了我们的编程需求，所以这里假设了指定位置删除。

(1)指定位置删除

template<class T, class Alloc>
    typename vector<T, Alloc>::iterator vector<T, Alloc>::erase(iterator position){
        return erase(position, position + 1);
    }

(2)指定范围删除

template<class T, class Alloc>
    typename vector<T, Alloc>::iterator vector<T, Alloc>::erase(iterator first, iterator last){
        //尾部残留对象数
        difference_type lenOfTail = end() - last;
        //删去的对象数目
        difference_type lenOfRemoved = last - first;
        finish_ = finish_ - lenOfRemoved;
        for (; lenOfTail != 0; --lenOfTail){
            auto temp = (last - lenOfRemoved);
            *temp = *(last++);
        }
        return (first);
    }

4.3 访问

vector 的访问是比较简单的，只要掌握了数组的使用，就不难理解。

*  返回下标位置元素

reference operator[](const difference_type i){  //重载[],这样可以用a[n]进行访问元素
        return *(begin() + i); 
    }

*  返回倒数第 i 个元素

const_reference operator[](const difference_type i)const{
        return *(cbegin() + i); 
    }

*  返回第一个元素

reference front(){ 
        return *(begin()); 
    }

*  返回最后一个元素

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

*  返回第一个元素的指针

pointer data(){ 
        return start_;
    }

4.4 插入

单纯的尾部添加可能还需要我们进行排序之类的操作，这样就增加了不少的外部代码，所以我们有必要增加一个成员函数 insert，用于在指定位置插入元素。

*  单个插入

template<class T, class Alloc>
    typename vector<T, Alloc>::iterator vector<T, Alloc>::insert(iterator position, const value_type& val){
        const auto index = position - begin();
        insert(position, 1, val);//插入辅助函数
        return begin() + index;
    }
    
    template<class T, class Alloc>
    template<class Integer>
    void vector<T, Alloc>::insert_aux(iterator position, Integer n, const value_type& value, std::true_type){
        assert(n != 0);//判断n是否为0
        difference_type locationLeft = endOfStorage_ - finish_; // 可使用空间大小
        difference_type locationNeed = n;//需要空间
    
        if (locationLeft >= locationNeed){//剩余空间大于需求空间
            auto tempPtr = end() - 1;
               for (; tempPtr - position >= 0; --tempPtr){//move the [position, finish_) back
                construct(tempPtr + locationNeed, *tempPtr);
            }
            mySTL::uninitialized_fill_n(position, n, value);
            finish_ += locationNeed;
        }
        else{
            reallocateAndFillN(position, n, value);
        }
    }

*  指定范围插入

template<class T, class Alloc>
    template<class InputIterator>
    void vector<T, Alloc>::insert(iterator position, InputIterator first, InputIterator last){
        insert_aux(position, first, last, typename         std::is_integral<InputIterator>::type());//插入辅助函数
    }
    
    void vector<T, Alloc>::insert_aux(iterator position,
    InputIterator first,InputIterator last,std::false_type){
        difference_type locationLeft = endOfStorage_ - finish_; // 计算剩余空间大小
        difference_type locationNeed = distance(first, last);//计算全部空间大小
    
        if (locationLeft >= locationNeed){//如果剩余空间满足需求，直接插入
            if (finish_ - position > locationNeed){
            mySTL::uninitialized_copy(finish_ - locationNeed, finish_, finish_);
            std::copy_backward(position, finish_ - locationNeed, finish_);
            std::copy(first, last, position);
            }
            else{//不满足，把指定位置后的元素先取出来，插入后在添加到末尾
                iterator temp = mySTL::uninitialized_copy(first + (finish_ - position), last, finish_);
                mySTL::uninitialized_copy(position, finish_, temp);
                std::copy(first, first + (finish_ - position), position);
                   }
                finish_ += locationNeed;
            }
        else{
            reallocateAndCopy(position, first, last);
        }
    }

四、vector增长模型

我们可以把 vector 理解为动态数组，作为一个动态数组，vector 有一个指针指向一片连续的内存空间，但是这片空间不是无限的，当内存装不下数据时，系统会自动申请一片更大的空间把原来的数据拷贝过去，释放原来的内存空间。 **vector 的内存非常重要，一旦内存重新配置，与之相关的所有指针、迭代器都会失效，而且配置内存非常耗时。**

五、vector成员函数

vector 是非常方便的，这离不开它的成员函数，vector 的许多操作都是通过成员函数完成的，包括添加删除。

**5.1 迭代器相关**

*  返回头部迭代器

iterator begin(){ return (start_); } 
    const_iterator begin()const{ return (start_); }//常量迭代器，只读属性
    const_iterator cbegin()const{ return (start_); }

*  返回尾部迭代器

iterator end(){ return (finish_); }
    const_iterator end()const{ return (finish_); }
    const_iterator cend()const{ return (finish_); }

*  逆向，返回头部迭代器

reverse_iterator rend(){ return reverse_iterator(start_); }
    const_reverse_iterator crend()const{ return const_reverse_iterator(start_); }

*  逆向，返回尾部

reverse_iterator rbegin(){ return reverse_iterator(finish_); }
    const_reverse_iterator crbegin()const{ return const_reverse_iterator(finish_);

**5.2访问元素相关**

*  顺序访问

reference front(){ return *(begin()); } //返回头部迭代器
    reference back(){ return *(end() - 1); }//返回最后一个元素迭代器
    pointer data(){ return start_; }//返回头部指针

*  定向访问

reference operator[](const difference_type i){ return *(begin() + i); }//返回第 i 个元素的迭代器
    const_reference operator[](const difference_type i)const{ return *(cbegin() + i); }//返回第 i 个元素的迭代器，只读

**5.3容量相关**

*  返回元素个数

difference_type size() const{ 
        return finish_ - start_; 
    }

*  返回容量大小

difference_type capacity() const{ 
        return endOfStorage_ - start_; 
    }

*  清空容器

bool empty() const{ 
        return start_ == finish_; 
    }

*  重新定义容器大小

template<class T, class Alloc>
    void vector<T, Alloc>::resize(size_type n, value_type val){
        if (n < size()){//如果重新定义空间小于元素个数，需要释放多余空间
            dataAllocator::destroy(start_ + n, finish_);
            finish_ = start_ + n;
        }
        else if (n > size() && n <= capacity()){//如果重新定义空间大于元素个数而小于本来空间，需要释放多余空间
            auto lengthOfInsert = n - size();
            finish_ = mySTL::uninitialized_fill_n(finish_, lengthOfInsert, val);
        }
        else if (n > capacity()){
            auto lengthOfInsert = n - size();
            T *newStart =             dataAllocator::allocate(getNewCapacity(lengthOfInsert));
            T *newFinish = mySTL::uninitialized_copy(begin(), end(), newStart);
            newFinish = mySTL::uninitialized_fill_n(newFinish, lengthOfInsert, val);
    
        destroyAndDeallocateAll();//初始化
        start_ = newStart;
        finish_ = newFinish;
        endOfStorage_ = start_ + n;
        }
    }

*  重新分配存储区大小

template<class T, class Alloc>
    void vector<T, Alloc>::reserve(size_type n){//首先释放空间，然后初始化
        if (n <= capacity())
            return;
        T *newStart = dataAllocator::allocate(n);
        T *newFinish = mySTL::uninitialized_copy(begin(), end(), newStart);
        destroyAndDeallocateAll();
    
        start_ = newStart;
        finish_ = newFinish;
        endOfStorage_ = start_ + n;
    }

*  删除所有元素

void clear() 
    {
        erase(begin(), end()); 
    }

*  释放内存

template<class T, class Alloc>
    void vector<T, Alloc>::clear(){
        dataAllocator::destroy(start_, finish_);
        finish_ = start_;
    }

**5.4辅助函数**

*  赋值,用于构造插入元素等

template<class T, class Alloc>
    template<class InputIterator>
    void vector<T, Alloc>::reallocateAndCopy(iterator position, InputIterator first, InputIterator last){
        difference_type newCapacity = getNewCapacity(last - first);//需要申请空间大小
    
        T *newStart = dataAllocator::allocate(newCapacity);//申请空间
        T *newEndOfStorage = newStart + newCapacity;
        T *newFinish = mySTL::uninitialized_copy(begin(), position, newStart);//把begin到position赋值给新地址的头
        newFinish = mySTL::uninitialized_copy(first, last, newFinish);//插入需要插入的值到新地址的尾
        newFinish = mySTL::uninitialized_copy(position, end(), newFinish);//剩下的元素拷贝过来
    
        destroyAndDeallocateAll();//释放空间
        start_ = newStart;//重新定义
        finish_ = newFinish;
        endOfStorage_ = newEndOfStorage;
    }

六、vector使用算法

vector 的编写使用了 `#include "Algoritm.h"` 和 `#include "Allocator.h"` 中的泛函算法，具体包括:

*  分配空间

pointer allocate (size_type n, allocator<void>::const_pointer hint=0);

*  填充元素

void construct(T* p,const T* val);插入元素

*  释放空间

void deallocate (pointer p, size_type n);释放空间

*  填充元素到目的区间

void uninitialized_fill(ForwardIt first, ForwardIt last, const T& value);

*  复制填充元素到目的区间

uninitialized_copy( InputIterator first, InputIterator last, ForwardIterator result);

*  在指定位置插入 count 个 元素

void uninitialized_fill_n( ForwardIt first, Size count, const T& value );

七、vector实例测试

在上面我们已经写了许多成员函数，接下来我们运用自己写的 vector 编写一个程序来测试一下效果，这里我们需要在 `Test`目录下创建 `vectortest.cpp`。

#include "Vector.h"
    #include <iostream>
    #include "Algorithm.h"
    
    int summing(mySTL::vector<int> val)
    {
        int sum = 0;
        mySTL::vector<int>::iterator ix = val.begin();
        for (;ix != val.end(); ix++)
            sum += *ix;//求和
        return sum;
    }
    
    void print(mySTL::vector<int> val){
        mySTL::vector<int>::iterator ix = val.begin();
        for (;ix != val.end(); ix++)
         std::cout<<*ix<<" ";
        std::cout<<std::endl;
    }
    
    int main(int argv,char *argc[])
    {
        int sum;
        int input[5];
        std::cout<<"enter 5 numbers"<<std::endl;
        for(int i = 0;i < 5;i++)
        {
            std::cin>>input[i];//输入5个参数
        }
        mySTL::vector<int> val(input,input + 5);
    
        if(val.size() == 0)//判断a是否为空
        {
            std::cout<<"no element?"<<std::endl;
            return -1;
        }
    
        std::cout<<"The vector of val:"<<std::endl;
        print(val);
    
        std::cout<<"After insert:"<<std::endl;
        mySTL::vector<int>::iterator it = val.begin();
        mySTL::advance(it,2);
        val.insert(it,2,3);
        print(val);
    
        std::cout<<"The size of val:"<<std::endl;
        std::cout<<val.size()<<std::endl;
    
        std::cout<<"After pushback:"<<std::endl;
        val.push_back(11);
        print(val);
    
        std::cout<<"After erase:"<<std::endl;    
        val.erase(it);
        print(val);
    
        std::cout<<"After popback:"<<std::endl;
        val.pop_back();
        print(val);    
    
        sum = summing(val);
        std::cout<<"The sum of val = "<<sum<<std::endl;
    
    
        std::cout<<"After sort:"<<std::endl;
        mySTL::vector<int>::iterator beg = val.begin();
        mySTL::vector<int>::iterator end = val.end();
        mySTL::sort(beg,end);
        print(val);
        return 0;
    }

在命令行中执行如下代码：

g++ vectortest.cpp -std=c++11 -o vectortest -I ../include

![此处输入图片的描述][wm]

八、实验总结

通过以上的学习，我们了解到 vector 的构造和成员函数的编写，也间接领悟到了 STL 的便捷与强大，通过对 vector 编写我们可以更加深刻的理解 vector 的用法，在接下来的实验中，我们还会掌握更多的知识。

[wm]: /images/20220413/be7f88e6acd641daab82e44e22d720f7.png