vector可以管理任意类型的数组,是一个表示可变大小数组的序列容器。
通过vector文档来看它的使用。
#include
#include
using namespace std;void test_vector1()
{vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);
}int main()
{test_vector1();return 0;
}
要使用vector需要先引头文件。现在插入一些元素后,要遍历v,可以用[],范围for,迭代器。
//[]for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;//迭代器vector::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;//范围forfor (auto e : v){cout << e << " ";}cout << endl;
创建一个数组并遍历可以这样写
void test_vector2()
{vector v1(10, 1);for (auto e : v1){cout << e << " ";}cout << endl;vector v2(v1.begin(), v1.end());//用迭代器范围来遍历数组for (auto e : v2){cout << e << " ";}cout << endl;
}
刚才提到vector可以传任何类型,string类也可以。
string s1("hello world");vector v3(s1.begin(), s1.end());for (auto e : v3){cout << e << " ";}cout << endl;
不过打印的是ANSCII码值罢了。
写一下反向迭代器
//vector::reverse_iterator rit = v.rbegin();auto rit = v.rbegin();//也可以使用autowhile (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;
对于vector,初始化变得很简单
void test_vector4()
{vector v;v.resize(10, 0);//初始化10个元素为0
}
vector的insert和erase和string不一样,它要配合迭代器。且vector的查找元素是用std的find函数。
vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector::iterator pos = find(v.begin(), v.end(), 2);if (pos != v.end()){v.insert(pos, 20);}for (auto e : v){cout << e << " ";}cout << endl;
而想删除不能直接erase
pos = find(v.begin(), v.end(), 2);if (pos != v.end()){v.erase(pos);}for (auto e : v){cout << e << " ";}cout << endl;
因为这时候迭代器失效了。头删就可以直接v.erase(v.begin())。
基本功能。扩容函数需要注意一下,防止程序崩掉,三个变量的赋值要考虑具体的结果。
vector.h
#pragma once
#include
using namespace std;
#includenamespace zyd
{templateclass vector{public:typedef T* iterator;vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}iterator begin(){return _start;}iterator end(){return _finish;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}bool empty(){return _start == _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i = 0; i < v1.size(); ++i){cout << v1[i] << " ";}cout << endl;v1.pop_back();v1.pop_back();v1.pop_back();v1.pop_back();vector::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;}
}
针对const对象的访问,我们写一个func函数放在和test函数同样的位置。
void func(const vector& v){for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;vector::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}}
然后再写上所调用成员函数的const函数,以及const版本的迭代器。
typedef T* iterator;typedef const T* const_iterator;
写一下resize()。如果传的参数n小于size,那就是删数据,如果大于,那么要扩容,还有新的空间要初始化,库里用了缺省参数,T val = T()。T()其实是一个匿名的默认构造,对自定义类型有用,对内置类型也适用,C++做了相关的函数,int a = int();,就会初始化a为0。但是指针不能这样写。
templatevoid f(){T i = T();cout << i << endl;}void test_vector2(){/*int a = int();int b = int(1);cout << a << endl;cout << b << endl;*/f();f();f();}
引入模板后,什么内置类型就可以了。
回到resize函数。
void resize(size_t n, T val = T()){if (n < size()){//删除数据_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}
void test_vector3(){vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);}
扩容后新空间就是0
void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;}
vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);/*cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);*/v1.insert(v1.begin(), 0);func(v1);auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.insert(pos, 30);}func(v1);
一个头插,一个第3个位置插入,结果如下
如果是5个,也就是进行了一次扩容后,就没问题了。有的编译器这里会崩掉。
在insert函数里,我们插入了4个数据,那么就会扩容一次,开新空间,旧空间释放,扩容之后_start _finish _end_of_storage都会变,但是pos还是指向原先的空间,pos就变成了野指针,这时候就变成了迭代器失效。为了解决这个问题,我们需要找到pos的新的相对位置。
void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){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 = val;++_finish;}
如果是插入5个,那么在找pos之前就已经扩容了,pos是按照新空间去找位置,所以就没问题。
都插入完成后,对pos位置++
auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.insert(pos, 30);}func(v1);(*pos)++;func(v1);
会发现什么都没发生。实际上这里越界了。这是因为虽然函数里面改正了pos,但是没传出去,所以外面还是以前的pos。如果函数里面pos没有改,那就没问题。insert目前是传值传参,但不能把pos改成引用传参,会报错。这是因为begin和end函数是传值,不能传给引用,所以insert返回pos就好。也可以不写这个返回,不在外面用pos就行。
erase函数
void erase(iterator pos){assert(pos >= _start && pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;}
void test_vector4(){vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.erase(pos);}for (auto e : v1){cout << e << " ";}cout << endl;}
刚才insert之后pos失效了,erase这里也会报错,pos会失效,最好不要访问,不容易控制,因为行为结果未定义,不同平台不同结果。
erase也可以认为是迭代器失效。如果pos是最后一个数据位置,那么删除后,finish会往前一步,但依然在最后一个元素后面,这时候pos和finish同一位置,实际上这时候pos已经失效了。
改一下erase函数
iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;return pos;}
测试代码
void test_vector5(){vector v1;v1.push_back(10);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(50);for (auto e : v1){cout << e << " ";}cout << endl;vector::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{++it;}}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;}
~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
vector还有别的构造。vector接口参数里的缺省参数通常不用0,而是const T& val = T(),防止类型冲突。但这里是否需要考虑匿名对象的生命周期只在这一行?
先测一下这个问题
class A
{
public:A(){cout << "A()" << endl;}~A(){cout << "~A()" << endl;}
};A a1;A();A a2;return 0;
可以看到确实是这样,a1和a2是在return0那里才都销毁,而A()直接就销毁。但入如果const A& xx = A(),就会使用上这个对象,一直到引用对象xx生命周期结束时才析构。
但不加const就不行,因为像匿名对象这样的临时对象都是有常性的。
继续写初始化构造函数。
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}
测试代码
zyd::vector v1(10, 5);for (auto e : v1){cout << e << " ";}cout << endl;
vector也有排序
v1.insert(v1.begin(), 10);sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;
除此之外,数组也可以。默认为升序。如果想降序,需要用到greater这个模板,它可以用任何类型,以及头文件#include < functional >。
greater g;sort(v1.begin(), v1.end(), g);
也可以
sort(v1.begin(), v1.end(), greater());
vector(const vector& v){reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();}
但是这个程序应对string类对象的拷贝就崩了。
vector v3(10, "1111111");for (auto e : v3){cout << e << " ";}cout << endl;vector v4(v3);for (auto e : v4){cout << e << " ";}cout << endl;
用vector
这里的解决办法就是挨个赋值。自定义类型的赋值会开一样大的空间,然后填充内容。
同样地,扩容也是memcpy,调起调试可以看出memcpy的两个对象是同一个指针。所以这里也要改。
void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}
这样其他类型的也都可以了。
void test_vector8(){class Solution{public:vector> generate(int numRows){vector> vv;vv.resize(numRows, vector());for (size_t i = 0; i < vv.size(); ++i){vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 1] = 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;}};vector> ret = Solution().generate(5);for (size_t i = 0; i < ret.size(); ++i){for (size_t j = 0; j < ret[i].size(); ++j){cout << ret[i][j] << " ";}cout << endl;}cout << endl;}
}
我们的拷贝构造函数是这样
vector(const vector& v){reserve(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();}
程序崩了,是因为浅拷贝问题,赋值浅拷贝。vv是深拷贝,而ret是浅拷贝。
赋值=没有重载函数
void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector& operator=(vector v){swap(v);return *this;}
结束。