STL之vector容器的介绍与模拟实现

STL之vector容器的介绍与模拟实现

所属专栏：C“嘎嘎" 系统学习❤️
🚀 >博主首页：初阳785❤️
🚀 >代码托管：chuyang785❤️
🚀 >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️
🚀 >博主也会更加的努力，创作出更优质的博文！！❤️

1. 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容器使用

一下垒列出的都是一些比较重要的接口。

2.1vectord 定义

(constructor)构造函数声明接口说明
vector()（重点）无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x);（重点） 拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

2.2 vector iterator 的使用

iterator的使用接口说明
begin +end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

2.3 vector 空间增长问题

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize（重点）改变vector的size
reserve （重点）改变vector的capacity

2.4 注意事项

  1. capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
    这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义
    的。vs是PJ版本STL，g++是SGI版本STL。
  2. reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
  3. resize在开空间的同时还会进行初始化，影响size。

3. vector功能模拟实现

3.1 架构搭建

  • 由于本次的模拟实现是基于STL库源码来模拟实现的，所以我们的本次模拟实现的整体构架是来自STL源码库的

1.首先为了防止与库里面的STL发生冲突，首先就要设置命名空间。
2.其次，从使用vector容器来看，我们容器中可以存放各种数据类型的数据，所以要用到模板。
3.在STL标准库中，使用三个指针来确定容器capacity，size的。_start指向数据块的开始，_finish指向有效数据的尾，_endOfStorage指向存储容量的尾。有了这三个指针，我们可以计算出大小，容量，以及迭代器的返回。

namespace qfw
{
	template<calss T>
	class vector
	{
	public:
		typedef T* iterator;
        typedef const T* const_iterator;
        
		vector()
		{……}
		
		~vector()
		{……}
		
	private:
		iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
	};
}

3.2 空间控制板块

  1. 返回数据的大小size()
size_t size() const
{
    return _finish - _start;
}
  1. 返回容器的容量capacity()
size_t capacity() const
{
    return _endOfStorage - _start;
}
  1. 修改容器的容量reserve()
    在这里插入图片描述
void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old = size();//记录原来_finish的位置，防止迭代器失效
        T* tmp = new T[n];//开新的的空间
        //将数据拷贝到新的空间
        for (int i = 0; i < old; i++)
        {
            tmp[i] = _start[i];
        }
        //删除旧的空间
        delete[] _start;
        //指向新新空间，更新数据
        _start = tmp;
        _finish = _start + old;
        _endOfStorage = _start + n;
    }
}
  1. 修改容器数据的大小resize()
void resize(size_t n, const T& value = T())
{
    if (n > size())
    {
        reserve(n);
        while (_finish < _start + n)
        {
            *_finish = value;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}

注意：这里用到的缺省参数的知识点，但是我们容器是可以存放各种数据类型的数据的，所以我们的缺省值因该也是要对应着给对应的缺省值的也就是T()。但是这个也不是好理解，如果是T是string类型的话，string()是一个匿名对象，回去调用string的默认构造，也就是说如果T类型是自定义类型的话说的过来，它回去调用它的默认构造。但是如果T是内置类型的话怎么办，我们之前学习的时候是了解到内置类型是没有默认构造的，那这里怎么说到过去呢？所以为了解决这个问题，C++给内置类型开了后面，允许内置类型有默认构造。

3.3 迭代器

迭代器提供两个版本，const和非const版本。

iterator begin()
{
    return _start;
}
iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}
const_iterator end() const
{
    return _finish;
}

3.4 增加/删除数据

  1. 尾插push_back()
void push_back(const T& x)
{
    if (_finish == _endOfStorage)
    {
        int newcapcity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapcity);
    }
    *(_finish) = x;
    ++_finish;
}
  1. 尾删pop_back()
void pop_back()
{
    assert(_finish >= _start);
    --_finish;
}
  1. 在任意位置增加insert()
iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _endOfStorage)
    {
        //防止扩容的时候迭代器失效
        size_t old = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + old;
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    ++_finish;
    *pos = x;

    return pos;
}
  1. 在任意位置删除erase()
iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator cur = pos + 1;
    while (cur < _finish)
    {
        *(cur - 1) = *cur;
        cur++;
    }
    --_finish;
}

3.5 运算符重载

T& operator[](size_t pos)
{
    return _start[pos];
}
const T& operator[](size_t pos)const
{
    return _start[pos];
}

3.6构造/析构

//默认构造调用初始化列表，调用缺省值
vector()
{}

//有参构造
vector(int n, const T& value = T())
{
    resize(n);
}

//区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first < last)
    {
        push_back(*first);
        ++first;
    }
}

//拷贝构造
vector(const vector<T>& v)
{
    reserve(v.capacity());
    for (const auto& e : v)
    {
        push_back(e);
    }
}

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

//赋值
vector<T>& operator= (vector<T> v)//注意这里串的不是引用，而是值转递
{
    swap(v);
    return *this;
}

//析构
~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}

4. 整体代码

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;

namespace qfw
{
    template<class T>
    class vector
    {
    public:
        // Vector的迭代器是一个原生指针
        typedef T* iterator;
        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;
        }

        // construct and destroy
        vector()
        {}

        vector(int n, const T& value = T())
        {
            resize(n);
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first < last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造
        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (const auto& e : v)
            {
                push_back(e);
            }
        }

        //赋值
        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }

        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }
        // capacity
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _endOfStorage - _start;
        }
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t old = size();
                T* tmp = new T[n];//开新的的空间
                //将数据拷贝到新的空间
                for (int i = 0; i < old; i++)
                {
                    tmp[i] = _start[i];
                }
                //删除旧的空间
                delete[] _start;
                //指向新新空间，更新数据
                _start = tmp;
                _finish = _start + old;
                _endOfStorage = _start + n;
            }
        }
        void resize(size_t n, const T& value = T())
        {
            if (n > size())
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

        ///access///
        T& operator[](size_t pos)
        {
            return _start[pos];
        }
        const T& operator[](size_t pos)const
        {
            return _start[pos];
        }

        ///modify/
        void push_back(const T& x)
        {
            if (_finish == _endOfStorage)
            {
                int newcapcity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapcity);
            }
            *(_finish) = x;
            ++_finish;
        }
        void pop_back()
        {
            assert(_finish >= _start);
            --_finish;
        }
        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }
        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start);
            assert(pos <= _finish);

            if (_finish == _endOfStorage)
            {
                //防止扩容的时候迭代器失效
                size_t old = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + old;
            }

            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            ++_finish;
            *pos = x;

            return pos;
        }
        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);

            iterator cur = pos + 1;
            while (cur < _finish)
            {
                *(cur - 1) = *cur;
                cur++;
            }
            --_finish;
        }
    private:
        iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
    };
}