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

2024-01-22 01:03:51 作者:欧亿体育

文章目录


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的使用

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

2.1 vector的定义

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

代码实现:

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 中迭代器底层也是原生指针。

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


模拟实现:

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 
#include 
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;
}

2.3 vector的空间增长问题

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

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 
#include 
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;
}


3、vector的增删查改

vector增删查改 接口说明
push_back(重点) 尾插
pop_back(重点) 尾删
find 查找
insert 在position之前插入val
erase 删除position位置的数据
swap 交换两个vector的数据空间
operator[](重点) 像数组一样访问

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);
}

*** 本篇结束 ***

在线咨询 拨打电话

电话

010-67916526

微信二维码

微信二维码