1.实现一个double类型的vector_vectory

原文：https://zhuanlan.zhihu.com/p/611692224

1.实现一个只支持double类型的vector

先抛下实现整个stl，先实现一个简单可用的vector

• 用double* 类型指定vector的头尾和可用空间的最大值
• 公共接口
  • 构造/析构函数
  • 获取首尾
  • 获取/操作大小
  • 插入/删除数据

记录问题：

• front和back为什么要返回引用

  • 提高代码的效率：在函数返回时，避免了创建副本的开销，因为他直接返回对象本身；后期调用方可以直接调用front和back来修改vector；

• 成员函数声明后跟const的目的

  • 成员函数声明为const：如果一个成员函数不会修改其所操作的对象的状态，可以将其声明为const成员函数。这样做有两个好处：一是可以使代码更加清晰易懂，表明该函数不会对对象的任何成员和函数进行修改；二是可以允许在const对象上调用该函数。
  • 需要注意的是，函数声明后跟const并不意味着该函数的返回值为const。而是表示该函数不会修改其所操作的数据。如果需要声明一个返回值为const的函数，应该将const放在函数返回值类型的前面，例如：const int func() const

• 成员初始化列表(member initialization list)

  • 成员初始化列表的语法是在冒号后面列出成员变量的初始化，每个成员变量的初始化用逗号分隔。成员初始化列表是C++中用于在构造函数中初始化类成员变量的一种方式，可以提高代码的效率和可读性。
  • 使用成员初始化列表的好处在于可以避免使用赋值操作符对成员变量进行赋值，从而提高代码的效率。此外，成员初始化列表还可以用于初始化const成员变量和引用类型成员变量。
  • 需要注意的是，如果类中的成员变量没有使用成员初始化列表初始化，那么它们会被默认初始化。对于内置类型的成员变量，未初始化的值是未定义的，而对于自定义类型的成员变量，则会调用默认构造函数进行初始化。

• delete指向数组头节点的指针，会回收整个数组吗

  • delete操作释放指向数组头节点的指针，会释放整个数组的内存空间。这是因为，在C++中，数组是一个连续的内存块，而数组名实际上是指向数组第一个元素的指针。因此，释放数组的头节点指针就相当于释放了整个数组的内存空间。
  • delete用于释放单个对象的内存空间。如果使用new操作符创建了一个单个对象的动态内存空间，则需要使用delete操作符释放该内存空间。
  • delete[]用于释放数组的内存空间。如果使用new[]操作符创建了一个数组的动态内存空间，则需要使用delete[]操作符释放该内存空间。
  • 在使用new和new[]操作符创建动态内存空间时，需要确保分配的内存空间与释放的内存空间类型匹配，否则可能会导致未定义的行为。
  • 在使用成员变量时，应该避免直接修改或暴露类的内部状态，而应该使用访问器（getter）和修改器（setter）等方法来控制对类状态的访问和修改。这样可以保证类的封装性，避免出现意外的状态修改或错误。

• 析构函数中应避免调用delete关键字

  • 析构函数是在对象被销毁时自动调用的函数，用于进行资源的释放和清理操作。当使用 delete 运算符删除一个对象时，会自动调用该对象的析构函数，释放对象占用的内存和资源
  • 如果析构函数调用 delete 运算符，会导致程序中止或者出现未定义的行为。这是因为在析构函数中调用 delete 运算符会导致对象的重复删除，可能会破坏堆内存的布局和内存的完整性，从而导致程序崩溃或产生未定义的行为。

• const对象（常量对象）不能调用非const成员函数

  • const对象的指针为const classA* this，因此传入非const成员函数时编译器报错（类型不匹配，无法从const 指针转换为非const指针）；但传入const成员函数则类型匹配。
  • 非const对象的指针为classA* this，可以调用const成员函数，因为const修饰符保证了不会修改该对象。
  • 同样，const成员函数不能调用非const成员函数

class vector
{

protected:
    // 用double* 类型表示vector的头尾和可用空间的最大值
    double *start;          // 表示当前空间的头
    double *finish;         // 表示当前使用空间的尾
    double *end_of_storage; // 表示当前可用空间的尾

    // 辅助函数，作用：用于vector空间不够时扩容
    // 可用空间为0时，申请更大的空间，并把元素都复制过去
    void allocate_and_copy()
    {
        // std::cout << "调用allocate_and_copy" << std::endl;

        int len = (capacity() != 0 ? capacity() * 2 : 1); // 以容量的2倍为规则扩容
        double *temp = new double[len];                   // 创建更大的空间,temp指向可用空间的头
        for (int i = 0; i < size(); ++i)
        {
            temp[i] = start[i];
        }
        end_of_storage = temp + len;
        finish = temp + size();

        // delete start; // 回收旧数组的头节点，实际上整个旧数组都被释放了
        delete[] start; // 回收旧数组
        start = temp;
    }

public:
    // 构造函数:这里用成员初始化列表进行初始化
    vector() : start(nullptr), finish(nullptr), end_of_storage(nullptr)
    { // 默认构造
        std::cout << "vector的默认构造" << std::endl;
    }

    // 有参构造:初始化vector的长度为n
    vector(int n)
    {

        std::cout << "vector的有参构造vector(n)" << std::endl;

        start = new double[n]; // 先创建空间
        finish = start;
        end_of_storage = start + n;
        for (int i = 0; i < n; ++i) // 初始值设为0.0
        {
            start[i] = 0.0;
        }
    }

    // 有参构造:初始化vector的长度为n，并将这些位置上的数据全部赋值为value
    vector(int n, const double &value)
    {

        std::cout << "vector的有参构造vector(n,value)" << std::endl;

        start = new double[n]; // 先创建空间
        finish = start + n;    // 因为对数组的数组是从0开始存放的，start+n表示的是使用空间的下一个位置
        end_of_storage = start + n;
        for (int i = 0; i < n; ++i) // 初始值设为0
        {
            start[i] = value;
        }
    }

    // 拷贝构造
    vector(const vector &another)
    {
        std::cout << "vector的拷贝构造函数" << std::endl;

        // 创建一个新空间存放another的数据
        int len = another.size();
        start = new double[len];
        for (int i = 0; i < len; ++i)
        {
            // start[i] = *(another.begin() + i);        //const对象不能调用非const成员函数
            start[i] = another[i];
        }
        finish = start + len;
        end_of_storage = finish;
    }

    // 析构函数
    ~vector()
    {
        std::cout << "vector的析构函数" << std::endl;

        delete[] start;
    }

    // 常用接口
    /**********************首尾******************************/

    // 给出vcetor当前使用空间的起始位置
    double *begin() const
    {
        return start;
    }

    // 给出vector当前使用空间的下一个位置
    double *end() const
    {
        return finish;
    }

    // 逆序遍历时，使用空间的起始位置
    double *rbegin()
    {
        return end() - 1;
    }

    // 逆序遍历时，使用空间的结束位置
    double *rend()
    {
        return begin() - 1;
    }

    /**********************随机访问******************************/

    // vector中第一个数据
    double &front()
    {
        return *begin(); // 尽量避免直接使用和暴露成员变量，保证类的封装性
    }

    // vector中最后一个数据
    double &back()
    {
        return *(end() - 1);
    }

    double &operator[](int n) // 返回引用，便于修改
    {                         // 不考虑n越界的情况
        return *(begin() + n);
    }

    double &operator[](int n) const // 返回引用，便于修改
    {                               // 不考虑n越界的情况
        return *(begin() + n);
    }

    /**********************大小******************************/

    // 此处const的作用：
    // 一、将成员函数声明为const,表明该函数不会对对象进行修改
    // 二、可以允许在const对象上调用该函数
    // vector中当前有多少个数据
    int size() const
    {
        return finish - start;
    }

    // 容量:vector中当前最多能存放多少个数据
    int capacity() const
    {
        return int(end_of_storage - begin());
    }

    int max_size() const
    {
        return end_of_storage - start;
    }

    // vector当前是否为空
    bool empty() const
    {
        return begin() == end();
    }

    /**********************  增删改  ******************************/
    // 在vector的末尾插入一个数据
    void push_back(const double &x)
    {
        // 容器内空间不够，就扩容
        if (finish == end_of_storage)
        { // 如果长度为零，初始空间设为1
            std::cout << "capacity()的值为：" << capacity() << std::endl;
            allocate_and_copy();
        }
        *finish = x;
        //*end() = x;       //ERROR:因为end()是静态成员函数，不能修改对象
        ++finish;
    }

    // 在vector的末尾删除一个数据
    void pop_back()
    {
        --finish; // ERROR:因为end()是静态成员函数，不能修改对象
    }

    // 删除position所指向的数据
    void erase(double *position)
    {
        // 把指针后面的全部前移
        for (double *i = position; (i + 1) != end(); ++i)
        {
            *i = *(i + 1);
        }
        --finish;
    }

    // 删除从first到last这一段数据
    void erase(double *first, double *last)
    {
        int diff = last - first;
        int count = 0;                                   // 计数器
        for (double *i = last; i != end(); ++i, ++count) // 如果last等于end(),就不用移动后面的数据了，直接更新finish就行
        {
            *(first + count) = *(first + diff + count); // 这里等号右边必须是first + diff,刚好是last的下一个位置,计数器从0开始遍历正好
        }
        finish = finish - diff; // 指针向前移动
    }

    // 调整vetor的容量，如果调整后的容量大于调整前，则用数据x填充空余部分；
    // 如果调整后容量小于调整前，则只保留前new_size位数据
    void resize(int new_size, const double &x)
    {
        if (new_size < size())
        {
            erase(begin() + new_size, end());
        }
        else
        {
            std::cout << "capacity()的值为：" << capacity() << std::endl;
            // 考虑需要扩容的情况
            while (new_size > capacity())
            { // 数组是从0开始存储的，所以如果new_size = capacity()的情况刚好能存放

                allocate_and_copy();
                std::cout << "capacity()的值为：" << capacity() << std::endl;
            }
            for (int i = 0; i < new_size - size(); ++i)
            {
                *(finish + i) = x;
            }
            finish += new_size - size();
        }
    }

    // 调整后的容量大于调整前，则用默认数据填充空余部分,其余上同
    void resize(int new_size)
    {
        resize(new_size, 0.0);
    }

    // 清空vector中所有数据
    void clear()
    {
        erase(begin(), end());
    }
};
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254

#include <iostream>
#include "../myStl/My_vector.h"

using std::cout;
using std::endl;

// 遍历数组
// void traverse(vector vec) // 如果不使用引用传递，则函数运行时调用拷贝构造函数
void traverse(const vector &vec)
{
    for (int i = 0; i < vec.size(); ++i)
    {
        std::cout << vec[i] << ' ';
    }
    std::cout << std::endl;
}

int main()
{
    // 对构造函数的测试
    vector vec;         // 默认构造
    vector vec1(6);     // 有参构造，6有容器长度
    vector vec2(10, 1); // 有参构造，数组长度为10，都初始化为1
    vector vec3(vec2);  // 拷贝构造

    for (int i = 0; i < 100; ++i)
    {
        vec.push_back((double)i / 100);
    }
    traverse(vec);

    // 测试成员函数
    cout << *vec.begin() << endl;
    cout << *vec.end() << endl; // 原则上vec.end()不能被访问
    cout << vec.front() << endl;
    cout << vec.back() << endl;
    cout << *vec.rbegin() << endl;
    // cout << *vec.rend() << endl;      //vec.rend()不能被访问
    cout << vec[66] << endl;
    cout << vec.size() << endl;
    cout << vec.capacity() << endl;
    cout << vec.max_size() << endl;
    cout << vec.empty() << endl;

    vec1.push_back(2.0);
    traverse(vec1);
    // 试一下遍历空数组
    vec1.pop_back();
    traverse(vec1);
    vec2.pop_back();
    traverse(vec2);

    vec.erase(vec.begin() + 66); // 参数为指针
    vec2.erase(vec2.begin() + 1, vec2.begin() + 4);

    // resize
    cout << vec.size() << endl;
    vec.resize(400, 1.24);
    traverse(vec);
    vec.resize(10);
    traverse(vec);

    vec.clear();
    traverse(vec);

    return 0;
}
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