当前位置：网站首页>Vector容器的底层实现
Vector容器的底层实现
2022-07-26 22:45:00 【江南伯爵.】
Vector
Vector同样是STL六大组件之一，简单来讲他就是一个封装了动态大小数组的顺序容器，同时他可以存入各种各样的对象，比如int，char，string类型等等
因为其本质上是一个顺序容器，所以他是按照顺序的方式进行存储，和数组类似，并且他能够动态的存储，即容器可以进行插入删除，改变大小
类成员
private:
iterator _start;
iterator _last;
iterator _endofstorage;
_start是头指针，_last是尾指针，_endofstorage是最多能够存储到的为位置（容器大小）
ps：iterator迭代器指针在后面哦
构造函数，拷贝构造函数和析构函数
vector()
:_start(nullptr)//均为空指针
,_last(nullptr)
,_endofstorage(nullptr)
{
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)//此构造函数，可以让别的容器
: _start(nullptr) //能够存入vector容器中
, _last(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);//逐个插入
++first;
}
}
// v2(v1)，传统写法
vector(const vector<T>& v)
:_start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)//可以直接通过范围for来逐个插入到v2中，不用像现代写法重新开辟tmp的vector对象
{
push_back(e);
}
}
~vector()
{
delete[] _start;//记得加[]哦
_last = nullptr;
_start = nullptr;
_endofstorage = nullptr;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_last, v._last);
std::swap(_endofstorage, v._endofstorage);
}
//现代写法v1=v2
vector<T>& operator=(vector<T> v)//这里没用使用引用，即在创建v时会开辟一个新的空间
{
swap(v);//此时直接调用swao函数即可，且v为形参，swap后获得this原本的数据，函数结束时v同原本this数据一同释放
return *this;
}
在Vector容器内同样是进行深拷贝的
这里我没有写=的传统写法和()的现代写法，感兴趣的小伙伴可以自己去了解一下哦
迭代器
这里使用了模板，使得vector可以传入各种类型的数据
typedef T* iterator;//对象的内容可以进行读写操作
typedef const T* const_iterator;//对象的内容只能进行读操作
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _last;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _last;
}
在这里和String的迭代器一样，他们的本质是指针，但是对于别的容器他们的本质就并不是指针了，后面的写到list容器时我会解释，不过要记住迭代器是为了让我们对容器的操作使用起来像指针一样
函数功能
size_t size()//对象的大小
{
return _last - _start;
}
size_t capacity()//对象的容量
{
return _endofstorage - _start;
}
bool empty()//是否为空
{
return _start == _last;
}
void reserve(size_t n)//开空间
{
if (n > size())
{
size_t sz = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * sz);
_start = tmp;
_last = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n,const T& val=T())
{
if (n <= size())
{
_last = _start + n;//是减小大小，而不是扩大
}
else
{
if (n > capacity())
{
reserve(n);
}
while(_last<_start+n)//不用等于，因为_last是指向有效字符的后一位
{
*_last= val;
_last++;
}
}
}
T& operator[](size_t n)//可以和数组一样使用
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}
void Push_back(const T& x)
{
/*if (_last==_endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_last = x; ++_last;*/
insert(end(), x);
}
void Pop_back()
{
assert(!empty());
--_last;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _last);
if (_last == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}//此语句是为了提高复用性，可以直接对Push_back进行复用
//size_t len = pos - _start;
//iterator end = _last + 1;
//if (_last == _endofstorage)
//{
// reserve(capacity() + 1);
//}
//pos = _start + len;//注意：重新开空间后pos也变成野指针；所以要重新找回来
//end = _last;//注意：end必须在if语句后面在写一次，因为resrve函数会重新开空间，不然end会变成野指针
iterator end = _last;
while (end >= pos)
{
*end = *(end - 1);//注，这里不能用--end，因为前面的end也会被改变
--end;
}
*pos = x;
++_last;
return pos;//为了给用户能够重新使用原本指向的数，避免野指针的情况
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _last);
iterator end = pos + 1;
while (end < _last)
{
*(end - 1) = *end;//注，这里不能用--end，因为前面的end也会被改变
++end;
}
--_last;
return pos;//同样为了避免野指针问题，给用户一个返回值，是被删元素的后面一个值
}
vector的功能和string的大致相同，值得注意的是，vector里面的insert和erase函数，当使用了他们后，原先的迭代器就没有用了，成为了野指针，这是因为vector对象在插入时候，如果空间不足，会重新开辟一个新的空间，而迭代器指向的是原先空间的指针，便无法使用。但如果空间足够不需要开空间呢？迭代器仍然指向有效的空间，但是迭代器指向的值本不是我们原先的值，因为那个空间的数据经过移动，改变了，此时我们仍然视其为野指针。所以对于insert和erase函数，我们都会给一个返回的迭代器给用户接受使用，insert是插入的数据，erase是删除数据的下一个值
如
vector<int> v;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
vector<int>::iterator it = v.begin();
it = v.insert(it+1 , 9);
cout << *it << " ";
cout << endl;
完整代码
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _last;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _last;
}
vector()
:_start(nullptr)
,_last(nullptr)
,_endofstorage(nullptr)
{
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)//此构造函数，可以让别的拥有头尾迭代器的容器能够存入vector容器中
: _start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// v2(v1)，传统写法
vector(const vector<T>& v)
:_start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)//可以直接通过范围for来逐个插入到v2中，不用像现代写法重新开辟tmp的vector对象
{
push_back(e);
}
}
~vector()
{
delete[] _start;
_last = nullptr;
_start = nullptr;
_endofstorage = nullptr;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_last, v._last);
std::swap(_endofstorage, v._endofstorage);
}
//现代写法v1=v2
vector<T>& operator=(vector<T> v)//这里没用使用引用，即在创建v时会开辟一个新的空间
{
swap(v);//此时直接调用swao函数即可，且v为形参，swap后获得this原本的数据，函数结束时v同原本this数据一同释放
return *this;
}
size_t size()
{
return _last - _start;
}
size_t capacity()
{
return _endofstorage - _start;
}
bool empty()
{
return _start == _last;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = capacity();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * sz);
_start = tmp;
_last = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n,const T& val=T())
{
if (n <= size())
{
_last = _start + n;//是减小大小，而不是扩大
}
else
{
if (n > capacity())
{
reserve(n);
}
while(_last<_start+n)//不用等于，因为_last是指向有效字符的后一位
{
*_last= val;
_last++;
}
}
}
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}
void Push_back(const T& x)
{
/*if (_last==_endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_last = x; ++_last;*/
insert(end(), x);
}
void Pop_back()
{
assert(!empty());
--_last;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _last);
if (_last == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}//此语句是为了提高复用性，可以直接对Push_back进行复用
//size_t len = pos - _start;
//iterator end = _last + 1;
//if (_last == _endofstorage)
//{
// reserve(capacity() + 1);
//}
//pos = _start + len;//注意：重新开空间后pos也变成野指针；所以要重新找回来
//end = _last;//注意：end必须在if语句后面在写一次，因为resrve函数会重新开空间，不然end会变成野指针
iterator end = _last;
while (end >= pos)
{
*end = *(end - 1);//注，这里不能用--end，因为前面的end也会被改变
--end;
}
*pos = x;
++_last;
return pos;//为了给用户能够重新使用原本指向的数，避免野指针的情况
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _last);
iterator end = pos + 1;
while (end < _last)
{
*(end - 1) = *end;//注，这里不能用--end，因为前面的end也会被改变
++end;
}
--_last;
return pos;//同样为了避免野指针问题，给用户一个返回值，是被删元素的后面一个值
}
private:
iterator _start;
iterator _last;
iterator _endofstorage;
};
总结
vector和string基本相似，我们经常会使用到此容器，因为他是顺序结构，所以对于随机访问十分的方便，同样尾插尾删也很方便，但是对于插入删除（如头插头删），同样他也是进行深拷贝，所以能用引用尽量用引用，可以减少很多的空间使用
最后感兴趣的小伙伴可以看一下我的String容器的实现哦
边栏推荐
猜你喜欢
Finding the greatest common divisor
Shell（12）正则表达式
OJ question of sequence table
DNS
Jenkins -- Basic -- 04 -- install Chinese plug-ins
C language to realize mine sweeping game:
iptables 防火墙（一）
![[question] what if Yum resources are occupied](/img/8d/50129fa1b1ef0aa0e968e6e6f20969.png)
[question] what if Yum resources are occupied
Lamp+discuz Forum
Adding, deleting, checking and modifying dynamic sequence table with C language
随机推荐
4.1 It is super simple to install QT without using Sogou Chinese input method
Problems and solutions of paddleocr packaging
39安装 LNMP
十二、正则表达式
5、 Conditional statement of shell
Shell（13）三剑客
Download pronunciation pairs+ship or sheet+tree or three
14、 Sed
hdc_ std
Web服务（02）——Web服务器中间件
29shell function
8、 Definition of array
十五、expect
27shell conditional statement
The difference between if and else if
[unity] unity interface scene view [1]
34iptables firewall
C language problem solving -- let the balloon rise
Shell脚本——文件的备份，更新和回滚
ESP8266 STA_ Mode