[C++] STL_vector使用与常用接口的模拟实现

向右看齐 2023-10-15 10:31 135阅读 0赞

![在这里插入图片描述][72aee3880771405d95f6b6d8fb46330e.gif_pic_center]

#### 文章目录 ####

*  1、vector的介绍
 *  2、vector的使用
 *   *  2.1 vector的定义
     *  2.2 vector迭代器的使用
     *  2.3 vector的空间增长问题
 *  3、vector的增删查改
 *   *  3.1 push\_back（重点）
     *  3.2 pop\_back（重点）
     *  3.3 operator\[\]（重点）
     *  3.4 insert
     *  3.5 erase
     *  3.6 swap

## 1、vector的介绍 ##

[vector文档介绍][vector]

> 1.  vector是表示可变大小数组的序列容器。
> 2.  就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
> 3.  本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
> 4.  vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
> 5.  因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
> 6.  与其它动态序列容器相比（deque, list and forward\_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward\_list统一的迭代器和引用更好。

## 2、vector的使用 ##

vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，**下面列出了哪些接口是要重点掌握的并且会模拟实现。**

### 2.1 vector的定义 ###

<table> 
 <thead> 
  <tr> 
   <th>(<a href="https://cplusplus.com/reference/vector/vector/vector/" rel="nofollow">constructor</a>)构造函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>vector()（重点）</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>vector（size_type n, const value_type&amp; val = value_type()</td> 
   <td>构造并初始化n个val</td> 
  </tr> 
  <tr> 
   <td>vector (const vector&amp; x); （重点）</td> 
   <td>拷贝构造</td> 
  </tr> 
  <tr> 
   <td>vector (InputIterator first, InputIterator last);</td> 
   <td>使用迭代器进行初始化构造</td> 
  </tr> 
 </tbody> 
</table>

代码实现：

template<class T>
        class vector
        {
        
        public:
        	typedef T* iterator;//typedef愿意给别人用就放在public，不想就放在private
            typedef const T* const_iterator;
    
        	vector()
            {
        }
    
            vector(int n, const T& value = T())
            {
        
                reserve(n);
                for (size_t i = 0; i < n; i++)
                {
        
                    push_back(value);
                }
            }
    
            template<class InputIterator>
    
            vector(InputIterator first, InputIterator last)
            {
        
                while (first != last)
                {
        
                    push_back(*first);
                    ++first;
                }   
            }
    
            vector(const vector<T>& v)
            {
        
                reserve(v.capacity());
                for (auto& e : v)
                {
        
                    push_back(e);
                }
            }
    
        private:
        iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
    };

### 2.2 vector迭代器的使用 ###

在 vector 中迭代器底层也是原生指针。

<table> 
 <thead> 
  <tr> 
   <th>iterator的使用</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin + end(重点)</td> 
   <td>获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator</td> 
  </tr> 
  <tr> 
   <td>rbegin + rend</td> 
   <td>获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][0d4cc2e3fc504070ac3895f3ff4ff394.png]  
模拟实现：

typedef T* iterator;//typedef愿意给别人用就放在public，不想就放在private
    typedef const T* const_iterator;
    
    iterator begin()
    {
        
        return _start;
    }
    
    iterator end()
    {
        
        return _finish;
    }
    
    const_iterator begin() const
    {
        
        return _start;
    }
    
    const_iterator end() const
    {
        
        return _finish;
    }

**使用：**  
迭代器一般使用在遍历，我们来看一下。

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
        
    	vector<int> v;
    	//我们这里使用push_back来插入数据
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    	v.push_back(5);
    
    	//迭代器方式遍历
    	vector<int>::iterator it = v.begin();
    	while (it != v.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    
    	return 0;
    }

![在这里插入图片描述][6ac7800837504b37bb392f8fc3d04170.png]

### 2.3 vector的空间增长问题 ###

<table> 
 <thead> 
  <tr> 
   <th>容量空间</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size</td> 
   <td>获取数据个数</td> 
  </tr> 
  <tr> 
   <td>capacity</td> 
   <td>获取容量大小</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>判断是否为空</td> 
  </tr> 
  <tr> 
   <td>resize（重点）</td> 
   <td>改变vector的size</td> 
  </tr> 
  <tr> 
   <td>reserve（重点）</td> 
   <td>改变vector的capacity</td> 
  </tr> 
 </tbody> 
</table>

**reserve接口：**  
**reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。**

void reserve(size_t n)//reserve只扩不缩
    {
        
        if (n > capacity())
        {
        
            T* tmp = new T[n];
            size_t sz = size();//这里必须先记下sz，_finish要是直接+size()会出问题
                               //_start指的是新空间，调用size()，size()内部会出问题
                               //因此先记下来后面用最合适
            if (_start)
            {
        
                //memcpy是浅拷贝，会出问题
                //memcpy(tmp, _start, sizeof(T) * sz);
                for (size_t i = 0; i < size(); i++)
                {
        
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
    
            _start = tmp;
            _finish = _start + sz;
            _endOfStorage = _start + n;
        }
    }

**resize接口：  
resize在开空间的同时还会进行初始化，影响size。**

void resize(size_t n, const T& value = T())//匿名对象/临时对象具有常性，需要const修饰
    {
        
        if (n <= size())//缩容
        {
        
            _finish = _start + n;
        }
        else
        {
        
            reserve(n);//这里可以不用判断是否要扩容，reserve里面会判断
    
            while (_finish < _start + n)
            {
        
                *_finish = value;
                ++_finish;
            }
        }
    }

其他几个接口比较简单，直接实现：

size_t size() const
    {
        
        return _finish - _start;
    }
    
    size_t capacity() const
    {
        
        return _endOfStorage - _start;
    }
    
    bool empty()
    {
        
    	return _finish - _start == 0;
    }

**注意：**

在扩容的时候有一个区别，**vs下capacity是按1.5倍增长的，g++是按2倍增长的**。不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。  
**我们来测试一下：**

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
        
    	vector<int> v;
    	size_t sz = v.capacity();
    
    	for (size_t i = 0; i < 100; i++)
    	{
        
    		v.push_back(i);
    		if (sz != v.capacity())
    		{
        
    			sz = v.capacity();
    			cout << "capacity changed：" << sz << endl;
    		}
    	}
    
    	return 0;
    }

![在这里插入图片描述][e47dbcd1190048ad8911121436a26e93.png]  
![在这里插入图片描述][3214399b1a12489398b4248b9bf5d663.png]

## 3、vector的增删查改 ##

<table> 
 <thead> 
  <tr> 
   <th>vector增删查改</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push_back（重点）</td> 
   <td>尾插</td> 
  </tr> 
  <tr> 
   <td>pop_back（重点）</td> 
   <td>尾删</td> 
  </tr> 
  <tr> 
   <td>find</td> 
   <td>查找</td> 
  </tr> 
  <tr> 
   <td>insert</td> 
   <td>在position之前插入val</td> 
  </tr> 
  <tr> 
   <td>erase</td> 
   <td>删除position位置的数据</td> 
  </tr> 
  <tr> 
   <td>swap</td> 
   <td>交换两个vector的数据空间</td> 
  </tr> 
  <tr> 
   <td>operator[]（重点）</td> 
   <td>像数组一样访问</td> 
  </tr> 
 </tbody> 
</table>

### 3.1 push\_back（重点） ###

我们梳理尾插的思路：  
1、先判断容量是否满了，如果满了先扩容。这里注意，尾插的时候是否为空，这里使用三木操作符进行判断一下，如果为空先扩4个空间，否则2倍扩法。  
2、尾插，再++\_finish。

void push_back(const T& x)
    {
        
        if (_finish == _endOfStorage)
        {
        
            reserve(capacity() == 0 ? 4 : 2 * capacity());
        }
    
        *_finish = x;
        ++_finish;
    }

### 3.2 pop\_back（重点） ###

在尾删的时候我们依然是先判断  
这次我们需要判空，用断言assert(\_finish - \_start != 0)，再去尾删，让\_finish–就好了，下一次尾插的时候直接覆盖。

void pop_back()
    {
        
        assert(_finish-_start != 0);
    
        --_finish;
        //erase(end() - 1);
    }

### 3.3 operator\[\]（重点） ###

\[\]的重载就是返回pos位置上数据就可以，比较简单直接秒杀。  
我们这里给两个接口，一个是只读的，一个是可以修改的。

T& operator[](size_t pos)//写
    {
        
        assert(pos < size());//判断位置是否合法
        return _start[pos];
    }
    
    const T& operator[](size_t pos)const//读
    {
        
        assert(pos < size());
        return _start[pos];
    }

### 3.4 insert ###

insert是在pos位置插入一个数据。  
**思路：**  
1、先判断pos位置是否合法；  
2、判满，如果满了就需要扩容，在扩容的时候需要注意迭代器失效的问题；  
3、因为插入数据就存在挪动数据，因此需要先挪动数据，我们 **从后往前** 依次后移一个位置的数据，挪到pos位置；  
4、再去给pos位置插入数据，最后返回pos位置。

iterator insert(iterator pos, const T& x)
    {
        
        assert(pos >= _start);
        assert(pos <= _finish);
    
        if (_finish == _endOfStorage)
        {
        
            size_t len = pos - _start;//先记下_start到pos位置的距离，因为扩容后迭代器pos就会失效
            reserve(capacity() == 0 ? 4 : 2 * capacity());
            pos = _start + len;//新的空间需要更新迭代器pos
        }
    
        iterator end = _finish - 1;
        //挪动数据
        while (end >= pos)
        {
        
            *(end + 1) = *end;
            --end;
        }
    
        *pos = x;
        ++_finish;
    
        return pos;
    }

### 3.5 erase ###

erase是删除pos位置的数据。  
**思路：**  
1、判断pos位置是否合法；  
2、挪动数据，从 **pos位置到尾** 依次向前挪动数据，直接用pos+1的数据覆盖掉pos位置的数据即可；  
3、–\_finish，返回pos位置即可。

iterator erase(iterator pos)
    {
        
        assert(pos >= _start);
        assert(pos < _finish);
    
        iterator it = pos + 1;
        //挪动数据
        while (it < _endOfStorage)
        {
        
            *(it - 1) = *it;
            ++it;
        }
        --_finish;
    
        return pos;
    }

### 3.6 swap ###

我们vector的swap直接套用库函数的swap来实现就好了。

void swap(vector<T>& v)
    {
        
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }

\*\*\* 本篇结束 \*\*\*

[72aee3880771405d95f6b6d8fb46330e.gif_pic_center]: https://img-blog.csdnimg.cn/72aee3880771405d95f6b6d8fb46330e.gif#pic_center
[vector]: https://cplusplus.com/reference/vector/vector/
[0d4cc2e3fc504070ac3895f3ff4ff394.png]: https://img-blog.csdnimg.cn/0d4cc2e3fc504070ac3895f3ff4ff394.png
[6ac7800837504b37bb392f8fc3d04170.png]: https://img-blog.csdnimg.cn/6ac7800837504b37bb392f8fc3d04170.png
[e47dbcd1190048ad8911121436a26e93.png]: https://img-blog.csdnimg.cn/e47dbcd1190048ad8911121436a26e93.png
[3214399b1a12489398b4248b9bf5d663.png]: https://img-blog.csdnimg.cn/3214399b1a12489398b4248b9bf5d663.png