目录
前言：vector的简单介绍
vector是STL中特别常用的容器，它能够给我们提供类似于C语言的数组的用法，[ ]是它最常用的遍历方式
它具有多个构造函数
?
在后面我们会一一实现
vector是一个模板类，类中的元素可以是任意数据类型，最常用的就是二维数组vector<vector<int>> 最外层的vector的每个元素都是vector<int>类型，内部的vector的每个元素的数据类型是int，这种结构使用起来就特别像C语言的二维数组
vector的其它成员函数，与string中的类似，就不一一赘述了。
文章目录参考：https://cplusplus.com
?一、Member variables
vector的成员变量与string不一样，它的成员变量都是迭代器，因为vector的空间是连续的，所以它的迭代器是原生指针。
?
它的基本构造是这样的，也就是说它有三个成员变量，_start ,_finish, _end_of_storage
我们再看看stl源码是怎样写的
?
与我们的猜想一致?
二、Iterators
迭代器，我们前面说过，它就是原生指针，那么就比较简单了，它的迭代器的写法与string的差不多
typedef T* iterator;
typedef const T* const_iterator;
因为vector是模板类，所以它的迭代器就是T*的指针
iterator begin()
{
return _start;
}
const_iterator begin()const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end()const
{
return _finish;
}
这些都是最基本的内容
三、Capacity
这里面一共实现了四个成员函数
1、size
size就是_finish减去_start就是vector的size
const size_t size()const
{
return _finish - _start;
}
2、capacity
capacity是_end_of_storage 减去_start
const size_t capacity()const
{
return _end_of_storage - _start;
}
3、reserve
resize与string的类似，都是先开辟空间，拷贝数据，释放旧空间，调整_start,_finish,_end_of_storage
不过这里有两个要点需要注意，这里是vector它的成员变量是指针，我们开辟空间之后只会把_start的值更改为新空间的起始地址，但是_finish和_end_of_storage需要我们手动的修改
而如何求出_finish在新空间的位置呢？
很简单，我们只需要记录_finish和_start之间的偏移量就可以了，开辟新空间后偏移量加上_start就是_finish的位置，而end_of_storage的位置也就好办了，因为我们开辟空间开辟的是n个元素的空间，偏移量就是n,end_of_storage就是_start加上n
另外一个注意点就是拷贝数据，对于像string这样的类来说拷贝数据十分的简单，因为它的元素的类型是固定的就是char，我们直接strcpy就能够拷贝，但是vector的数据类型是不确定的，如果直接使用strcpy或者是memcpy很容易造成浅拷贝，如果是vector<vector<int>>这样的类型呢？
因此我们不能这样做，我们需要手动赋值，而手动赋值就需要我们实现T这个vector的变量类型的赋值=操作符重载(如果不是内置类型)
//扩容，为了兼容T是自定义类型，为了实现深拷贝，不使用memcpy
void reserve(size_t n)
{
if(n > capacity())
{
size_t len = _finish - _start;
T* tmp = new T[n];
if(_start)
{
//拷贝数据，为了实现深拷贝，不使用memcpy
for(size_t i = 0; i < len; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + len;
_end_of_storage = _start + n;
}
}
4、resize
resize与reserve类似，在reserve的基础上加入了初始化，缩容等
resize分为三种情况：
1、n > capacity? 扩容+初始化
2、n > size 初始化
3、n < size 缩容
缩容十分的简单，我们直接将_finish减小就可以了
剩下的就没有什么要点了
//三种情况，比capacity()大，在size()和capacity之间,比size()小
void resize(size_t n, const T& val = T())
{
if(n > capacity())
{
reserve(n);
}
//初始化
if(n > size())
{
while(_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
四、Modifiers
1、push_back
尾插，与我们前面所学过的数据结构和string的大体相差不大
检查容量，插入元素，size++
//使用cosnt &为了能够传临时对象
void push_back(const T& x)
{
if(_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
2、pop_back()
_finish直接向前挪动一位就可以了
void pop_back()
{
assert(size() > 0);
_finish--;
}
3、insert
insert要注意的问题就比较多了，它会出现迭代器失效的问题，
它的大体框架与string的insert没有什么差别
不过vector的insert要传入的是插入位置的iterator，与string的不同，string传入的是下标
因为C++并没有对标realloc的操作符，导致我们只能new一块新空间然后将数据拷贝，但是这就会导致pos位置失效，因为pos指向的是原空间，但是我们是先扩容再插入，所以我们就需要手动修正pos位置，修正的过程与前面的reserve类似，先记录偏移量，然后与空间起始位置相加
//返回值是iterator 返回的是最近一次插入的元素位置
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if(_finish == _end_of_storage)
{
//修正pos的位置
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;//是地址，怎末写都无所谓
while(end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
4、erase
erase会不会发生迭代器失效呢？
答案是不确定的：因为STL只是一个规范，他没有要求具体的实现细节，如果会出现迭代器失效，那么可能它的底层实现了缩容，如果没有失效可能没有缩容。
eraser实现与string类似都是将需要删除的数据位置，那后面的数据覆盖，这里面就不用担心浅拷贝的问题，因为只要T实现了深拷贝，我们直接调用它的=操作符重载就可以了
//返回值同理,删除元素的下一个位置
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while(begin < _finish)
{
*begin = *(begin - 1);
begin++;
}
return pos;
}
5、swap
这里实现的swap与std里面的swap功能相同，不过效率不同，std里面的swap使用了拷贝构造
同时这里面的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);
}
六、Element access
这里就十分的简单了
1、[ ]操作符重载
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
2、front
T& front()
{
assert(size() > 0);
return *_start;
}
3、back
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
七、Member functions
终于来到了最后
1、构造函数
(1)无参构造
无参构造直接将所有的成员变量置为nullptr
//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
(2)迭代器区
迭代器区间构造就需要我们再定义一套模板参数，因为vector可以拿别的容器的迭代器区间来构造
//构造函数，用其它容器的迭代器来构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
while(first != last)
{
push_back(*first);
first++;
}
}
(3)拷贝构造
我们直接使用现代写法，直接与形参交换数据
//拷贝构造，现代写法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
(4)用n个元素构造
这里面比较复杂，我们需要重载多个这种函数来实现，因为如果直接只有一种参数是size_t，那么传入两个int类型的参数时就会被前面的迭代器区间的构造函数调用，造成非法的间接寻址的错误，因为前面的构造函数的参数比size_t这个函数的参数更加吻合，为了应对这种情况，所以使用了多个重载
这是库中的实现也是多个构造函数重载
vector(int n, const T& value)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(int i = 0; i < n; i++)
{
push_back(value);
}
}
vector(long n, const T& value)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(long i = 0; i < n; i++)
{
push_back(value);
}
}
vector(size_t n, const T& value = T())
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(size_t i = 0; i < n; i++)
{
push_back(value);
}
}
?
2、析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
3、=操作符重载
//赋值=重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
八、完整代码
#pragma once
#include <iostream>
#include <cassert>
#include<string>
using namespace std;
namespace ww
{
template<class T>
class vector
{
typedef T* iterator;
typedef const T* const_iterator;
public:
//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
const size_t size()const
{
return _finish - _start;
}
const size_t capacity()const
{
return _end_of_storage - _start;
}
iterator begin()
{
return _start;
}
const_iterator begin()const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end()const
{
return _finish;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
//扩容，为了兼容T是自定义类型，为了实现深拷贝，不使用memcpy
void reserve(size_t n)
{
if(n > capacity())
{
size_t len = _finish - _start;
T* tmp = new T[n];
if(_start)
{
//拷贝数据，为了实现深拷贝，不使用memcpy
for(size_t i = 0; i < len; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + len;
_end_of_storage = _start + n;
}
}
//使用cosnt &为了能够传临时对象
void push_back(const T& x)
{
if(_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
_finish--;
}
//构造函数，用其它容器的迭代器来构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
while(first != last)
{
push_back(*first);
first++;
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//拷贝构造，现代写法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//赋值=重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
vector(int n, const T& value)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(int i = 0; i < n; i++)
{
push_back(value);
}
}
vector(long n, const T& value)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(long i = 0; i < n; i++)
{
push_back(value);
}
}
vector(size_t n, const T& value = T())
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
for(size_t i = 0; i < n; i++)
{
push_back(value);
}
}
//三种情况，比capacity()大，在size()和capacity之间,比size()小
void resize(size_t n, const T& val = T())
{
if(n > capacity())
{
reserve(n);
}
//初始化
if(n > size())
{
while(_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
//返回值是iterator 返回的是最近一次插入的元素位置
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if(_finish == _end_of_storage)
{
//修正pos的位置
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
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);
assert(pos < _finish);
iterator begin = pos + 1;
while(begin < _finish)
{
*begin = *(begin - 1);
begin++;
}
return pos;
}
T& front()
{
assert(size() > 0);
return *_start;
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
for(auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for(size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
void test_vector4()
{
string str("Hello World");
vector<char> v(str.begin(), str.end());
for(auto e : v)
{
cout << e;
}
cout << endl;
}
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);//只能使用resize要初始化
for (size_t i = 0; i < vv.size(); i++)
{
vv[i].resize(i + 1, 0);
vv[i].front() = vv[i].back() = 1;
}
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j < vv[i].size(); j++)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
return vv;
}
};
void test_vector5()
{
vector<vector<int>> ans = Solution().generate(8);
for(auto e : ans)
{
for(auto m : e)
{
cout << m << " ";
}
}
cout << endl;
}
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
v1.push_back(7);
for(auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2(v1);
for(auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
vector<string> ans(10, "Hello World");
for(auto e : ans)
{
cout << e << endl;
}
cout << endl;
}
void test_vector8()
{
vector<vector<int>> dp(10, vector<int>(10, 1));
for(auto e : dp)
{
for(auto m : e)
{
cout << m << " ";
}
cout << endl;
}
cout << endl;
}
}总结
以上就是今天要讲的内容，本文仅仅简单实现了vector