一、迭代器
定义
vector类型的迭代器就是原生态的指针，对T*进行重命名即可
|
1
2
|
typedef T* iterator;
typedef const T* const_iterator;
|
普通迭代器
|
1
2
3
4
5
6
7
8
|
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
|
const类型迭代器
const类型迭代器可以访问const成员变量
|
1
2
3
4
5
6
7
8
|
const iterator cbegin()const
{
return start;
}
const iterator cend()const
{
return finish;
}
|
二、构造类
构造函数
构造空对象
在初始化列表中对三个成员变量进行初始化
|
1
2
3
4
5
|
vector()
:start(nullptr)
, finish(nullptr)
, endOfStorage(nullptr)
{}
|
n个T类型
开辟空间以后，对finish进行自增，在空间填充元素
|
1
2
3
4
5
6
7
8
9
10
|
vector(size_t n, const T& value = T())
:start(new T[n])
, finish(start)
, endOfStorage(start + n)
{
for (int i = 0; i < n; i++)
{
*finish++ = value;
}
}
|
重载前一个构造函数，将第一个参数设置为int类型
|
1
2
3
4
5
6
7
8
9
10
|
vector(int n, const T& value = T())
:start(new T[n])
, finish(start)
, endOfStorage(start + n)
{
for (int i = 0; i < n; i++)
{
*finish++ = value;
}
}
|
之所以要对这种类型的构造函数进行重载，是因为在调用构造函数时，如果实参传两个整型数字，编译器会默认为int类型数据，进行推演之后与前面的size_t类型不匹配，则会调用下面的区间构造的方法，导致程序报错，如图：
迭代器构造
将构造方法中迭代器的类型写成模板类型，这样便可以接收其它类型的迭代器，如：T类型为char，Iterator迭代器为string类型，便可以从字符串中截取字符，构造vector<char>类型的对象。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
//写成函数模板，可以接受任意类型的迭代器
template<typename Iterator>
vector(Iterator first, Iterator last)
{
size_t n = ZH::distance(first, last);//获取长度
start = new T[n];
finish = start;
endOfStorage = start + n;
while (first != last){
*finish = *first;
first++;
finish++;//完成赋值的同时也移动了finish的位置
}
}
|
将distance方法写到另一个.hpp头文件中
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template<typename Iterator>
//此处的Iterator是模板参数，表示可以传任意类型的迭代器
size_t distance(Iterator first, Iterator last)
{
//获取元素个数，暂时只考虑底层空间连续的情况
int count = 0;
while (first != last)
{
first++;
count++;
}
return count;
}
|
拷贝构造函数
拷贝构造函数的形参必须是const类对象的引用，必须使用const类型的迭代器才能访问，复用迭代器构造的方法定义一个临时变量temp，交换temp与当前对象
|
1
2
3
4
5
6
7
8
9
10
|
//此处拷贝构造函数的形参是const类型
vector(const vector<T>& v)
:start(nullptr)
, finish(nullptr)
, endOfStorage(nullptr)
{
//▲用const类型的迭代器访问const变量
vector<T> temp(v.cbegin(), v.cend());
this->swap(temp);
}
|
赋值运算符重载
形参设置为类类型对象，调用赋值运算符重载函数时，形参会拷贝实参，交换当前对象与形参的值。
|
1
2
3
4
5
|
vector<T>& operator=(const vector<T> v)
{
this->swap(v);
return *this;
}
|
析构函数
释放空间，将三个迭代器赋值为空
|
1
2
3
4
5
6
7
|
~vector()
{
delete[]start;
start = nullptr;
finish = nullptr;
endOfStorage = nullptr;
}
|
三、容量相关操作
size、capacity
|
1
2
3
4
5
6
7
8
|
size_t size()
{
return finish - start;
}
size_t capacity()
{
return endOfStorage - start;
}
|
empty
判断fiinsh与start是否相等即可，相等则为空
|
1
2
3
4
|
size_t empty()
{
return finish == start;
}
|
resize
定义一个变量保存旧的size的值‘判断是减小还是增加size；判断是否需要扩容，需要则调用reserve函数，从旧空间的结束位置开始，给新增加的空间填充元素；最后改变finish的值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void resize(size_t newsize, const T& value = T())
{
size_t oldsize = size();
if (newsize > oldsize){
if (newsize > capacity()){
reserve(newsize);
}
for (size_t i = oldsize; i < newsize; i++)
{
start[i] = value;
}
}
finish = start + newsize;//不用考虑增加或减小
}
|
?reserve
reserve的步骤：申请新空间，拷贝旧空间的元素，释放旧的空间。
|
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
|
void reserve(size_t newcapacity)
{
size_t oldcapacity = capacity();
if (newcapacity > oldcapacity)
{
size_t n = size();//保存size()的值
T* temp = new T[newcapacity];
//start不为空时才进行拷贝旧空间元素和释放的操作
if (start)
{
//memcpy浅拷贝，当vector中存放的对象内部设计资源管理
// 会有内存泄漏和野指针问题
//memcpy(temp, start, sizeof(T) * n);
for (size_t i = 0; i < n; i++)
{
temp[i] = start[i];//调用赋值运算符重载
}
delete[] start;
}
start = temp;
//▲此处不能用satart+size(),因为size方法中有finish-start,而start值已经改变
finish = start + n;
endOfStorage = start + newcapacity;
}
}
|
▲易错点：
- 判断start的值是否为空 ，如果原来的start为空，则不需要再拷贝元素和释放
- 浅拷贝问题
finish更新问题
size()的方法内部finish-start，而此时start已经发生改变，finish还是旧的，所以要提前定义一个临时变量保存size()的值
三、元素访问
[ ]重载
重载成普通类型和const类型，const类型可以访问const成员
|
1
2
3
4
5
6
7
8
9
10
11
|
T& operator[](size_t index)
{
assert(index < size());
return start[index];
}
const T& operator[](size_t index)const
{
assert(index < size());
return start[index];
}
|
front
返回动态数组第一个元素
|
1
2
3
4
5
6
7
8
|
T& front()
{
return start[0];
}
const T& front()const
{
return start[0];
}
|
back
返回最后一个位置前一个元素
|
1
2
3
4
5
6
7
8
|
T& back()
{
return *(finish - 1);
}
const T& back()const
{
return *(finish - 1);
}
|
四、修改类接口
push_back
插入前先判断空间是否已满，空间若满则进行扩容，扩容时，要原来的空间容量为0的情况；将value放置到末尾位置，并将finish向后移动一个单位
|
1
2
3
4
5
6
7
8
9
|
void push_back(const T& value)
{
if (finish == endOfStorage)
{
//因为原来的capacity可能为0,所以要+3
reserve(capacity() * 2 + 3);
}
*finish++ = value;
}
|
pop_back
尾删，先判断对象是否为空，若不为空则将finish位置前移一个单位
|
1
2
3
4
5
6
7
8
|
void pop_back()
{
if (empty())
{
return;
}
finish--;
}
|
insert
任意位置插入，insert的返回值为新插入的第一个元素位置的迭代器；因为插入可能会进行扩容，导致start的值改变，所以先定义一个变量保存pos与start的相对位置；判断是否需要扩容；从插入位置开始，将所有元素向后搬移一个位置；将pos位置的值置为要插入的值；更新finish的值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//第二个参数用const修饰，常量引用
//不用const修饰则为非常量引用
iterator insert(iterator pos, const T& value)
{
int index = pos - start;
assert(pos >= start && pos < finish);
//判断空间是否足够
if (finish == endOfStorage)
{
reserve(capacity() * 2);
}
pos = start + index;
for (auto it = finish; it > pos; it--)
{
*it = *(it - 1);
}
*pos = value;
finish++;
return pos;
}
|
erase
判断下标合法性；从pos位置下一个位置开始，将所有元素向前搬移一个位置；更新finish的值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
iterator erase(iterator pos)
{
assert(pos >= start && pos < finish);
auto it = pos;
while (it < finish - 1)
{
*it = *(it + 1);
it++;
}
finish--;
return pos;
}
|
clear
清空所有元素，令finish=start即可
|
1
2
3
4
|
void clear()
{
finish = start;
}
|
swap
vector内置的swap函数，调用标准库中的swap交换vector的三个成员变量的值
|
1
2
3
4
5
6
|
void swap(vector<T>& v)
{
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(endOfStorage, v.endOfStorage);
}
|
五、成员变量
|
1
2
3
4
|
private:
iterator start;
iterator finish;
iterator endOfStorage;
|
vector内部有三个成员变量，start表示起始位置，finish表示有效元素的末尾位置，endOfStorage表示空间的末尾位置；通过这三个成员变量可以得到size和capacity等值，如图：
|
