目录
vector是STL中特别常用的容器,它能够给我们提供类似于C语言的数组的用法,[ ]是它最常用的遍历方式
它具有多个构造函数
在后面我们会一一实现
vector是一个模板类,类中的元素可以是任意数据类型,最常用的就是二维数组vector
vector的其它成员函数,与string中的类似,就不一一赘述了。
文章目录参考:https://cplusplus.com
vector的成员变量与string不一样,它的成员变量都是迭代器,因为vector的空间是连续的,所以它的迭代器是原生指针。
它的基本构造是这样的,也就是说它有三个成员变量,_start ,_finish, _end_of_storage
我们再看看stl源码是怎样写的
与我们的猜想一致
迭代器,我们前面说过,它就是原生指针,那么就比较简单了,它的迭代器的写法与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;
- }
这些都是最基本的内容
这里面一共实现了四个成员函数
size就是_finish减去_start就是vector的size
- const size_t size()const
- {
- return _finish - _start;
- }
capacity是_end_of_storage 减去_start
- const size_t capacity()const
- {
- return _end_of_storage - _start;
- }
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
因此我们不能这样做,我们需要手动赋值,而手动赋值就需要我们实现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;
- }
- }
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;
- }
- }
尾插,与我们前面所学过的数据结构和string的大体相差不大
检查容量,插入元素,size++
- //使用cosnt &为了能够传临时对象
- void push_back(const T& x)
- {
- if(_finish == _end_of_storage)
- {
- reserve(capacity() == 0 ? 4 : capacity() * 2);
- }
-
- *_finish = x;
- _finish++;
- }
_finish直接向前挪动一位就可以了
- void pop_back()
- {
- assert(size() > 0);
-
- _finish--;
- }
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;
- }
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;
- }
这里实现的swap与std里面的swap功能相同,不过效率不同,std里面的swap使用了拷贝构造
同时这里面的swap是为了拷贝构造和=操作符重载的现代写法打基础
- void swap(vector
& v) - {
- std::swap(_start, v._start);
- std::swap(_finish, v._finish);
- std::swap(_end_of_storage, v._end_of_storage);
- }
这里就十分的简单了
- 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& front()
- {
- assert(size() > 0);
- return *_start;
- }
- T& back()
- {
- assert(size() > 0);
- return *(_finish - 1);
- }
终于来到了最后
无参构造直接将所有的成员变量置为nullptr
- //无参构造
- vector()
- :_start(nullptr)
- ,_finish(nullptr)
- ,_end_of_storage(nullptr)
- {}
迭代器区间构造就需要我们再定义一套模板参数,因为vector可以拿别的容器的迭代器区间来构造
- //构造函数,用其它容器的迭代器来构造
- template<class InputIterator>
- vector(InputIterator first, InputIterator last)
- :_start(nullptr)
- ,_finish(nullptr)
- ,_end_of_storage(nullptr)
- {
- while(first != last)
- {
- push_back(*first);
- first++;
- }
- }
-
我们直接使用现代写法,直接与形参交换数据
- //拷贝构造,现代写法
- vector(const vector
& v) - :_start(nullptr)
- ,_finish(nullptr)
- ,_end_of_storage(nullptr)
- {
- vector
tmp(v.begin(), v.end()) ; - swap(tmp);
- }
-
这里面比较复杂,我们需要重载多个这种函数来实现,因为如果直接只有一种参数是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);
- }
- }
-
- ~vector()
- {
- delete[] _start;
- _start = _finish = _end_of_storage = nullptr;
- }
- //赋值=重载
- vector
& operator=(vector v) - {
- swap(v);
- return *this;
- }
-
- #pragma once
- #include
- #include
- #include
-
- 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
& v) - {
- std::swap(_start, v._start);
- std::swap(_finish, v._finish);
- std::swap(_end_of_storage, v._end_of_storage);
- }
-
- //拷贝构造,现代写法
- vector(const vector
& v) - :_start(nullptr)
- ,_finish(nullptr)
- ,_end_of_storage(nullptr)
- {
- vector
tmp(v.begin(), v.end()) ; - swap(tmp);
- }
-
-
- //赋值=重载
- vector
& operator=(vector 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
int>> generate(int numRows) { - 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
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
ans(10, "Hello World") ; -
- for(auto e : ans)
- {
- cout << e << endl;
- }
- cout << endl;
- }
-
- void test_vector8()
- {
- vector
int>> dp(10, vector<int>(10, 1)); - for(auto e : dp)
- {
- for(auto m : e)
- {
- cout << m << " ";
- }
- cout << endl;
- }
- cout << endl;
- }
-
- }
以上就是今天要讲的内容,本文仅仅简单实现了vector