C++STL——vector的模拟实现（代码+解析）

迭代器

typedef T* iterator：定义了一个可读可写版本的迭代器。

typedef T* iterator; 
1

typedef const T* const_iterator：定义了一个可读不可写版本的迭代器。

typedef const T* const_iterator;
1

iterator begin()：返回可读可写迭代器的开始位置。

iterator begin()
{
    return _start;
}
1
2
3
4

iterator end()：返回可读可写迭代器的结束位置。

iterator end()
{
    return _finish;
}
1
2
3
4

const_iterator begin() const：返回可读不可写迭代器的开始位置。

const_iterator begin() const
{
    return _start;
}
1
2
3
4

const_iterator end() const：返回可读不可写迭代器的结束位置。

const_iterator end() const
{
    return _finish;
}
1
2
3
4

构造函数

vector()：默认构造函数，初始化_start、_finish和_endOfStorage为nullptr。

   vector() 
       		: _start(nullptr)
           	, _finish(nullptr)
           	, _endOfStorage(nullptr)
        {}
1
2
3
4
5

vector(int n, const T& value = T())：构造函数重载，创建一个大小为n的vector，并初始化为value。

 vector(int n, const T& value = T()) 
     		: _start(nullptr)
         	, _finish(nullptr)
         	, _endOfStorage(nullptr)
        {
            resize(n, value);
        }
1
2
3
4
5
6
7

template vector(Inputiterator first, Inputiterator last)：构造函数重载，根据给定迭代器范围创建vector。

 template 
        vector(Inputiterator first, Inputiterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
1
2
3
4
5
6
7
8
9

operator=运算符重载：实现了赋值运算符重载，用来进行vector之间的拷贝。

 vector& operator=(vector v)
        {
            _start = new T[v.capacity()];
            memcpy(_start, v._start, sizeof(T) * v.size());
            for (size_t i = 0; i < v.size(); i++)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _endOfStorage = _start + v.capacity();
            return *this;
        }
1
2
3
4
5
6
7
8
9
10
11
12

析构函数

~vector()：析构函数，释放_start指针指向的内存空间。

~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}
1
2
3
4
5
6
7
8

元素个数

size() const：返回vector中元素的个数。

 size_t size() const
 {
     return _finish - _start;
 }
1
2
3
4

存储容量

capacity() const：返回vector当前的存储容量。

  size_t capacity() const
  {
  return _endOfStorage - _start;
  }
1
2
3
4

扩大存储容量

reserve(size_t n)：将vector的存储容量扩展到n个元素大小。

void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start)
                {
                    memcpy(tmp, _start, sizeof(T) * sz);
                    delete[] _start;
                }


                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

改变大小

​ resize(size_t n, const T& value = T())：改变vector的大小，若n小于当前大小，则删除多余的元素，若n大于当前大小，则在尾部填充value直到达到n大小。

void resize(size_t n, const T& value = T())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                reserve(n);
                while (_finish != _start + n)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运算符重载

operator[](size_t pos)：重载运算符[]，通过索引pos访问vector中的元素。

T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }
1
2
3
4
5

operator[](size_t pos) const：重载运算符[]，通过索引pos访问vector中的元素（常量版本）。

  const T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
1
2
3
4
5

插入/删除

push_back(const T& x)：在vector的尾部插入元素x，若当前存储空间不足，则进行扩容。

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


            *_finish = x;
            ++_finish;
        }
1
2
3
4
5
6
7
8
9
10
11
12

pop_back()：删除vector的尾部元素。

 void pop_back()
        {
            if (size() == 0)
            {
                return;
            }
            erase(end() - 1);
        }
1
2
3
4
5
6
7
8

swap(vector& v)：交换当前vector和v的内容。

 void swap(vector& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }
1
2
3
4
5
6

insert(iterator pos, const T& x)：在pos位置之前插入元素x。

iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start && pos <= _finish);
            if (_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;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• erase(iterator pos)：删除指定位置的元素。

	 iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos + 1;
            while (it != _finish)
            {
                *(it - 1) = *it;
                ++it;
            }
            --_finish;
            return --pos;
        }
1
2
3
4
5
6
7
8
9
10
11
12

完整代码

#pragma once
#include 
#include 
#include 
#include 
using namespace std;
namespace bit
{
    template 
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        // 迭代器可读可写版本：开始+结束
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        // 迭代器可读不可写版本：开始+结束
        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }
        // 构造函数
        vector() : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {
        }


        vector(int n, const T& value = T()) : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {
            resize(n, value);
        }


        template 
        vector(Inputiterator first, Inputiterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }


        vector& operator=(vector v)
        {
            _start = new T[v.capacity()];
            memcpy(_start, v._start, sizeof(T) * v.size());
            for (size_t i = 0; i < v.size(); i++)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _endOfStorage = _start + v.capacity();
            return *this;
        }


        // 析构函数
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endOfStorage = nullptr;
            }
        }
        // 大小
        size_t size() const
        {
            return _finish - _start;
        }
        // 容量
        size_t capacity() const
        {
            return _endOfStorage - _start;
        }
        // 扩容
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start)
                {
                    memcpy(tmp, _start, sizeof(T) * sz);
                    delete[] _start;
                }


                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }
        // 改变大小
        void resize(size_t n, const T& value = T())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                reserve(n);
                while (_finish != _start + n)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
        }
        // []运算符重载
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }
        // []运算符重载
        const T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
        // 尾部插入
        void push_back(const T& x)
        {
            if (_finish == _endOfStorage)
            {
                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapacity);
            }


            *_finish = x;
            ++_finish;
        }
        // 尾部删除
        void pop_back()
        {
            if (size() == 0)
            {
                return;
            }
            erase(end() - 1);
        }
        // 交换
        void swap(vector& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }
        // 插入
        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start && pos <= _finish);
            if (_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;
        }
        // 删除
        iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos + 1;
            while (it != _finish)
            {
                *(it - 1) = *it;
                ++it;
            }
            --_finish;
            return --pos;
        }


    private:
        iterator _start = nullptr;        // 指向数据块的开始
        iterator _finish = nullptr;       // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾部
    };
    
}
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