欢迎来到我的Blog，点击关注哦💕

【C++】vector介绍以及模拟实现

前言vector介绍

vector常见操作构造函数iteratorcapacitymodify

`vector`模拟实现存储结构默认构造函数构造函数拷贝构造函数赋值运算符重载析构函数

容量（capacity）`size`和`capzcity`reserveresize

修改（modify）push_back直接将`_finsih`位置解引用赋值，`++_finsih`

pop_backinserterase

元素访问（Element access）operator [ ]

迭代器（iterator）

源码

前言

<code>string的特性和用法以及底层的探索已经，虽然string不算container的成员之一，但是也见到了其的影子，接下来让我们看看vector

vector介绍

vector 是 C++ 标准模板库（STL）中的一个动态数组容器，它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的，这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存，不需要手动分配和释放，支持常见容器操作，如插入、删除、遍历等.

vector常见操作

构造函数

iterator

capacity

modify

vector模拟实现

存储结构

结构上使用命名空间myvector进行封装，防止与库冲突，使用class封装成为对象vector

这样typedef的一点是和STL保持一致

写vector写成类模板，可以支持存贮多种类型数据_start表示数据存储的开始地址_finish表示数据存贮的的下一个地址_end_of_storage表示数据当前开辟的最大空间的地址

namespace myvector

{

template<class T>

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

private:

iterator _start;

iterator _finish;

iterator _end_of_storage;

};

}

默认构造函数

构造函数

初始化是使用的都是空指针

vector()

:_start(nullptr)

, _finish(nullptr)

, _end_of_storage(nullptr)

{ }

使用n个val初始化对象

vector(size_t n, const T& val = T())

{

resize(n, val);

}

根据可以模板的嵌套的性质，再次进行模板的定义这是使用两个迭代器的进行初始化

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

拷贝构造函数

利用一个对象初始化另外一个对象传引用new出和传递的对象一样大小的空间，在string类中我们利用了mencpy进行拷贝，在vector中不采用mencpy

mencpy拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝在这里面进行依次赋值，或者push_back 最后进行_finish和_end_of_storage的初始化

vector(const vector<T>& v)

{

_start = new T[v.capacity()];

for (size_t i = 0; i < v.size(); i++)

{

_start[i] = v._start[i];

}

_finish = _start + v.size();

_end_of_storage = _start + v.capacity();

}

赋值运算符重载

在operator=的参数中是值传递，是实参的拷贝，这里面利用这个特性进数据的交换返回this指针就是赋值的内容了

void swap(vector<T> v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_end_of_storage, v._end_of_storage);

}

vector<T> operator=(vector<T> v)

{

swap(v);

return *this;

}

析构函数

判断_start是否为空为空，避免再次析构

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

容量（capacity）

size和capzcity

vector的size和capacity不同于string类中的不一样，vector定义的是指针充分利用只针的特性，（指针—指针）是数值，可以计算出capacity和size

size_t size()const

{

return _finish - _start;

}

size_t capacity()const

{

return _end_of_storage - _start;

}

reserve

开始判断需要扩容的大小是否大于capacity，以避免重复扩容效率低下在开始时候记录原始空间的大小，是为了避免迭代器失效

进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的_start _finish _end_of_storage已经失效 这里还是采用在这里面进行依次赋值，或者push_back更新_start _finish _end_of_storage

void reserve(size_t n)

{

if (n > capacity())

{

T* tmp = new T[n];

size_t sz = size();

if (_start)

{

//memcpy(tmp, _start, sizeof(T)*capacity());

//string 类深拷贝

for (int i = 0; i < sz; i++)

{

tmp [i] = _start[i];

}

delete[] _start;

}

_start = tmp;

_finish = sz + _start;

_end_of_storage = _start + n;

}

}

resize

两种情况

N<capacity

直接进行移动_finish

N>capacity

进行容量的检查和扩容，依次赋值val

const T& val = T()这句话是针对内置类型和自定义类型，C++这里将内置类型进行了升级

int = 1; <=> int(1);//这里int有点像构造函数

void resize(size_t n, const T& val = T())

{

if (n < capacity())

{

_finish = n + _start;

}

else

{

reserve(n);

while (_finish != _start + n)

{

*_finish = val;

++_finish;

}

}

}

修改（modify）

push_back

首先进行容量的检查

直接将_finsih位置解引用赋值，++_finsih

void push_back(const T& x)

{

if (_finish == _end_of_storage)

{

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(newcapacity);

}

*_finish = x;

++_finish;

}

pop_back

复用erase

void pop_back()

{

erase(end()-1);

}

insert

进行断言，防止pos越界访问判断空间的大小_finish == _end_of_storagesize_t step = pos - _start用step记录，距离 _start距离，扩容的时候将原空间释放，pos将无法访问,扩容完成后进行pos的恢复将pos位置的数据依次进行移动、插入pos位置的值，修改_finish为了避免迭代器失效，返回现在的位置pos

iterator insert(iterator pos, const T& x)

{

assert(pos <= _finish && pos >= _start);

if (_finish == _end_of_storage)

{

//防止迭代器失效

size_t step = pos - _start;

size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2;

reserve(newcapacity);

//防止迭代器失效

pos = _start + step;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

++end;

}

*pos = x;

++_finish;

return pos

}

erase

进行断言，防止pos越界访问将pos后面的元素向前面移动，进行覆盖为了避免迭代器失效，返回现在的位置pos

iterator erase(iterator pos)

{

assert(pos <= _finish && pos >= _start);

while (pos != _finish)

{

*pos = *(pos + 1);

pos++;

}

--_finish;

return pos

}

元素访问（Element access）

operator [ ]

实现const和非const两种，只读和可读可改充分利用字符串特性可以进行下标的访问

T& operator[](size_t pos)

{

assert(pos >= 0 && pos < size());

return _start[pos];

}

const T& operator[](size_t pos)const

{

assert(pos >= 0 && pos < size());

return _start[pos];

}

迭代器（iterator）

本质还是指针，直接进行指针的返回就好

//iterator

const_iterator cbegin()

{

return _finish;

}

const_iterator cend() const

{

return _start;

}

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin()const

{

return _start;

}

const_iterator end()const

{

return _finish;

源码

#include <string.h>

#include <assert.h>

#include <iostream>

namespace MyVector

{

template <class T>

class vector

{

public:

//iterator

const_iterator cbegin()

{

return _finish;

}

const_iterator cend() const

{

return _start;

}

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin()const

{

return _start;

}

const_iterator end()const

{

return _finish;

}

//默认构造

vector()

:_start(nullptr)

, _finish(nullptr)

, _end_of_storage(nullptr)

{ }

vector(size_t n, const T& val = T())

{

resize(n, val);

}

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

vector(const vector<T>& v)

{

_start = new T[v.capacity()];

for (size_t i = 0; i < v.size(); i++)

{

_start[i] = v._start[i];

}

_finish = _start + v.size();

_end_of_storage = _start + v.capacity();

}

void swap(vector<T> v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_end_of_storage, v._end_of_storage);

}

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

vector<T> operator=(vector<T> v)

{

swap(v);

return *this;

}

//capacity

void reserve(size_t n)

{

if (n > capacity())

{

std::cout << "reserve(size_t n)" << std::endl;

T* tmp = new T[n];

size_t sz = size();

if (_start)

{

//memcpy(tmp, _start, sizeof(T)*capacity());

//string 类深拷贝

for (int i = 0; i < sz; i++)

{

tmp [i] = _start[i];

}

delete[] _start;

}

_start = tmp;

_finish = sz + _start;

_end_of_storage = _start + n;

}

}

size_t size()

{

return _finish - _start;

}

size_t capacity()

{

return _end_of_storage - _start;

}

size_t size()const

{

return _finish - _start;

}

size_t capacity()const

{

return _end_of_storage - _start;

}

//modify

void push_back(const T& x)

{

if (_finish == _end_of_storage)

{

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(newcapacity);

}

*_finish = x;

++_finish;

}

void pop_back()

{

erase(end()-1);

}

void insert(iterator pos, const T& x)

{

assert(pos <= _finish && pos >= _start);

if (_finish == _end_of_storage)

{

//防止迭代器失效

size_t step = pos - _start;

size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2;

reserve(newcapacity);

//防止迭代器失效

pos = _start + step;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

++end;

}

*pos = x;

++_finish;

return pos;

}

void erase(iterator pos)

{

assert(pos <= _finish && pos >= _start);

while (pos != _finish)

{

*pos = *(pos + 1);

pos++;

}

--_finish;

return pos;

}

void resize(size_t n, const T& val = T())

{

if (n < capacity())

{

_finish = n + _start;

}

else

{

reserve(n);

while (_finish != _start + n)

{

*_finish = val;

++_finish;

}

}

}

T& operator[](size_t pos)

{

assert(pos >= 0 && pos < size());

return _start[pos];

}

const T& operator[](size_t pos)const

{

assert(pos >= 0 && pos < size());

return _start[pos];

}

private:

iterator _start;

iterator _finish;

iterator _end_of_storage;

};

}