vector使用和模拟
(一)vector的认识
(1)简单了解
vectoe的文档介绍
vector 是一种表示可变大小数组的序列容器，它融合了原生数组的高效访问特性与动态大小调整能力，核心特点如下：
一方面，vector 与数组类似，采用连续存储空间存储元素，这意味着可以通过下标直接访问元素（如 v[i]），访问效率与数组相同（O (1) 时间复杂度）；但与数组不同的是，它的大小可以动态改变，且无需用户手动管理内存，由容器自动处理扩容与空间分配。
另一方面，vector 的动态增长依赖于动态分配数组：当插入新元素导致现有空间不足时，它会分配一块更大的新数组，将旧元素拷贝到新数组后释放旧空间。为避免频繁扩容（每次扩容的拷贝操作代价较高），vector 采用 “预留额外空间” 的策略 —— 分配的存储空间通常大于当前实际需要的大小。不同实现中，额外空间的分配策略可能不同，但均遵循 “扩容间隔呈对数增长” 原则，确保尾部插入元素的平均时间复杂度为 O (1)。这也使得 vector 会占用略多的存储空间，以此换取动态管理内存的便利性和高效增长能力。
与其他动态序列容器（如 deque、list、forward_list）相比，vector 的优势在于元素访问效率最高，且尾部插入 / 删除元素的操作相对高效；劣势则是非尾部的插入 / 删除操作效率较低（需移动后续元素）。此外，由于存储空间连续，vector 的迭代器和引用稳定性优于 list 等非连续存储容器，迭代器失效场景更可控。
综上，vector 以少量额外空间为代价，实现了高效的随机访问和尾部操作，是兼顾性能与灵活性的常用容器，适用于需动态调整大小且以尾部操作和元素访问为主的场景。
(2)常用接口
01. 构造
使用：
这里博主为了方便打印查看写了个Print函数
void Print(const vector<int>& v)
{for (auto e : v) {cout << e << " ";}cout << endl;
}void test1()
{//vector()vector<int> v1; //vector（size_type n, const value_type& val = value_type()）vector<int> v2(4, 100); //vector (InputIterator first, InputIterator last)vector<int> v3(v2.begin(), v2.end()); // vector (const vector& x);vector<int> v4(v3); Print(v1);Print(v2);Print(v3);Print(v4);
}//运行结果：100 100 100 100
100 100 100 100
100 100 100 100
02.迭代器
解释：
使用：
void test2()
{vector<int> v2(4, 100);//auto为vector<int>::iteratorfor (auto it = v2.begin(); it != v2.end(); ++it)cout << ' ' << *it;cout << endl;
}//运行结果：100 100 100 10003. 空间增长
小细节：
- capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问 题。
- resize在开空间的同时还会进行初始化，影响size。
使用：
void test3()
{vector<int> v;cout << "size=" << v.size() << ", capacity=" << v.capacity() << endl;v.reserve(10);cout << "reserve(10)后: ";cout << "size=" << v.size() << ", capacity=" << v.capacity() << endl;v.resize(5);cout << "resize(5)后: ";cout << "size=" << v.size() << ", capacity=" << v.capacity() << endl;v.push_back(1);cout << "push_back(1)后: ";cout << "size=" << v.size() << ", capacity=" << v.capacity() << endl;v.resize(8);cout << "resize(8)后: ";cout << "size=" << v.size() << ", capacity=" << v.capacity() << endl;
}//运行结果：
size=0, capacity=0
reserve(10)后: size=0, capacity=10
resize(5)后: size=5, capacity=10
push_back(1)后: size=6, capacity=10
resize(8)后: size=8, capacity=1004. 增删查改
头插和头删未提供——要移动数据，效率慢，但是insert和erase可以做到：
//头插
v.insert(v.begin(), 1);
//头删
v.erase(v.begin());使用：
void test4()
{vector<int> nums; nums.push_back(10);nums.push_back(20);nums.push_back(30);for (int i = 0; i < nums.size(); ++i){cout << nums[i] << " "; }cout << endl;nums.pop_back();cout << "删除尾部元素后： ";for (int i = 0; i < nums.size(); ++i) {cout << nums[i] << " "; }cout << endl;
}//运行结果：
10 20 30
删除尾部元素后： 10 20小拓展：
<algorithm>有一个很方便的一个接口sort
sort
功能：是 C++ 中用于排序的常用算法，它能高效地对容器中的元素进行排序，支持多种排序场景和自定义排序规则。
用法：
要包含头文件 #include <algorithm>
1.升序排序：最基础形式
void test5() {vector<int> v = { 3, 1, 4, 1, 5, 9 };sort(v.begin(), v.end());Print(v); }//运行结果： 1 1 3 4 5 9采用快速排序的优化版本（通常是 introsort 算法，结合了快速排序、堆排序和插入排序），平均时间复杂度为 O(n log n)，性能高效。
2.降序排序：
sort(v.begin(), v.end(), greater<int>());//运行结果： 9 5 4 3 1 1注意事项：
1.迭代器类型限制：
- sort 要求容器支持随机访问迭代器(如 vector、array)，不支持双向迭代器的容器(如 list)，此时需使用容器自带的 sort 成员函数(如 list::sort)。
2.元素可比较性：
- 若使用默认排序，元素类型必须支持 < 运算符(如基本类型 int、string 等)。
- 自定义类型需重载 < 运算符，或在排序时传入自定义比较函数。
3.稳定性：
- sort 是不稳定排序(相等元素的相对位置可能改变)。若需要稳定排序，可使用 <algorithm> 中的stable_sort。
(二)vector的模拟实现
(1)准备工作
在模拟实现 vector 之前，首先需要定义一个专属命名空间。这是因为我们的自定义实现可能会与 C++ 标准库中的 vector 产生命名冲突，而将模拟实现的 vector 封装在独立命名空间中，既能有效避免命名冲突，也能确保代码的独立性和可维护性。同时，这种设计便于我们在测试阶段通过命名空间的切换，直接对比自定义 vector 与标准库 vector 的行为差异，从而验证模拟实现的正确性。需要注意的是，由于 vector 本质是模板类，我们的模拟实现也必须采用模板形式，以支持不同数据类型的存储需求，命名空间的具体名称可根据实际情况自定义.
namespace Yu
{template<class T>class vector{public://模拟的内容private:iterator _start;// 指向数据块的开始iterator _finish;// 指向有效数据的尾iterator _endofStorage;// 指向存储容量的尾};
}(2)模拟vector
01. 构造函数
将三个成员变量都置空
vector():_start(nullptr), _finish(nullptr), _endofStorage(nullptr)
{}后面会有更好的方法，我先简单写一个简易版。
02. 析构函数
将开辟的空间销毁，并重新置空
~vecor()
{if (_start){delete[] _start;_start = _finish = _endofStorage = nullptr;}
}03. 迭代器
Vector的迭代器是一个原生指针，因为有普通成员和const成员所以得有两个迭代器
typedef T* iterator; //普通迭代器，可读写元素
typedef const T* const_iterator; //常量迭代器，仅可读元素iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator cbegin() const
{return _start;
}const_iterator cend() const
{return _finish;
}04. size和capacity
由左图可知得：
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endofStorage - _start;
}05. reserve
void reserve(size_t n)
{if (n > capacity()){size_t sz = size();//开辟所需要的新的空间T* tmp = new T[n];//拷贝数据到新空间if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}//更新指针_start = tmp;_finish = _start + sz;_endofStorage = _start + n;}
}测试结果：
06. push_back
void push_back(const T& x)
{//扩容判断if (_finish == _endofStorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}//元素插入*_finish = x;//指针后移++_finish;
}测试结果：
07. operator[]
因为有普通成员和const成员所以得有两个
T& operator[](size_t pos)
{assert(pos < size());//返回指定位置元素的引用return _start[pos];
}const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}测试结果：
08. 拷贝
vector(const vector<T>& v)
{_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}_finish = _start + v.size();_endofStorage = _start + v.capacity();
}测试结果：
可能有人会想为什么要用for来拷贝不可以直接一个memcpy吗？
我们得注意当T为自定义类型 是，如：
Yu::vector<string> v1;v1.push_back("11111111"); v1.push_back("22222222"); v1.push_back("33333333"); v1.push_back("44444444");拷贝string的类型时，如果用memcpy会有一个隐藏的浅拷贝
使用memcpy可能导致浅拷贝问题，主要原因在于：
自定义类型（特别是包含指针成员的类，如std::string）通常由两部分组成：
- 栈上的指针（如std::string内部管理的字符数组指针）
- 指针指向的堆内存（如实际存储的字符串数据）
memcpy执行的是二进制层面的内存拷贝，仅会复制栈上的指针值，而不会复制指针指向的堆内存。这将导致以下问题：
- 两个对象的指针成员指向同一块堆内存（浅拷贝）
- 析构时对同一块内存进行多次释放（double free），导致程序崩溃
- 若其中一个对象修改数据，会影响另一个对象（破坏拷贝独立性）
故：vector是深拷贝，但vector空间上存在的对象是string数组或其他自定义数组时，memcpy会导致它出现浅拷贝，从而出错。
解决方法如下：
使用上述for循环时，对于自定义类型T（如需要深拷贝的string类），会调用string的赋值重载运算符来实现string对象的深拷贝。
09. insert
iterator insert(iterator pos, const T& x)
{//验证插入位置的合法性assert(pos >= _start && pos <= _finish);//检查容量，若满则扩容并更新posif (_finish == _endofStorage){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;
}一些小细节：
但先了解一下什么是迭代器失效：
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器， 程序可能会崩溃)。
1.size_t len = pos - _start;与pos = _start + len;的作用
这两行代码是解决扩容导致内部迭代器失效的关键，解决问题的逻辑：
- 记录偏移量：len = pos - _start 计算插入位置pos相对于容器起始地址_start的偏移量（非绝对地址）。
- 重定位迭代器：当扩容发生时(旧内存被释放，_start指向新内存)，通过pos = _start + len 重新计算pos在新内存中的位置。
为什么能避免失效？
- 绝对地址会随内存释放而失效，但偏移量是相对位置，不受内存块移动影响。
- 即使pos原本指向特殊地址，偏移量计算仍能准确定位。
小知识点：
假若pos为0会有很多坑，但这样pos不可能为0，是一段空间的地址，有效空间的地址不可能为0，那0会时地址吗？从内存地址的本质来说，0 确实可以作为地址值存在(即nullptr对应的地址)，但这是操作系统预留的 “无效地址”，不会分配给用户程序的正常内存空间。因此，pos作为指向容器有效范围的迭代器，其底层指针绝不可能是 0，也就不存在 “pos为 0” 的隐患。
2.返回值pos的作用：
解决外部迭代器失效，防止下面的代码：
auto it = vec.begin() + 1; vec.insert(it, 200); *it += 10;外部代码可能保存插入前的迭代器，若插入触发扩容：旧内存被释放，外部保存的it会指向无效地址(失效)。此时若继续使用it（如*it += 10），会访问已释放内存，导致未定义行为(如崩溃)。*it += 10;这个为高危行为，不要多用。记住insert以后就不要使用这种形参迭代器了，因为他可能失效，所以增加返回值就是为了防止这个。正确写法：
auto it = vec.begin() + 1; // 插入后，it可能失效，改用返回值 auto new_it = vec.insert(it, 200); *new_it += 10; // 安全：new_it指向新内存中的正确位置insert返回新的pos(扩容后已重定位的迭代器)的意义在于：
提供一个有效的迭代器，替代失效的旧迭代器。总结
- 内部防失效：通过偏移量len记录相对位置，确保扩容后pos在新内存中正确定位，保证insert函数内部逻辑正常。
- 外部防失效：返回更新后的pos，提醒用户放弃使用可能失效的旧迭代器，改用新的有效迭代器。
小复用：
简化了尾插
void push_back(const T& x) {insert(end(), x); }
测试结果：
10. erase
iterator erase(Iterator pos)
{//验证删除位置的合法性assert(pos >= _start && pos < _finish);//从pos的下一个元素开始，依次向前移动覆盖iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}//更新容器状态并返回--_finish;return pos;
}小细节：
若没有返回值，用库里面的，且这样调用：
auto it = v.begin() ; v.erase(it);在vs下会强制检查，直接报错，从 C++ 标准角度看是迭代器失效是明确定义的行为
C++ 标准明确规定：对vector执行erase(pos)后，被删除元素的迭代器pos及其之后的所有迭代器都会失效。此时对失效迭代器进行解引用（*it）或递增（++it）操作，属于未定义行为。未定义行为的意思是：标准不规定程序的执行结果，编译器可以自由处理（崩溃、输出错误结果、甚至 "看似正常运行" 都有可能）。
但是在linux会正常，所以不同平台底层不用用，有些程序体现会不一样，那难道linux就很好了吗？不是的。他们俩的区别：
- VS：对迭代器有效性做了严格的额外检查（属于编译器的扩展保护机制），一旦检测到使用失效迭代器，会直接报错或崩溃，提前暴露问题。
- Linux：默认不做强制检查，失效的迭代器可能恰好指向一块未被回收的内存，导致程序 "看似能运行"。
但这只是巧合，本质上仍是错误代码。你若写一个删除偶数的代码
auto it = v.begin(); while (it != v.end()) {if (*it % 2 == 0){v.erase(it);}++it; }然后测试用例为
1. 1 2 2 3 4 5
2. 1 2 2 3 4 5 6
1得到的结果为1 2 3 5；2得到的结果是1 2 3 5 6，解释如下图：
即1是因为两个2连着但是it++直接跳过了一个2；2是因为1的结果再加上删除的本质是移动数据覆盖要删除的数据，故finish迁移，之后it和finish永远不会相等。
这时候在把代码改成
auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}else{++it;}}发现在linux中这两个测试案例都可以成功了，那这个代码可以吗？
在 Linux 下能 "通过测试"，完全是依赖vector的内存布局实现（元素连续存储、删除后未立即回收内存），但：
- 不符合 C++ 标准：erase(it)后it已失效，即使不执行++it，后续循环中it != v.end()的判断也可能因it失效而出错。
- 移植性极差：换用其他编译器（如 VS）或vector实现（如调试模式下的内存检查），会立即暴露问题（崩溃或逻辑错误）。
- 隐藏风险：若vector在删除元素后触发扩容（内存重分配），失效的it会指向旧内存块，此时任何操作都会导致严重错误。
最正确的方法就是上面给的加返回值。
总结
判断一段代码是否正确，不能依赖 "在某个平台能运行"，而应看是否符合语言标准。vector删除元素时，必须通过erase的返回值更新迭代器，这是唯一能保证跨平台一致性和程序正确性的做法。其他 "看似可行" 的写法，本质上都是依赖未定义行为的侥幸，隐藏着难以排查的风险。
11. pop_back、
复用erase
void pop_back()
{iterator it = end(); --it;erase(it);
}12. resize
这个在vector中还是常用的，因为数组常常会初始化
若n < 当前size：保留前n个元素，截断后面的元素(不改变容量）
若n >= 当前size：扩容到至少能容纳n个元素，并用value填充新增的位置(从原size到n-1）
void resize(size_t n, const T& value = T())
{//n<size()if (n < size()){_finish = _start + n;}//n>=size()else{reserve(n);while (_finish != _start + n){*_finish = value;++_finish;}}
}小细节：
const T& value = T()参数为什么是这样的：
参数设计的核心目的
const T& value = T() 是 C++ 中默认参数的典型用法
- 允许用户自定义填充值(如resize(5, 10)用 10 填充）
- 若用户不指定，则使用T的默认值(由T()生成）
T()会生成T类型的默认值：
- 对自定义类型：调用其默认构造函数(无参构造)
- 对内置类型：生成零值(int()是 0，double()是 0.0).但是模板对内置类型有了升级，出现了默认构造。
const T&作用:
vector<T>& operator= (vector<T> v) {swap(v);return *this; }
- 引用传递避免参数拷贝，提高效率(尤其对大型自定义类型）
- const确保不会意外修改传入的默认值
13. operato=
用现代法会很方便，所以我们先写一个swap
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}然后就可以写operator=
vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}14. 构造函数拓展
//一
vector(size_t n, const T& value = T())
{resize(n, value);
}//二
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++ first;}
}vector()
{}小细节：
一.要初始化在resize也可以用C++1的补丁，在private初始化
private:iterator _start = nullptr;// 指向数据块的开始iterator _finish = nullptr;// 指向有效数据的尾iterator _endofStorage = nullptr;// 指向存储容量的尾二.类模板里面还可以套函数模板。
这时候有两个测试案例：
1.vector <int> v(10, 1); 2.vector <string> v1(10, "11111");很明显我们想让1调用一但是1却调用了二，而且还会出现报错
为什么会匹配构造二？
因为模板参数推导时，int被错误地推导为 “InputIterator” 类型，且匹配优先级更高：1.模板参数推导逻辑：
构造二是函数模板，编译器会尝试推导InputIterator的类型。当传入10(int 类型)和1(int 类型)时，编译器会认为 “两个参数都是同一类型（int）”，满足InputIterator first, InputIterator last的参数类型要求（两个参数类型相同），因此推导InputIterator = int。
2.重载匹配优先级：
C++ 重载匹配时，遵循 “精确匹配优先于需要隐式转换的匹配”：构造一的第一个参数是size_t，而传入的10是int，需要进行 “int→size_t” 的隐式转换(非精确匹配)。构造二被推导为InputIterator = int，两个参数都是int，无需转换(精确匹配)。因此编译器会优先选择构造二。
为什么会报错？
构造二的逻辑是 “通过迭代器遍历插入元素”，核心操作是*first（解引用迭代器）和++first(递增迭代器)。但当InputIterator被推导为int时：*first会被解析为 “解引用 int 类型”(把10当指针解引用)，这在语法上是错误的(int 不是指针 / 迭代器，无法解引用),最终编译报错。解决方法：
方法一：显式传入size_t类型参数
vector <int> v(10u, 1);方法二：新增int参数的非模板构造函数
vector(int n, const T& value = T()) {resize(n, value); }
以上就是vector的知识点了，后续的完善工作我们将留待日后进行。希望这些知识能为你带来帮助！如果觉得内容实用，欢迎点赞支持~ 若发现任何问题或有改进建议，也请随时与我交流。感谢你的阅读！