网站推广的定义及方法,手机主页网站推荐,特产电商网站建设报价单,网站如何收录一. vector 底层核心#xff1a;三指针控制内存vector 的本质是动态管理连续内存的容器#xff0c;其核心通过三个指针#xff08;迭代器#xff09;控制内存块#xff1a;_start #xff1a;指向内存块的起始位置#xff08;第一个元素的地址#xff09;#xff1b;_…一. vector 底层核心三指针控制内存vector 的本质是动态管理连续内存的容器其核心通过三个指针迭代器控制内存块_start 指向内存块的起始位置第一个元素的地址_finish指向有效元素的末尾最后一个元素的下一位_end_of_storage指向内存块的末尾容量的边界。代码语言javascriptAI代码解释namespace Lotso { templateclass T class vector { public //typedef T* iterator; using iterator T*; using const_iterator const T*; private: iterator _start nullptr;//数据起始位置 iterator _finish nullptr;//有效数据 iterator _end_of_storage nullptr;//空间 }; }通过这三个指针可直接计算有效元素个数size_finish - _start容量capacity_end_of_storage - _start代码语言javascriptAI代码解释public size_t capacity() const { return _end_of_storage - _start; } size_t size() const { return _finish - _start; }二. 迭代器设计连续内存的 “天然优势”vector的迭代器是对原生指针的封装支持随机访问等操作是很好用的迭代器类型定义代码语言javascriptAI代码解释public: //typedef T* iterator; using iterator T*; using const_iterator const T*; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }--我们这里迭代器的使用可以测试一下实现的打印函数我就直接放上去了之前讲过test.c代码语言javascriptAI代码解释namespace Lotso { void Print(const vectorint v) { for (auto e : v) { cout e ; } cout endl; for (size_t i 0; i v.size(); i) { //v[0]; cout v[i] ; } cout endl; } void test_vector1() { Lotso::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(5); v.push_back(5); v.push_back(5); v.push_back(5); v.push_back(5); v[0]; Print(v); for (auto e : v) { cout e ; } cout endl; } } int main() { Lotso::test_vector1(); return 0; }三. 核心接口实现从构造到析构的内存管理3.1 构造与析构vector的基础框架--我们这里主要介绍一下无参构造其它的就不多讲了代码语言javascriptAI代码解释public: vector() //:_start(nullptr) //,_finish(nullptr) //,_end_of_storage(nullptr) //可以直接在底下声明时给缺省值 { } ~vector() { if (_start) { delete[] _start; _start _finish _end_of_storage nullptr; } }3.2 容量管理reserve 与 resize 的区别3.2.1 reserve仅扩容不初始化元素reserve(n) 保证容量至少为 n仅当 ncapacity 时才分配新内存不改变 size。代码语言javascriptAI代码解释public: void reserve(size_t n) { if (n capacity()) { //先记录一下不然后面start会变 size_t sz size(); T* tmp new T[n]; /*if (_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; }*///string,vector这种深拷贝的会出错 if (_start) { for (size_t i 0; i sz; i) { //tmp[i] _start[i];//swap更好用 std::swap(tmp[i], _start[i]); } delete[] _start; } _start tmp; _finish _start sz; _end_of_storage _start n; } }核心reserve 只管理内存不创建或销毁元素适合提前扩容以优化性能。3.2.2 resize 改变size可能初始化或销毁元素resize(nval) 会将 size 调整为 n 多余元素销毁不足则用 val 填充。代码语言javascriptAI代码解释void resize(size_t n, T val T()) { if (n size()) { _finish _start n; } else { reserve(n); while (_finish _start n) { *_finish val; _finish; } } }3.3 元素操作增删查改的实现细节3.3.1 尾插(push_back)与尾删(pop_back)尾插和尾删是 vector 最高效的操作O (1)只需检查容量并构造元素销毁元素代码语言javascriptAI代码解释void push_back(const T x) { if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); } *_finish x; _finish; } void pop_back() { assert(!empty()); --_finish; }3.3.2 插入insert中间插入的性能代价在指定位置插入元素需挪动后续元素时间复杂度 O (n)代码语言javascriptAI代码解释public: iterator insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); // 扩容可能导致 pos 失效需记录偏移量 if (_finish _end_of_storage) { //提前记录一下 size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; } 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; }为什么从后往前挪若从前往后挪会覆盖未移动的元素3.3.3 访问元素operator []提供数组式访问不做越界检查高效代码语言javascriptAI代码解释T operator[](size_t i) { assert(i size()); return _start[i]; } const T operator[](size_t i) const { assert(i size()); return _start[i]; }四. 避坑指南vector 使用的 3 个核心陷阱4.1 迭代器失效扩容与删除的 “隐形炸弹”扩容导致失效reservepush_backinsert 等可能触发扩容旧内存被释放迭代器变为野指针。解决扩容后重新获取迭代器如 insert 中通过偏移量修正 pos。删除导致失效erase 或pop_back 后指向被删元素的迭代器失效后续元素迭代器可能偏移。解决erase返回下一个有效迭代器见下方示例代码语言javascriptAI代码解释// 正确删除偶数元素 auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) { it v.erase(it); // 用返回值更新迭代器 } else { it; } }--下面这些也可以参考一下代码语言javascriptAI代码解释void test_vector2() { Lotso::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //v.push_back(5); Print(v); v.insert(v.begin(), 0); Print(v); auto it v.begin() 3; // insert以后it是否失效 // it失效了也就意味着insert以后it失效了it就不能使用了 v.insert(it, 30); Print(v); } void test_vector3() { Lotso::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.erase(v.begin()); Print(v); auto it v.begin() 2; // it是否失效呢失效不能访问访问结果未定义 v.erase(it); Print(v); } void test_vector4() { Lotso::vectorint v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); // Print(v); for (auto e : v) { cout e ; } cout endl; // 删除所有的偶数 /*auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) { v.erase(it); } it; }*/ auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) { it v.erase(it); } else { it; } } for (auto e : v) { cout e ; } cout endl; } }4.2 浅拷贝风险自定义类型必须深拷贝若 vector 存储的是含指针的自定义类型如 string直接用 memcpy 拷贝会导致多个对象共享内存析构时双重释放。本文实现的 reserve 和拷贝构造均用移动 / 拷贝构造函数迁移元素避免了这一问题。