抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

vector的实现

就业学习开发测试手撕STLvector的实现

发布于：2025年6月30日

次浏览

我们先一步一步来实现

1
2
3
4
5
6
7
8
template <typename T>
class myVector {
private: 
    T* elements;  
    size_t capacity;
    size_t current_size;    
};

  1. template <typename T>

这句话其实可以这么理解：我要定义一个“模板”，T 是一个占位符类型，在使用这个模板时才会指定具体的类型。

  • 所以T可以理解为表示变量类型的变量

也就是比如说当你使用这个类的时候

1
2
myVector<int> v1;     // 这里 T 是 int
myVector<double> v2;  // 这里 T 是 double

这里的T就是你传进来的类型

  • typename也就可以理解为类型参数，也可以用class代替
  1. T* elements;
  • 这个实际上是一个指针，指向elements这个数组，里面元素的类型为T*，可以是int*、double*等等
  1. size_t capacity;
  • size_t的”容量“很大，是和平台相关的，所以他很适合用来表示数组的长度，所以等等
  • capacity表示的是当前数组分配了多少容量，也就是elements能存放多少个元素，比如说你当前插入了4个元素，但是为了提高效率，他可能分配了容量为8的数组
  1. size_t current_size;
  • current_size表示当前插入的元素的个数
1
2
3
4
5
public:
    myVector() : elements(nullptr), capacity(0), current_size(0) {}
    ~myVector(){
        delete[] elements;
    }

  • myVector() : elements(nullptr), capacity(0), current_size(0) {}

    • 构造函数常用这种写法，变量直接初始化，更加高效

    • elements(nullptr)：把 elements 初始化为空指针，表示当前没有分配任何内存

    • capacity(0)：容量初始化为 0

    • current_size(0)：当前实际存储的元素个数也为 0

  • ~myVector()

    • 自动释放内存，避免内存泄漏

    • elements 是用 new[] 分配的，所以要用 delete[] 来释放它

下面两个是拷贝构造函数和拷贝赋值运算符，这边说明一下两者的调用条件

  • 拷贝构造函数是用一个已经存在的对象去初始化一个新对象（这个新对象还不存在）
  • 拷贝赋值运算是把一个已经存在的对象的值赋给另外一个已经存在的对象

具体可以通过如下的代码来方便理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

class Test {
public:
    Test() { cout << "Default constructor\n"; }

    Test(const Test& other) { cout << "Copy constructor\n"; }

    Test& operator=(const Test& other) {
        cout << "Copy assignment operator\n";
        return *this;
    }
};

int main() {
    Test a;        // Default constructor
    Test b = a;    // ✅ Copy constructor
    Test c;        
    c = a;         // ✅ Copy assignment operator
}

说白了就是

  • Test b = a; 或 Test b(a);调用的是拷贝构造函数
  • Test c; c = a;调用的是拷贝赋值运算符

拷贝构造函数

1
2
3
myVector(const myVector& other) : capacity(other.capacity), current_size(other.current_size){
    elements = new T[capacity];  
    copy(other.elements, other.elements + current_size, elements);
  • 构造函数重载，这部分其实就是拷贝构造函数，它的作用是：当你用一个已存在的对象去创建一个新对象时，按值复制它的内容。
1
2
3
myVector<int> a;
a.push_back(10);
myVector<int> b = a;  // 调用了拷贝构造函数

  • 如果没有这个函数的，编译器会默认生成一个浅拷贝，就是拷贝的是引用，新对象和旧对象共用的是一块内存地址

  • myVector(const myVector& other) : capacity(other.capacity), current_size(other.current_size)

    • 这部分是直接初始化了成员变量，然后{}里面再写了具体的实现
    • const myVector& other可以理解为定义函数的时候的参数，类似于const vector<int>& other
    • myVector& other这边的myVector&实际上就是一个引用，这时候执行myVector<int> b = a; ，other就是a的一个别名

  • elements = new T[capacity];

    • //分配一块新的类型为T，大小为capacity的动态数组内存，类似于int[5]这样的

  • copy(other.elements, other.elements + current_size, elements);

    • 主要是实现值的拷贝
    • 参数分别是源起始地址，源结束地址，目标地址

到拷贝赋值预算符之前，先理解一下引用、地址和指针三者的区别

  • 指针
1
2
3
int x = 42;
int* p = &x;      // p 是一个指针，保存了 x 的地址
std::cout << *p;  // 👉 解引用，取出 p 指向的值（就是 x 的值：42）
  • 地址
1
2
int x = 42;
std::cout << &x << std::endl;  // 👉 打印的是 x 的地址（内存位置）
  • 引用
1
2
3
4
int x = 42;
int& ref = x;     // ref 是 x 的“引用”，它不是地址，也不是副本
ref = 100;
std::cout << x;   // 👉 输出 100，因为 ref 就是 x
  • 引用就是变量的别名，两个名字指向同一个值

拷贝赋值运算符

1
2
3
4
5
6
7
8
9
10
myVector& operator= (const myVector& other){
    if (this != &other){
        delete[] elements;
        capacity = other.capacity;
        current_size = other.current_size;
        elements = new T[other.capacity];
        copy(other.elements, other.elements + current_size, elements);
    }
    return *this;
}
  • myVector& operator= (const myVector& other)，写b = a的时候，等价于b.operator=(a);
    • 这边的myVector&是返回类型，结合最后return的*this以支持链式赋值a = b = c，等价于a = (b = c)
    • operator=是重载复制运算符，还有例如operator+等等
    • (const myVector& other)也就是a的别名
  • 实际上就是对赋值运算符（=）进行重载，当你写b = a的时候就是把b的内容复制到a当中
  • 这边的this是一个指针，他指向当前调用这个函数的对象，所以当执行的是b = a的时候，这边的this指向的就是&b，*this就是解引用，得到b这个对象

例如

1
2
myVector<int> a;
a.push_back(10);  // push_back 函数内部，this 指向 a

在这边b.operator=(a);，也就是调用了b的成员函数operator=()，所以这时候的this指向的是b

  • 这边的other就是a的一个引用，也就是a这个对象，而this是一个指针，所以要使用&other
  • 这边的elements、capacity和current_size都是b，复制前要先delete

[]也要重载，也就是重载下标访问运算符

1
2
3
4
5
6
7
8
9
10
T& operator[] (size_t index){
    if (index >= current_size) throw out_of_range("越界访问");
    return elements[index];
}

const T& operator[] (size_t index) const {
    if (index >= current_size) throw out_of_range("越界访问");
    return elements[index];
}

  • 第二种加了const表示为常成员函数，只读不改

例如

1
2
3
4
5
myVector<int> v;
v[0] = 100;   // ✅ 用的第一个版本，可以修改

const myVector<int> cv;
int x = cv[0]; // ✅ 用的第二个版本，只能读，不能改

接下来是扩容函数reserve

1
2
3
4
5
6
7
8
9
void reserve(size_t newCapacity){
    if (newCapacity > capacity){
        T* newElements = new T[newCapacity];
        copy(elements, elements + current_size, newElements);
        delete[] elements;
        elements = newElements;
        capacity = newCapacity;
    }
}

这个功能挺简单的，看都看得懂

然后是push_back的实现

1
2
3
4
5
6
7
void push_back(const T& input){
    if (current_size == capacity){
        capacity ? reserve(2 * capacity) : reserve(1);
    }
    elements[current_size++] = input;
}

  • 当需要添加元素的时候，如果检测到已经满了，就会扩容
    • 如果当前是空的，也就是capacity = 0的时候，就会调用reserve(1)，否则就会两倍扩容

pop_back的实现

1
2
3
 void pop_back(){
    if (current_size) current_size--;
}
  • 这边不需要释放内存，因为push_back里面新值也是覆盖操作的

获取大小的size

1
2
3
size_t size(){
    return current_size;
}

insert的实现

1
2
3
4
5
6
7
8
9
void insert(const size_t index, const T& input){
    if (index > current_size) throw out_of_range("越界访问");
    if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
    for (size_t i = current_size; i > index; i--){
        elements[i] = elements[i - 1];
    }
    elements[index] = input;
    current_size++;
}

考虑三种情况

  • index > current_size，可以=的，相当于push_back，>就是表示越界了
  • 如果要插入的时候刚好满了，要扩容一下
  • 如果没有异常情况就是元素右移后再插入

clear的实现

1
2
3
void clear(){
    current_size = 0;
}

最后的话是迭代器接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T* begin(){
    return elements;
}

T* end(){
    return elements + current_size;
}

const T* begin() const {
    return elements;
}

const T* end() const {
    return elements + current_size;
}

  • begin指向第一个元素的位置

  • end指向最后一个元素的下一个位置

  • 同样需要两种版本，应对const myVector 调用（只读）

这样才能实现如下的for循环遍历

1
2
3
for (int x : v) {
    std::cout << x << " ";
}

等价于

1
2
3
4
for (T* it = v.begin(); it != v.end(); ++it) {
    T x = *it;
    ...
}

当然这个和真正的STL比起来，还是差非常多的

完整版本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>     // for cout, endl
#include <stdexcept>    // for std::out_of_range
#include <cstddef>      // for size_t
#include <algorithm>    // for std::copy

using namespace std;

template <typename T>
class myVector {
private: 
    T* elements;  
    size_t capacity;
    size_t current_size;    

public:
    myVector() : elements(nullptr), capacity(0), current_size(0) {}
    ~myVector(){
        delete[] elements;
    }

    myVector(const myVector& other) : capacity(other.capacity), current_size(other.current_size){
        elements = new T[capacity];
        copy(other.elements, other.elements + current_size, elements);
    }

    myVector& operator= (const myVector& other){
        if (this != &other){
            delete[] elements;
            capacity = other.capacity;
            current_size = other.current_size;
            elements = new T[other.capacity];
            copy(other.elements, other.elements + current_size, elements);
        }
        return *this;
    }

    T& operator[] (size_t index){
        if (index >= current_size) throw out_of_range("越界访问");
        return elements[index];
    }

    const T& operator[] (size_t index) const {
        if (index >= current_size) throw out_of_range("越界访问");
        return elements[index];
    }


    void reserve(size_t newCapacity){
        if (newCapacity > capacity){
            T* newElements = new T[newCapacity];
            copy(elements, elements + current_size, newElements);
            delete[] elements;
            elements = newElements;
            capacity = newCapacity;
        }
    }

    void push_back(const T& input){
        if (current_size == capacity){
            capacity ? reserve(2 * capacity) : reserve(1);
        }
        elements[current_size++] = input;
    }

    void pop_back(){
        if (current_size) current_size--;
    }

    size_t size(){
        return current_size;
    }

    void insert(const size_t index, const T& input){
        if (index > current_size) throw out_of_range("越界访问");
        if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
        for (size_t i = current_size; i > index; i--){
            elements[i] = elements[i - 1];
        }
        elements[index] = input;
        current_size++;
    }

    void clear(){
        current_size = 0;
    }

    T* begin(){
        return elements;
    }

    T* end(){
        return elements + current_size;
    }

    const T* begin() const {
        return elements;
    }

    const T* end() const {
        return elements + current_size;
    }


};

简单测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main() {
    myVector<int> vec;

    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 使用范围 for 遍历（因为你写了 begin()/end()）
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    vec.insert(1, 99);  // 在索引1的位置插入99
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    vec.pop_back();
    cout << "Size: " << vec.size() << endl;

    vec.clear();
    cout << "After clear, size: " << vec.size() << endl;

    return 0;
}

输出为

1
2
3
4
5
10 20 30 
10 99 20 30 
Size: 3
After clear, size: 0

为预期结果

更新于：2025年7月4日

评论

评论区