STL 上头系列——vector 容器详解
带你一命通关 vector 容器十分钟手撕 STL 底层原理
传统艺能😎
小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我
🎉🎉🎉倾力打造转码社区微信公众号🎉🎉🎉
vector🤔
vector是表示可变大小数组的序列容器，本质上是一个支持动态开辟的顺序表。本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
他就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
vector分配空间的策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略来规划空间使用和分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，可以理解成以空间换时间，与其它容器相比（deques, lists 等），== vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效，对于其他不在末尾的删除和插入操作，相率更低==。
vector 的使用🤔
vector() 是无参构造，他的拷贝构造通常为：vector (const vector& x)，下面是 vector 的基本书写形式：
#include <iostream>
#include <vector>
int main()
{
std::vector<int> a; // 空的整型vector
std::vector<int> b(1,2); // 1个整型值为2
std::vector<int> c(b.begin(), b.end()); // 贯穿b的迭代器
std::vector<int> d(c); // c 的拷贝
int ints[] = { 1,2,3,4 };
std::vector<int> e(ints, ints + sizeof(ints) / sizeof(int));//非迭代器控制访问
}
迭代器的使用🤔
通常有两种方法：begin+end 和 rbegin+rend ，前者获取第一个数据位置的iterator/const_iterator， 后者获取最后一个数据的下一个位置的iterator/const_iterator。特别说明一下下面两种情况：
// const对象使用const迭代器进行遍历打印
void PrintVector(const vector<int>& v)
{
vector<int>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
// 使用反向迭代器进行遍历打印
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
PrintVector(v);
return 0;
}
reserve 和 resize🤔
reserve 和 resize 是 vector 里常见的两种重要接口。reserve只负责开辟空间，如果确定知道需要用多少空间，他可以缓解 vector 增容的代价缺陷问题。resize 在开空间的同时还会进行初始化，影响size。
reserve：
int main()
{
std::vector<int> v;
sz = v.capacity();
v.reserve(100); // 预先开出需要的空间
std::cout << "making v grow:\n";
for (int i = 0; i<100; ++i) {
v.push_back(i);
if (sz != v.capacity()) {
sz = v.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
return 0;
}
resize：
resize（n）的使用分为三种情况：
- n > size，扩容并将新添加的 （n-size） 个元素默认初始化为 0 插入，如果是 resize（n，t）就将新添加的元素初始化为 t
- n < size 直接将 （size+1） 位置置为 \0
int main()
{
std::vector<int> v;
for (int i = 1; i<10; i++)
v.push_back(i);
v.resize(10，10);//情况1
v.resize(5);//情况2
std::cout << "v contains:";
for (int i = 0; i<v.size(); i++)
std::cout << ' ' << v[i];
std::cout << '\n';
return 0;
}
vector 迭代器失效🤔
迭代器是存在分类的，大致分为三类：
在继承的知识中，双向可包含单向，随机又可以包含双向，这里 vector 就属于双向迭代器：
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际还是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T*。因此迭代器失效，其中一种情况就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃，如果继续使用已经失效的迭代器，程序可能会噶掉。这种情况可以统称为野指针：
一些涉及空间开辟的操作都有可能造成野指针的迭代器失效，比如 resize，reserve，insert 等操作
int main()
{
vector<int> v{ 1,2,3,4,5};
auto it = v.begin();
v.resize(100, 8);
v.reserve(100);
v.insert(v.begin(), 0)；
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
以上操作，都可能会导致 vector 发生扩容，也就是说 vector 旧空间会被释放掉，而在打印时，it 还使用的是释放之间的旧空间，在对 it 迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。要解决这个问题很简单，只需要将该操作赋值给迭代器就行，实质上这算是一种深拷贝。
erase 导致的非法访问：
int main()
{
int a[] = { 1, 2, 3};
vector<int> v(a, a + sizeof(a) / sizeof(int));
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
v.erase(pos);// 删除pos位置的数据，导致pos迭代器失效
cout << *pos << endl; // 非法访问
return 0;
}
erase删除pos位置元素后，pos位置之后的元素会往前搬移，理论上讲迭代器不应该会失效因为没有造成底层空间的改变，但是因为 pos 刚好是最后一个元素，删完之后 pos 是 end 的位置，而 end 位置是没有元素的，解引用会导致非法访问，那么pos就失效了。
其实深浅拷贝造成问题的场景也非常的，比如经典的杨辉三角：
这是杨辉三角实现的底层原理图，vv 是一个vectorT 的结构，有点类似于一个二维数组，对每层结构进行构建时需要用到 memcpy 函数，memcpy 是典型的浅拷贝，把上一个 vector 所有节点的值搬到下一个 vector，两个 vector 指向同一空间，再一手 delete 铁铁的迭代器失效，所以这个操作不慎就会造成千古恨。
第二种情况：迭代器意义更改导致失效，我们看一个场景，请问下面这个代码是否正确？
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it); //删除所有 vector 中的偶数对象
++it;
}
return 0;
}
表面上它是正确的，但是里面的错误却经不住细想，这个代码也没有底层空间上的错误，那问题出在哪里呢？我们不妨设想一下，删除操作完了剩下的数会自己前移对吧，但是这时迭代器所在位置仍然没变，那么结果就不正确，我们需要考虑到迭代器位置的更新，只要 erase 后 ++ 即可。
vector深度剖析🤔
这时侯捷老师在 《STL源码剖析》一书中的插图，生动形象的展示了 vector 的底层结构和原理。我们可以借此模拟实现一个 vector：
#pragma once
#include <assert.h>
namespace bite
{
template<class T>
class vector
{
public:
typedef T* iterator;
public:
vector()
: start(nullptr)
, finish(nullptr)
, endofstorage(nullptr)
{}
vector(int n, const T& data = T())
: start(new T[n])
, finish(start+n)
, endofstorage(finish)
{
for (int i = 0; i < n; ++i)
{
start[i] = data;
}
}
template<class Iterator>
vector(Iterator first, Iterator last)
{
// 确定该区间中有多少个元素
Iterator it = first;
size_t count = 0;
while (it != last)
{
count++;
++it;
}
// 给当前对象开辟空间，并初始化成员变量
start = new T[count];
finish = start;
endofstorage = start + count;
// 赋值
while (first != last)
{
*finish++ = *first++;
}
}
vector(const vector<T>& v)
{
size_t vsize = v.size();
start = new T[vsize];
finish = endofstorage = start + vsize;
for (size_t i = 0; i < vsize; ++i)
start[i] = v[i];
}
// 大家需要自己实现 赋值运算符重载&析构函数
~vector()
{
if (start)
{
delete[] start;
start = finish = endofstorage = nullptr;
}
}
///
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
//
// capacity
size_t size()const
{
return finish - start;
}
size_t capacity()const
{
return endofstorage - start;
}
bool empty()const
{
return start == finish;
}
void resize(size_t newsize, const T& data = T())
{
size_t oldsize = size();
if (newsize <= oldsize)
{
finish = start + newsize;
}
else
{
if (newsize > capacity())
reserve(newsize);
for (size_t i = oldsize; i < newsize; ++i)
start[i] = data;
finish = start + newsize;
}
}
void reserve(size_t newcapacity)
{
size_t oldcapacity = capacity();
size_t oldsize = size();
if (newcapacity > oldcapacity)
{
// 开辟新空间
T* temp = new T[newcapacity];
// 拷贝元素
//memcpy(temp, start, oldsize*sizeof(T));
for (size_t i = 0; i < oldsize; ++i)
temp[i] = start[i];
// 释放旧空间
delete[] start;
start = temp;
finish = start + oldsize;
endofstorage = start + newcapacity;
}
}
/
// acess
T& operator[](size_t index)
{
assert(index < size());
return start[index];
}
const T& operator[](size_t index)const
{
assert(index < size());
return start[index];
}
T& front()
{
return start[0];
}
const T& front()const
{
return start[0];
}
T& back()
{
return start[size()-1];
}
const T& back()const
{
return start[size() - 1];
}
///
// modify
void push_back(const T& data)
{
if (size() == capacity())
reserve(capacity() * 2+3);
*finish++ = data;
}
void pop_back()
{
if (empty())
return;
--finish;
}
iterator insert(iterator pos, const T& data)
{
assert(pos <= end());
if (size() == capacity())
reserve(capacity() * 2);
auto it = end();
while (it > pos)
{
*it = *(it - 1);
--it;
}
*pos = data;
++finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos < end());
if (size() == 1)
{
pop_back();
return end();
}
auto it = pos;
while (it < end())
{
*it = *(it + 1);
++it;
}
--finish;
return pos;
}
void clear()
{
finish = start;
}
void swap(const vector<T>& v)
{
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(endofstorage, v.endofstorage);
}
private:
iterator start;
iterator finish;
iterator endofstorage;
};
}
今天就到这里吧，润了家人们
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
36
0- 0
已为社区贡献1条内容
所有评论(0)