【C++入门】STL容器--vector底层数据结构剖析
?
目录
size、capacity、empty、operator[ ]；
前言
? ? ? ? ?vector在C++中非常重要的容器，在刷题中也经常使用，它是一个动态的数组，提供了快速的随机访问和在尾部的插入和删除操作。vector的底层实现也是非常优秀的数据结构，值得我们去学习鉴赏，使用STL我们需要做到三个境界：能用，明理，能扩展；所以了解它的基本底层原理也是非常有必要的。
?1. vector的使用
? ? ??vector的构造
?常见的构造方式：
vector<int> v1;
vector<int> v2(10,1); // 使用10个1进行初始化
vector<int> v3(v2);?迭代器区间构造：
vector<int> v = { 1,2,3,4,5 };
vector<int> vv(v.begin(),v.end());?除此之外我们还可以传变量：
vector<int> v(n + m, 0);//开一个数组大小为n+m初始化为0?这样写也是可以的，在一些刷题常见可能会遇到。
?vector迭代器
?
?vector和string迭代器的使用方法相同
vector<int> v{1,2,3,4,5,6};
vector<int>::iterator it = v.begin();
while(it!=vv.end())
{
cout<<*it;
it++;
}?vector空间相关的接口
?这些接口的功能与使用和string的很相似，不做过多的介绍。
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size
?vector 功能型接口
?这里着重介绍一下find和swap
?find
?find属于算法库里的内容在头文件?algorithm?中
?函数返回时返回的也是迭代器类型
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}?使用样例：
vector<int> v{1,2,3,4,5,6,7,8,9};
auto pos = find(v.begin(),v.end(),5);
cout<<*pos;?swap
?细心的朋友可能会发现，vector、string中都有一个swap接口，它和算法库里的swap还有些不一样：
vector：
?算法库：
算法库里的swap要传两个参数，vector里只用传一个参数；并且它们的交换方式也有所不同；
?算法库中的交换就是简单的数值交换
template <class T>
void swap ( T& a, T& b )
{
T c(a); a=b; b=c;
}?vector和string中的swap通过交换指针指向来实现交换的；
在调用vector的swap时，其实还存在一个this指针作为参数，交换指针指向的内容。
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};
v1.swap(v2);?insert
vector<int> v{1,2,3,4,5,6,7,8,9};
auto pos = find(v.begin(),v.end(),5);
v.insert(pos,10); // 在5前边插入10?erase
vector<int> v{1,2,3,4,5,6,7,8,9,10};
auto pos = find(v.begin(),v.end(),10);
vv.erase(pos);
//删除一个区间
v.erase(v.begin()+2,v.end()-2);2. vector内部数据结构剖析
vector的底层本质就是一个动态顺序表，然而它的设计方式又与我们之前的顺序表又有所不同：
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
// 给缺省值，避免每个构造函数都要写初始化列表
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
}?它的底层是通过三个指针来控制的
?这样的设计也是为了迭代器的适配，有了这样的适配，在STL容器中，迭代器的使用都基本相同，也是为了去除不同容器在使用迭代器时的差异。
?模拟封装一个vector的类，首先我们要先实现它的构造函数和析构函数：
vector() // 注意：这里虽然什么都没有但是不能删，因为我们写的有构造函数
// 编译器不会生产默认构造，如果删除无参构造时就会报错
{}
~vector()
{
if (_start)
{
delete[] _start;
//析构时要将所有的指针变量置为NULL
_start = _finish = _endofstorage = nullptr;
}
}?构造函数用于初始化
reserve
?刚开始就要遇到一个大难题，迭代器失效的问题；
????????reserve的主要功能就是开空间，而开空间时就可能会遇到空间转移的情况（开辟一块新的空间，将原空间的内容拷贝过去）；空间一旦转移，就会导致原先的指针失效——迭代器失效。所以我们要先记录一下原空间的一些数据。
第二个问题，浅拷贝的问题：
? ? ? ? 将数据拷贝到新的空间看似很简单，但是它存在浅拷贝的问题，在只用内置类型时不会出问题，一旦遇到涉及动态内存管理的自定义类型就直接会挂；
?memcpy将所有的数据都拷贝过去，这会导致更深一层的浅拷贝问题，两个_str指向同一块空间，原空间交换后就会被销毁，字符串也会被销毁，new的新空间中的_str就会是一个野指针。
所以看似简单的拷贝使用memcpy直接拷贝不行；
? ? ? ? 可以使用一个更为直接的方式，就是直接赋值（利用自定义类型的operator=）.
void reserve(size_t n)
{
if (n > capacity())
{
//考虑到交换后地址空间转移，需要提前记录旧空间的数据大小
size_t old = size();
T* tmp = new T[n];
if (_start)
{
// 自定义类型会造成迭代器失效的问题例如：string
// memcpy(tmp, _start, n * sizeof(T)); // 这个属于浅拷贝
for (int i = 0; i < old; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endofstorage = _start + n;
}
}?push_back和pop_back
?有了reserve，尾插和尾删就简单多了：
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}size、capacity、empty、operator[ ]；
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
bool empty() const
{
return (size()==0);
}
T& operator[] (size_t pos)
{
assert(size() > pos);
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}?insert和erase
?????????插入和删除操作，依然存在着迭代器失效的问题，删除和插入操作可能面临缩容和扩容问题，这都会导致操作后的pos与原先的pos数据不同导致迭代器失效（有些编译器会进行检查，认为erase之后的迭代器失效）；insert 和 erase 之后形参pos都可能会失效，insert和erase之后的迭代器不要使用
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
为了避免操作后的pos数据丢失，所以返回类型最好是迭代器类型（也就是指针，连续存储的空间可以被视为是一个天然的迭代器）；
resize
resize的主要作用是改变容器中元素的数量(size为有效元素个数，capacity为容量）
?三种情况：
- n > size ，n<capacity? ?
resize的参数值大于当前容器中size的大小，小于capacity，会在容器末尾插入新的元素，不进行扩容（插入的元素可指定，也可以默认使用默认构造）
- n > capacity?
?resize的参数值大于当前容器的capacity大小，进行扩容，并插入新的元素
- n < size
resize的参数值小于当前容器的size大小，那么会删除多余的元素
?它又可以分为两种情况，有删除操作和无删除操作；
// T()为匿名构造
void resize(size_t n, T val = T())
{
if (n > size())
{
// 扩容时会判断传值是否大于它的容量
reserve(n);
// 插入新的数据
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}不管自定义类型还是内置类型匿名构造会调用它的默认构造函数（在C++中认为内置类型也有默认构造函数）
int i; // 默认初始化为0
double d; // 默认初始化为0.0
char c; // 默认初始化为'\0'
bool b; // 默认初始化为false
int* ptr; // 默认初始化为nullptr
swap
swap可以直接使用std里的swap进行封装：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}?拷贝构造和赋值重载
?在学习时，我们使用的都是传统的写法，每次都是开空间然后将数据拷贝过去，这样其实很烦，于是小编上网查阅了一些资料，看到别人的代码，偷学来了一种新的写法，简单便捷；
在这里分享给大家：
?我们可以利用我们实现的一些接口来帮我们做，简单便捷；
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;
}?最为精妙的莫过于operator=；之前我们写赋值运算符重载要写一大堆，这里只需要两行就可以完成；
什么原理？
?如上图，v1有数据，v2没有数据，现在将v1的值赋值给v2，调用赋值运算符重载（operator=）；
注意这里是传值调用，传值调用会调用拷贝构造，创建一个临时变量（也就是图上的v）;
调用swap函数，交换两个指针指向的内容；
函数执行结束，临时对象v就会连同v的内容一同被销毁；
这样的设计堪称精妙，值得我们学习和鉴赏；
构造函数补充
构造函数我们只实现了一个，构造函数还有迭代器区间构造，指定数值个数构造
?迭代器区间构造
在此之前我们要先来把我们实现的vector迭代器接口实现，方便遍历：
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}?????????这里我们可以使用模板，传进来的迭代器的类型我们未知，可能是int类型、string类型、double类型...
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}?利用push_back接口进行数据插入；
指定数值个数构造
vector(size_t n, const T& val = T())
{
resize(n, val);
}?我们直接调用resize来帮我做；但是这样存在缺陷，我们用10个0进行初始化就会报错；为什么？
????????模板调用时，一定是选择最合适的，两个参数都是int类型，他会调用迭代器的那个函数模板（模板的两个参数类型相同），不会走vector(size_t n, const T& value = T())这个构造方法，到了*first，就会报错，一个int类型如何解引用？
?解决办法也很简单在实现一个构造函数给int类型：
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}?
总结
????????在本文中，我们深入探讨了STL容器中的vector，以及它的底层数据结构。vector的底层设计也是比较好的，值得每位初学者借鉴学习；以上便是本文全部内容，希望对你有所帮助，最后感谢阅读！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- ajax都有哪些优点和缺点
- 前端发送请求之参数处理---multipart/form-data与application/x-www-form-urlencoded
- 洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes 刷题笔记
- 前端学习笔记
- 一个时间胶囊，送给一位朋友
- vue项目本地开发完成后部署到服务器后报404是什么原因
- 【记录】Python3｜Python出现循环引用模块怎么办？（又称循环依赖）
- Dobbo---分布式系统通信方式
- MSF学习
- 使用css实现旋转木马HTML