vector 接口预览

<code>namespace HL

{ -- -->

template<class T>

class vector

{

//迭代器iterator

typedef T* iterator;

typedef const T* const_iterator;

public:

//默认成员函数

vector();

vector(size_t n, const T& val = T());

vector(int n, const T& val = T());

vector(const vector& v);

template<class InputIterator>

vector(InputIterator first, InputIterator last);

~vector();

vector<T>& operator=(vector v);

//Iterator

iterator& begin();

iterator& end();

const_iterator begin() const;

const_iterator& end() const;

//Capacity

size_t size() const;

size_t capacity() const;

bool empty() const;

void reserve(size_t n);

void resize(size_t n, const T& val = T());

//Modifiers

void push_back(const T& val);

void pop_back();

void insert(iterator pos, const T& val);

template<class InputIterator>

void insert(iterator pos, InputIterator first, InputIterator last);

iterator erase(iterator pos);

void swap(vector<T>& v);

//Element access:

T& operator[](size_t i);

const T& operator[](size_t i) const;

private:

iterator start;

iterator finish;

iterator end_of_storage;

};

};

vector模拟实现

vector成员变量

​ vector成员变量，和顺序表的成员变量有所不同，不再是指针、size和capacity了，而是迭代器 start、finish和end_of_storage。

start指向起始位置、finish指向最后一个数据的下一个位置（表示数据的末尾）、end_of_storage指向这一块空间的最后。

默认成员函数

构造函数

1、无参构造

​ 无参构造，就是默认构造函数，将成员变量都初始化成nullptr。

<code>vector()

:start(nullptr)

,finish(nullptr)

,end_of_storage(nullptr)

{ -- -->}

2、构造并初始化成n个val值

​ 理论上，我们只需要写一个函数vector(size_t n, const T& val = T());即可，但是如果两个参数都是int类型，（即vector v(5,1);）编译器在编译时，认为T已经实例化成了int，对于两个int类型，编译器就会选择更为匹配的模版

template vector(InputIterator first, InputIterator last);

所以这里写一个vector(int n, const T& val = T()); 让上面这种情况匹配这个函数。

vector(size_t n, const T& val = T())

{

start = new T[n];

for (size_t i = 0; i < n; i++)

{

start[i] = val;

}

end_of_storage = finish = start + n;

}

vector(int n, const T& val = T())

{

start = new T[n];

for (int i = 0; i < n; i++)

{

start[i] = val;

}

end_of_storage = finish = start + n;

}

3、使用一段迭代器区间进行初始化

​ 使用迭代器区间进行初始化，这里不一定是vector的迭代器，所以写成模板。

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

size_t sz = last - first;

start = new T[sz];

finish = start;

while (first != last)

{

*finish = *first;

++finish;

++first;

}

end_of_storage = start + sz;

}

4、拷贝构造

​ 这里要注意，需要深拷贝，而不是浅拷贝。

vector(const vector& v)

{

size_t sz = v.size();

size_t cp = v.capacity();

start = new T[sz];

for (int i = 0; i < sz; i++)

{

start[i] = v[i];

}

finish = start + sz;

end_of_storage = start + cp;

}

析构函数

​ 析构函数比较简单，释放动态开辟的空间即可。

~vector()

{

if (start)

delete[] start;

start = finish = end_of_storage = nullptr;

}

赋值运算符重载

​ 赋值运算符重载，这个编译器自动生成的是浅拷贝，我们需要写一个深拷贝的。

这里有多种写法，首先就是传统写法，我们自己释放、开辟空间再拷贝数据

vector<T>& operator=(const vector& v)

{

if (start)

delete[] start;

size_t sz = v.size();

start = new T[sz];

for (int i = 0; i < sz; i++)

{

start[i] = v[i];

}

finish = end_of_storage = start + sz;

}

​ 还有现代写法，我们这里传参不使用引用，而使用传值传参；这样生成的形参对象再与我们的this(对象)进行交换；这样形参出了作用域就自动调用析构函数，不用我们去处理了。（这个需要先实现交换函数）

vector<T>& operator=(vector v)

{

swap(v);

return *this;

}

​ 注意事项： 在赋值的过程中没有使用memcpy函数，因为这个函数只是将数值拷贝过去(浅拷贝)；

如果我们vector 示例化是vector 这样的自定义类型，使用浅拷贝就可能会出现问题；所以这里采用一个一个进行赋值操作，这样就会去调用自定义类型的赋值运算符重载；而不只是简单的浅拷贝了。

iterator 迭代器

​ vector 的迭代器这里实现的是原生指针；迭代器相关函数：begin()、end()这些都比较简单就不过多描述了。

//迭代器iterator

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;

}

Capacity

​ capacity容量相关的函数，主要在于调整空间大小和设置内容。

size、capacity、empty

size_t size() const

{

return finish - start;

}

size_t capacity() const

{

end_of_storage - start;

}

bool empty() const

{

return start == finish;

}

reserve

​ reserve，调整空间大小；即扩容。

void reserve(size_t n)

{

if (n > capacity())

{

iterator tmp = T[n];

size_t sz = size();

for (int i = 0; i < sz; i++)

{

tmp[i] = start[i];

}

if (start)

delete[] start;

start = tmp;

finish = start + sz;

end_of_storage = start + n;

}

}

resize()

void resize(size_t n, const T& val = T())

{

reserve(n);

if (n < size())

{

finish = start + n;

}

else {

for (int i = size(); i < n; i++)

{

start[i] = val;

}

finish = start + n;

}

}

Modifiers

​ modifiers 增删查改、vector头插头删效率很低，就不提供头插头删接口了。

push_back、pop_back

​ 尾差、尾删，直接在vector最后插入删除数据。

void push_back(const T& val)

{

if (capacity() == size())

{

size_t n = (capacity() == 0) ? 4 : 2 * capacity();

reserve(n);

}

*finish = val;

++finish;

}

void pop_back()

{

assert(start != finish);

--finish;

}

insert

insert函数，在某个位置插入n(可以是1)个数据。或者插入一段迭代器区间的数据。

iterator insert(iterator pos, const T& val)

{

// 空间不够先进行增容

if (finish == end_of_storage)

{

size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;

reserve(newCapacity);

// 如果发生了增容，需要重置pos

pos = _start + size();

}

//挪动数据

iterator p = finish;

while (p != pos)

{

*p = *(p - 1);

--p;

}

*pos = val;

finish += 1;

return pos;

}

template<class InputIterator>

void insert(iterator pos, InputIterator first, InputIterator last)

{

//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了

size_t sz = last - first;

size_t n = pos - start;

reserve(sz + size());

pos = start + n;

//挪数据

iterator p = finish - 1;

while (p >= pos)

{

*(p + sz) = *p;

--p;

}

//插入数据

for (size_t i = 0; i < sz; i++)

{

pos[i] = first[i];

}

finish += sz;

}

​ 这里，扩容之后还用一个迭代器失效问题，需要重新给pos赋值。

erase

​ erase就是删除某个位置的数据，直接将后面数据往前移动即可

iterator erase(iterator pos)

{

size_t sz = finish - pos;

for (int i = 0; i < sz; i++)

{

pos[i] = pos[i + 1];

}

finish -= 1;

return pos;

}

clear、swap

void swap(vector<T>& v)

{

std::swap(start, v.start);

std::swap(finish, v.finish);

std::swap(end_of_storage, v.end_of_storage);

}

void clear()

{

finish = start;

}

Element access

operator[ ]

​ 下标访问，直接返回start[i]即可。

T& operator[](size_t i)

{

return start[i];

}

const T& operator[](size_t i) const

{

return start[i];

}

代码总览

#pragma once

#include<iostream>

#include<assert.h>

namespace HL

{

template<class T>

class vector

{

//迭代器iterator

typedef T* iterator;

typedef const T* const_iterator;

public:

//默认成员函数

vector()

:start(nullptr)

,finish(nullptr)

,end_of_storage(nullptr)

{ }

vector(size_t n, const T& val = T())

{

start = new T[n];

for (size_t i = 0; i < n; i++)

{

start[i] = val;

}

end_of_storage = finish = start + n;

}

vector(int n, const T& val = T())

{

start = new T[n];

for (int i = 0; i < n; i++)

{

start[i] = val;

}

end_of_storage = finish = start + n;

}

vector(const vector& v)

{

size_t sz = v.size();

size_t cp = v.capacity();

start = new T[sz];

for (int i = 0; i < sz; i++)

{

start[i] = v[i];

}

finish = start + sz;

end_of_storage = start + cp;

}

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

size_t sz = last - first;

start = new T[sz];

finish = start;

while (first != last)

{

*finish = *first;

++finish;

++first;

}

end_of_storage = start + sz;

}

~vector()

{

if (start)

delete[] start;

start = finish = end_of_storage = nullptr;

}

/*vector<T>& operator=(vector v)

{

swap(v);

return *this;

}*/

vector<T>& operator=(const vector& v)

{

if (start)

delete[] start;

size_t sz = v.size();

start = new T[sz];

for (int i = 0; i < sz; i++)

{

start[i] = v[i];

}

finish = end_of_storage = start + sz;

}

//Iterator

iterator& begin()

{

return start;

}

iterator& end()

{

return finish;

}

const_iterator begin() const

{

return start;

}

const_iterator& end() const

{

return finish;

}

//Capacity

size_t size() const

{

return finish - start;

}

size_t capacity() const

{

end_of_storage - start;

}

bool empty() const

{

return start == finish;

}

void reserve(size_t n)

{

if (n > capacity())

{

iterator tmp = T[n];

size_t sz = size();

for (int i = 0; i < sz; i++)

{

tmp[i] = start[i];

}

if (start)

delete[] start;

start = tmp;

finish = start + sz;

end_of_storage = start + n;

}

}

void resize(size_t n, const T& val = T())

{

reserve(n);

if (n < size())

{

finish = start + n;

}

else {

for (int i = size(); i < n; i++)

{

start[i] = val;

}

finish = start + n;

}

}

//Modifiers

void push_back(const T& val)

{

if (capacity() == size())

{

size_t n = (capacity() == 0) ? 4 : 2 * capacity();

reserve(n);

}

*finish = val;

++finish;

}

void pop_back()

{

assert(start != finish);

--finish;

}

iterator insert(iterator pos, const T& val)

{

// 空间不够先进行增容

if (finish == end_of_storage)

{

size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;

reserve(newCapacity);

// 如果发生了增容，需要重置pos

pos = _start + size();

}

//挪动数据

iterator p = finish;

while (p != pos)

{

*p = *(p - 1);

--p;

}

*pos = val;

finish += 1;

return pos;

}

template<class InputIterator>

void insert(iterator pos, InputIterator first, InputIterator last)

{

//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了

size_t sz = last - first;

size_t n = pos - start;

reserve(sz + size());

pos = start + n;

//挪数据

iterator p = finish - 1;

while (p >= pos)

{

*(p + sz) = *p;

--p;

}

//插入数据

for (size_t i = 0; i < sz; i++)

{

pos[i] = first[i];

}

finish += sz;

}

iterator erase(iterator pos)

{

size_t sz = finish - pos;

for (int i = 0; i < sz; i++)

{

pos[i] = pos[i + 1];

}

finish -= 1;

return pos;

}

void swap(vector<T>& v)

{

std::swap(start, v.start);

std::swap(finish, v.finish);

std::swap(end_of_storage, v.end_of_storage);

}

void clear()

{

finish = start;

}

//Element access:

T& operator[](size_t i)

{

return start[i];

}

const T& operator[](size_t i) const

{

return start[i];

}

private:

iterator start;

iterator finish;

iterator end_of_storage;

};

};

到这里，vector模拟实现就结束了，希望你能有所收获

感谢各位大佬支持并指出问题

​ 如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！