当前位置： 首页 > news >正文

万字C++STL——vector模拟实现

news 2025/3/28 6:15:30

模拟实现总览

namespace wlw
{//命名空间为了让其隔离//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector();                                           //构造函数vector(size_t n, const T& val);                     //构造函数template<class InputIterator>                      vector(InputIterator first, InputIterator last);    //构造函数vector(const vector<T>& v);                         //拷贝构造函数vector<T>& operator=(const vector<T>& v);           //赋值运算符重载函数~vector();                                          //析构函数//迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//容量和大小相关函数size_t size()const;size_t capacity()const;void reserve(size_t n);void resize(size_t n, const T& val = T());bool empty()const;最好➕const//修改容器内容相关函数void push_back(const T& x);void pop_back();void insert(iterator pos, const T& x);iterator erase(iterator pos);void swap(vector<T>& v);//访问容器相关函数T& operator[](size_t i);const T& operator[](size_t i)const;private:iterator _start;        //指向容器的头iterator _finish;       //指向有效数据的尾iterator _endofstorage; //指向容器的尾};
}

模拟vector变量

注：_start 和_finish是左闭右开，_start、_finish 和 _endofstorage 均为 vector 的内部成员指针，它们分别指向 vector 内存块的起始位置、已使用元素的末尾位置以及内存块的末尾位置。

默认函数

构造函数

1.无参构造

都设为空就行，也可以在定义的时候给

vector()//无参默认构造:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}

2.传组值构造函数

 该构造函数借助 std::initializer_list 来初始化 vector 对象。std::initializer_list 属于 C++ 的一个标准库类型，可让你以初始化列表的形式传递一组值。借助这个构造函数，你能像下面这样初始化 vector 对象：

vector(initializer_list<T> il):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(il.size());for (auto& e : il){push_back(e);}
}

常见问题与陷阱

1 类型不匹配问题

若initializer_list元素类型与T不兼容，会触发编译错误：

vector<int> v = {'a', 'b'};  // 错误，char无法隐式转换为int

2 空列表处理

当传入空列表时，构造空vector：

vector<int> v = {};  // 合法，size为0

3 性能优化点

  • 提前计算容量：il.size()是O(1)操作，可直接用于reserve。
  • 避免冗余检查：push_back内部会检查容量是否足够，但由于reserve已保证，实际不会触发扩容。

4. 测试用例与输出验证

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v = {1, 2, 3, 4, 5};for (int num : v) {cout << num << " ";}cout << endl;return 0;
}

输出结果：

1 2 3 4 5

参数：initializer_list<T> il 为传递进来的初始化列表，其中 T 是 vector 所存储元素的类型。

函数调用：reserve(il.size()); 此语句会预先分配足够的内存，以容纳初始化列表中的所有元素。这样做的目的是避免在后续插入元素时频繁进行内存重新分配，从而提升性能。

3.迭代器构造函数 

这个构造函数允许你使用一个迭代器区间 [first, last) 来初始化 vector 对象。迭代器是一种用于遍历容器元素的对象，通过提供一个迭代器区间，你可以从另一个容器或者其他可迭代对象中提取元素，并将这些元素插入到新创建的 vector 中。

template<class InputIterator>//一个模板构造函数
//类模板的成员函数，也可以是一个函数模板  可以是其他容器的迭代器区间
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);first++;}
}

InputIterator 是一个模板类型参数，它代表输入迭代器类型。输入迭代器是一种最基本的迭代器类型，它支持递增操作（++）、解引用操作（*）和相等比较操作（== 和 !=）。 

  • 使用 while 循环遍历迭代器区间 [first, last)。在每次循环中，通过解引用操作 *first 获取当前迭代器指向的元素，并调用 push_back 函数将该元素添加到 vector 的末尾。

  • 然后，使用 first++ 将迭代器移动到下一个元素的位置。

  • 当 first 等于 last 时，说明已经遍历完整个迭代器区间，循环结束。

#include <iostream>
#include <vector>// 假设这是你的自定义 vector 类
template <typename T>
class vector {
private:T* _start;T* _finish;T* _endofstorage;// 其他成员函数和私有方法void push_back(const T& value) {// 实现 push_back 逻辑}
public:template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);first++;}}
};int main() {int arr[] = {1, 2, 3, 4, 5};vector<int> vec(arr, arr + 5);// 这里可以添加代码来验证 vec 中的元素return 0;
}

4.多个n值构造函数

此构造函数的作用是创建一个 vector 对象，并且让该对象包含 n 个值为 val 的元素。

可以有两种实现逻辑

vector(size_t n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); for (size_t i = 0; i < n; i++) {push_back(val);}
}

  • 参数：
    • size_t n：表示要创建的 vector 中元素的数量。
    • const T& val：代表每个元素的初始值，T 是 vector 所存储元素的类型。
  • 成员变量初始化：
    • _start、_finish 和 _endofstorage 是 vector 类的内部成员指针，分别代表 vector 所管理内存的起始位置、已使用元素的末尾位置以及内存的末尾位置。在构造函数开始时，将这些指针初始化为 nullptr。
  • 内存预分配：reserve(n); 这一语句调用 reserve 函数，目的是预先分配足够的内存，使其能够容纳 n 个元素。这样做可以避免在后续插入元素时频繁进行内存重新分配，进而提高性能。
  • 元素插入：
    • 借助 for 循环执行 n 次 push_back 操作。
    • 每次循环都会把值为 val 的元素添加到 vector 的末尾。
#include <iostream>
// 假设这是你的自定义 vector 类
template <typename T>
class vector {
private:T* _start;T* _finish;T* _endofstorage;// 其他成员函数和私有方法void reserve(size_t newCapacity) {// 实现 下文有reserve 逻辑}void push_back(const T& value) {// 实现 下文有push_back 逻辑}
public:vector(size_t n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n); for (size_t i = 0; i < n; i++) {push_back(val);}}
};int main() {vector<int> vec(5, 10); // 创建一个包含 5 个值为 10 的元素的 vector// 后续可添加代码验证 vec 内容return 0;
}

拷贝构造

vector的构造函数涉及深拷贝问题，这里提供两种深拷贝的写法：
写法一：传统写法
拷贝构造的传统写法的思想是我们最容易想到的：先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。

//传统写法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾
}

注意： 将容器当中的数据一个个拷贝过来时不能使用memcpy函数，当vector存储的数据是内置类型或无需进行深拷贝的自定义类型时，使用memcpy函数是没什么问题的，但当vector存储的数据是需要进行深拷贝的自定义类型时，使用memcpy函数的弊端就体现出来了。例如，当vector存储的数据是string类的时候。

 代码中看似是使用普通的“=”将容器当中的数据一个个拷贝过来，实际上是调用了所存元素的赋值运算符重载函数，而string类的赋值运算符重载函数就是深拷贝，所以拷贝结果是这样的：

总结一下： 如果vector当中存储的元素类型是内置类型（int）或浅拷贝的自定义类型（Date），使用memcpy函数进行进行拷贝构造是没问题的，但如果vector当中存储的元素类型是深拷贝的自定义类型（string），则使用memcpy函数将不能达到我们想要的效果。

写法二：现代写法
拷贝构造函数的现代写法也比较简单，使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来即可。


vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同for (auto e : v) //将容器v当中的数据一个个尾插过来{push_back(e);}
}

注意： 在使用范围for对容器v进行遍历的过程中，变量e就是每一个数据的拷贝，然后将e尾插到构造出来的容器当中。就算容器v当中存储的数据是string类，在e拷贝时也会自动调用string的拷贝构造（深拷贝），所以也能够避免出现与使用memcpy时类似的问题。

析构函数

~vector()
{if (_start)//不等于空就进来  避免空指针进入{delete[] _start;_start = _finish = _endofstorage = nullptr;}
}

复制运算符重载

传统写法

vector<T>& operator=(const vector<T>& v)
{if (this != &v) //防止自己给自己赋值{delete[] _start; //释放原来的空间_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾}return *this; //支持连续赋值
}
  1. 自我赋值检查：if (this != &v) 用于检查是否是自我赋值。若为自我赋值，就无需进行任何操作，直接返回 *this。
  2. 释放原有空间：delete[] _start; 释放当前 vector 对象所占用的内存空间。
  3. 分配新空间：_start = new T[v.capacity()]; 分配一块大小和 v 容量相同的新内存空间。
  4. 数据拷贝：借助 for 循环将 v 中的元素逐个拷贝到新分配的内存中。
  5. 更新指针：
    • _finish = _start + v.size(); 更新 _finish 指针，使其指向新分配内存中有效数据的末尾。
    • _endofstorage = _start + v.capacity(); 更新 _endofstorage 指针，使其指向新分配内存的末尾。
  6. 返回引用：return *this; 返回当前对象的引用，以支持连续赋值操作。

现代写法

vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(v); //交换这两个对象return *this; //支持连续赋值
}
  1. 值传递：参数 v 采用值传递的方式，这会触发 vector 的拷贝构造函数，从而创建一个 v 的深拷贝对象。
  2. 交换对象：swap(v); 交换当前对象和 v 的内容。因为 v 是一个局部对象，在函数结束时会自动调用析构函数释放其占用的内存。
  3. 返回引用：return *this; 返回当前对象的引用，以支持连续赋值操作。

注意事项

  • 深拷贝：两种写法都进行了深拷贝，避免了浅拷贝可能引发的内存问题。
  • 禁止使用 memcpy：在传统写法中，不能使用 memcpy 进行数据拷贝，因为 memcpy 是按字节进行拷贝的，对于包含指针或动态分配内存的对象，会导致浅拷贝问题。
  • 传统写法通过手动释放原有内存、分配新内存并逐个拷贝元素来实现深拷贝。
  • 现代写法借助值传递触发拷贝构造函数创建深拷贝对象，然后交换对象内容，代码更加简洁。

迭代器相关函数 

1. 迭代器类型定义

typedef T* iterator;
typedef const T* const_iterator;

  • typedef T* iterator;：定义了一个名为 iterator 的类型别名，它实际上是指向 T 类型的指针。这意味着 iterator 可以像指针一样操作，用于遍历和修改 vector 中的元素。

  • typedef const T* const_iterator;：定义了一个名为 const_iterator 的类型别名，它是指向 const T 类型的指针。使用 const_iterator 只能访问 vector 中的元素，不能修改它们。

2. 普通迭代器的 begin 和 end 方法

iterator begin()
{return _start;
}iterator end()
{return _finish;
}

  • iterator begin()：返回一个指向 vector 中第一个元素的迭代器。在这个实现中，它返回 _start 指针，因为 _start 指向 vector 所管理内存的起始位置。

  • iterator end()：返回一个指向 vector 中最后一个元素之后位置的迭代器。在这个实现中，它返回 _finish 指针，因为 _finish 指向 vector 中已使用元素的末尾位置

3. 常量迭代器的 begin 和 end 方法

const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

  • const_iterator begin() const：这是一个常量成员函数，用于在 const 对象上调用。它返回一个 const_iterator，指向 vector 中第一个元素。同样，它返回 _start 指针。

  • const_iterator end() const：这也是一个常量成员函数，用于在 const 对象上调用。它返回一个 const_iterator，指向 vector 中最后一个元素之后的位置。它返回 _finish 指针。

容量和大小相关函数

 size() 

  • 功能：返回 vector 中当前存储的有效元素个数。

  • 实现：通过 _finish - _start 计算有效元素数量。_start 指向容器内存起始位置，_finish 指向有效元素末尾，两者差值即为已存储元素的个数。

 capacity() 

  • 功能：返回 vector 已分配的内存空间能容纳的元素最大数量（即容量）。

  • 实现：通过 _endofstorage - _start 计算容量。_endofstorage 指向容器内存空间的末尾，与 _start 的差值表示当前分配的内存可容纳的元素总数。

size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endofstorage - _start;
}

扩容 reserve

reserve 函数会检查传入的参数 n 是否大于当前容器的容量 capacity()。

如果 n 更大，就会重新分配一块大小为 n 的新内存空间，并将原有的数据复制到新空间中，最后释放原有的内存空间。

如果 n 小，不变。

	void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (_start)//拷贝旧空间数据给新空间，并释放{memcpy(tmp, _start, sizeof(T) *  size());delete[] _start;}_start = tmp;_finish = _start +  size()_endofstorage = _start + n;}}

看看这样模拟实现，代码有没有问题  答案是有问题。

size_t size() const
{return _finish - _start;
}

你是否发现在_statr 被销毁了，当到最后要求_finish的时候size（）已经改变了。 所以需要提前更新size（）的值。

	void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start)//拷贝旧空间数据给新空间，并释放{memcpy(tmp, _start, sizeof(T) * oldSize);delete[] _start;}_start = tmp;_finish = _start + oldSize;size()中的_start值已经改了 提前记录size()的值_endofstorage = _start + n;}}

注意： 为什么用new 不用malloc

  • new T[n] 会为每个 T 元素调用构造函数。若 T 是自定义类，构造函数会初始化成员变量、申请资源等。

例如，若 T 是一个包含动态内存成员的类，构造函数会负责该成员的初始化，确保对象状态合法。

  • malloc 的缺陷：malloc(sizeof(T) * n) 仅分配字节级内存，不涉及 T 类型的构造函数。若 T 是类，未初始化的对象成员变量处于随机值状态，资源未正确申请，

后续使用必然引发错误（如访问未初始化的指针成员导致程序崩溃）。

扩容resize


 1、当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
 2、当n小于当前的size时，将size缩小到n。

根据resize函数的规则，进入函数我们可以先判断所给n是否小于容器当前的size，若小于，则通过改变_finish的指向，直接将容器的size缩小到n即可，否则先判断该容器是否需要增容，然后再将扩大的数据赋值为val即可。

void resize(size_t n, const T& val = T())
//void resize(size_t n, T val = T()){if (n < size()) //当n小于当前的size时{_finish = _start + n; //将size缩小到n}else //当n大于当前的size时{if (n > capacity()) //判断是否需要增容{reserve(n);}while (_finish < _start + n) //将size扩大到n{*_finish = val;_finish++;}}
}
void resize(size_t n, T val = T())


#include <iostream>
// 假设这是你的自定义 vector 类
template <typename T>
class vector {
private:T* _start;T* _finish;T* _endofstorage;// 其他成员函数和私有方法size_t size() const { return _finish - _start; }size_t capacity() const { return _endofstorage - _start; }void reserve(size_t n) {// 实现 reserve 逻辑}
public:void resize(size_t n, const T& val = T()) {if (n < size()) {_finish = _start + n;}else {if (n > capacity()) {reserve(n);}while (_finish < _start + n) {*_finish = val;_finish++;}}}
};int main() {vector<int> vec;vec.resize(5, 10); // 将容器大小调整为 5，新增元素初始化为 10return 0;
}

判空empty

vector 容器中用于判断是否为空的成员函数

bool empty()
{return _start == _finish;  //左闭右开
}

查询find

在STL容器中没有为每个模板单独写一个find函数，是公用的需要包头文件

#include <algorithm>    // std::find
//实例
#include <iostream>     // std::cout
#include <algorithm>    // std::find
#include <vector>       // std::vectorint main () {// using std::find with array and pointer:int myints[] = { 10, 20, 30, 40 };int * p;p = std::find (myints, myints+4, 30);if (p != myints+4)std::cout << "找到了 " << *p << '\n';elsestd::cout << "找不到\n";// 对vector和迭代器使用std::find：std::vector<int> myvector (myints,myints+4);std::vector<int>::iterator it;it = find (myvector.begin(), myvector.end(), 30);if (it != myvector.end())std::cout << "Element found in myvector: " << *it << '\n';elsestd::cout << "Element not found in myvector\n";return 0;
}

注：像string他是类型不是模板对find函数调用的方式多，需要但单独实现

修改容器内容相关函数

 尾删pop_back

void pop_back(){assert(!empty());//防止结构错乱，防止删多了--_finish;//不用抹除数据}

尾插push_back

第一种写法

先判断是否扩容在，从给_finish赋值

void push_back(const T& x)
{if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

第二种

insert本身就是插入，只是改在尾插罢了

void push_back(const T& x){insert(_finish, x);}

插入 insert

insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。

//在pos位置插入数据
void insert(iterator pos, const T& x)
{if (_finish == _endofstorage) //判断是否需要增容{size_t len = pos - _start; //记录pos与_start之间的间隔size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容pos = _start + len; //通过len找到pos在增容后的容器当中的位置}//将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入iterator end = _finish;while (end >= pos + 1){*end = *(end - 1);end--;}*pos = x; //将数据插入到pos位置_finish++; //数据个数增加一个，_finish后移
}

第一种迭代器失效 野指针

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在值为2的元素的位置插入10//v: 1 10 2 3 4 5v.erase(pos); //删除元素2 ？？？error（迭代器失效）//v: 1 2 3 4 5return 0;
}

在该代码中，我们本意是使用元素2的迭代器在原序列中2的位置插入一个10，然后将2删除，但我们实际上获取的是指向2的指针，当我们在2的位置插入10后，该指针就指向了10，所以我们之后删除的实际上是10，而不是2。 

 解决办法：更新pos的位置就可以解决了

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); v.insert(pos, 10); //v: 1 10 2 3 4 5pos= find(v.begin(), v.end(), 2);//更新pos的位置v.erase(pos);//v: 1 2 3 4 5return 0;
}

 注：STL中的find()函数是共享的，string中单独写了一个是因为string中实现的方法多。

erase

erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可。

//删除pos位置的数据
iterator erase(iterator pos)
{assert(!empty()); //容器为空则断言//将pos位置之后的数据统一向前挪动一位，以覆盖pos位置的数据iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}_finish--; //数据个数减少一个，_finish前移return pos;
}

第二种迭代器失效 逻辑问题

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{v.erase(it);}it++;}return 0;
}

该代码看上去实际上并没有什么错误，但如果你画图仔细分析，你就会发现该代码的问题所在，迭代器访问到了不属于容器的内存空间，导致程序崩溃。 

我们可以接收erase函数的返回值（erase函数返回删除元素的后一个元素的新位置），并且控制代码的逻辑：当元素被删除后继续判断该位置的元素（因为该位置的元素已经更新，需要再次判断）。 

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{it = v.erase(it); //删除后获取下一个元素的迭代器}else{it++; //是奇数则it++}}return 0;
}

迭代器失效解决方法

使用迭代器时，永远记住一句话：每次使用前，对迭代器进行重新赋值。

swap

swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

//交换两个容器的数据
void swap(vector<T>& v)
{//交换容器当中的各个成员变量::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);
}

 访问容器相关函数

operator[ ]

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中的operator[]是不能修改的由const限制。
 


http://www.mrgr.cn/news/95862.html

相关文章：

  • STM32内部时钟输出比较OC（学习笔记）
  • 常用的离散时间傅里叶变换（DTFT）对
  • Langchain中的表格解析:RAG 和表格的爱恨情仇
  • 深入 SVG：矢量图形、滤镜与动态交互开发指南
  • Python进阶编程总结
  • 定长内存池原理及实现
  • 【Linux知识】RPM软件包安装命令行详细说明
  • MoManipVLA：将视觉-语言-动作模型迁移到通用移动操作
  • Rust从入门到精通之精通篇：21.高级内存管理
  • Tasklet_等待队列_工作队列
  • ngx_http_core_location
  • SVN常用命令
  • 团体协作项目总结Git
  • 基于Ebay拍卖网站成交价格的影响因素分析
  • python工厂模式
  • 2025前端面试题（vue、react、uniapp、微信小程序、JS、CSS、其他）
  • 吾爱出品，文件分类助手，高效管理您的 PC 资源库
  • 内核编程十二：打印task_struct中的数据
  • 单片机和微控制器知识汇总——《器件手册--单片机、数字信号处理器和可编程逻辑器件》
  • Mycat安装验证流程整理