C++效率掌握之STL库：vector底层剖析
C++效率掌握之STL库：vector底层剖析
了解完 vector 函数的主要用法，很有必要对 vector 进行深层次的剖析，进一步了解其运作原理，深化理解的同时帮助我们在找 Bug 时提升效率
在学习本专题前，请详细学习有关 vector 的使用
1.学习vector底层的必要性
vector底层通过动态数组实现，学习其内存分配策略，能让我们明白如何避免不必要的内存分配和拷贝操作，迭代器失效问题、扩容策略等
2.vector类对象基本函数实现
namespace bit
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_end_of_storage = _start + capacity();
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage;
}
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}我们这里先了解迭代器的本质也是指针类型，后续会针对迭代器进行详细的本质剖析
传送门：C++效率掌握之STL库：list底层剖析及迭代器万字详解（暂未开放版）
此图选自《STL源码剖析》这本书，有时间建议去读一读这本书，会对STL库有更详细且清晰的认识，所以 _start 是头指针，_finish 是有效字节的尾指针，_end_of_storage 是容量的尾指针，实现基本的构造、析构、拷贝，注意都是 iterator 类型，为了方便配合迭代器使用
3.vector类对象的遍历
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;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}operator= 通过值传递 v，会调用 vector 的拷贝构造函数创建一个临时对象，然后将当前对象和这个临时对象进行交换，最后返回当前对象的引用
🔥值得注意的是： 这种实现方式具有异常安全性，如果拷贝构造函数抛出异常，当前对象的状态不会被改变，同时避免了手动管理内存
4.vector类对象的扩容追加
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
//insert(end(), x);
}
void pop_back(const T& x)
{
erase(--end());
}reserve：注意不要写成 _finish = _start + size()，必须写在 _start = tmp ，因为 size() 的计算依赖于 _start ，所以要在 _start 没有被改变前计算
resize：如果 n 小于当前大小，会截断 vector；如果 n 大于当前大小，会将 vector 扩展到 n 个元素，并使用 val 填充新增的元素
🔥值得注意的是： push_back 函数 reserve 时要判断下是因为扩容是 *2 ，避免空间为 0 时扩容 *2 导致出错
5.string类对象的插入、删除
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
void erase()
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}insert：
• 扩容处理： 当容器已满 _finish == _end_of_storage 时，能够自动进行扩容操作，保证有足够的空间插入新元素
• 元素移动逻辑： 通过将插入位置之后的元素依次向后移动一个位置，为新元素腾出空间，实现了在指定位置插入元素的功能
• 返回值： 函数返回指向插入元素的迭代器，方便调用者后续操作
🔥值得注意的是： size_t len = pos - _start 和 pos = _start + len 的目的是通过记录插入位置相对于起始位置的偏移量 len，在扩容后可以正确恢复插入位置
6.vector类对象的其余操作
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return *(_start + pos);
}🔥值得注意的是：
- 常量正确性是
C++编程中的一个重要原则，它确保对象在被声明为const时，其状态不会被意外修改。当一个对象被声明为const时，只能调用该对象的const成员函数。如果没有const版本的[]运算符，就无法通过const对象访问其元素 - 虽然理论上仅提供
const版本的[]运算符是可行的，但在实际编程中这样做会有诸多局限性，const版本的[]运算符返回的是const引用，这意味着通过该运算符获取的元素不能被修改。在很多场景下，我们需要对容器中的元素进行修改操作，如果只有const版本的[]运算符，就无法实现这一功能
7.使用memcpy拷贝问题
int main()
{
bite::vector<bite::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
//insert(end(), x);
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;
}
}memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中- 如果拷贝的是内置类型的元素，
memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
比如 reserve 函数，memcpy 后，新内存的指针和旧内存的指针都指向原来的内存，delete[] _start 之后原来的空间就被释放了，内置类型就没事，自定义类型会出问题----
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
腾讯云开发者
