1.vector是什么？
- vector是STL中表示可变大小数组的序列容器。
- 和数组一样，vector也可以使用下表访问，因为采用连续的空间存储。vector的大小还可以动态增长，并且由容器自动管理。
- 本质上，vector使用动态分配数组来存储元素，插入一个新的元素时，这个数组需要重新分配大小为了增加存储空间。其做法是，每插入一个元素，都会申请一个新的数组，将数据移到这个新的数组，时间代价相对高 ，所以每次有元素要插入时，vector不会每次都重新分配大小。
- vector分配空间的策略实际并不会只开实际需要的大小，而是会分配一些额外的空间以适应可能的增长。不同的库采用不同的策略来进行空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小来进行，以至于在尾部插入数据是在常数时间内完成的
- 因此，vector占用的更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长
2.vector的使用
2.1 vector 的constructor(构造函数)
- 无参的构造函数 ：vector();
- 构造并初始化n个value : vector(size_type n,const value_type& val =value_type()); //value_type实际就是模板的参数T
- 拷贝构造函数 ： vector(const vector& x);
- 迭代器区间进行构造：vector(Inputlterator first,Inputlteratorl last);
vector<int> v1;//无参构造
8 vector<int> v2(5,55);//构造有5个55的vector
9 vector<int> v3(v2);//拷贝构造
10 vector<int> v4(v3.begin(),v3.end());//迭代器区间构造
2.2 vector iterator的使用
begin()/end() 获取第一个数据位置的iterator/const_iterator，获取最后一个位置下一个的iterator/const_iterator
rbegin()/rend() 获取最后一个数据位置的iterator/const_iterator，获取第一个位置前一个的iterator/const_iterator
vector<int>:: iterator it1 = v2.begin();
32 while(it1!=v2.end())
33 {
34 cout << *it1 << " ";
35 it1++;
36 }
37 cout << endl;
38 const vector<int> v5;
39 vector<int>::const_iterator it2 = v5.begin();
40 while(it2!=v5.end())
41 {
42 cout << *it2 << " ";
43 it2++;
44 }
45 cout << endl;
46 vector<int>:: reverse_iterator it3 = v2.rbegin();
47 while(it3!=v2.rend())
48 {
49 cout << *it3 << " ";
50 it3++;
51 }
52 cout << endl;
53 const vector<int> v6;
54 vector<int>::const_reverse_iterator it4 = v6.rbegin();
55 while(it4!=v6.rend())
56 {
57 cout << *it4 << " ";
58 it4++;
59 }
60 cout << endl;
2.3 vector 空间增长
- size：获取数据个数
- capcacity：获取容量大小
- empty：判断是否为空
- reserve：改变vector的capacity //reserve只负责开辟空间，如果事先知道要用多少空间，可以避免vector的扩容问题
- resize：改变vector的size //resize在开辟空间是还会初始化，影响size
cout << v2.size() << endl;
cout << v2.capacity() << endl;
cout << v2.empty() << endl;
v2.reserve(100);
cout << v2.size() << endl;
cout << v2.capacity() << endl;
v2.resize(10,6);
cout << v2.size() << endl;
cout << v2.capacity() << endl;
2.4 vector 增删查改
- push_back：尾插
- pop_back：尾删
- insert：在position的位置之前插入数据
- erase：删除position位置的数据
- operator[]：像数组一样访问
- swap：交换两个vector的数据空间
vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.pop_back();
vec.insert(vec.end(),10);
vec.insert(vec.end(),20);
vec.insert(vec.end(),30);
vec.erase(vec.begin());
for(size_t i=0;i<vec.size();i++)
{
cout << vec[i] << " ";
}
cout << endl; 3.vector 的模拟实现
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
namespace hj
{
template<class T>//创建一个模板类vector
class vector{
public:
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;
}
//构造
vector()
:_start(nullptr),
_finish(nullptr),
_en_of_storage(nullptr)
{}
//析构
~vector()
{
delete[] _start;
_start = _finish = _en_of_storage;
}
//迭代器区间构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr),
_finish(nullptr),
_en_of_storage(nullptr)
{
while(first != last)
{
push_back(*first);
++first;
}
}
void swap(vector<T>& v)//交换两个vector的值
{
std::swap(v._start,_start);
std::swap(v._finish,_finish);
std::swap(v._en_of_storage,_en_of_storage);
}
//拷贝构造-深拷贝
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_en_of_storage(nullptr)
{
vector<T> tmp(v.begin(),v.end());
swap(tmp);
}
//赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
size_t size()
{
return _finish - _start;
}
size_t capacity()
{
return _en_of_storage - _start;
}
void reserve(size_t n)//扩容
{
if(n > capacity())
{
size_t len = size();
T* tmp = new T[n];
if(_start)//判断是否为空
{
for(size_t i = 0;i < len; i++)//拷贝数据
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + len;
_en_of_storage = _start + n;
}
}
void resize(size_t n,T& val=T())//设置有效数据个数
{
if(n>capacity())//扩容
{
reserve(n);
}
if(n>size())
{
while(_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
void push_back(const T& val)
{
insert(_finish,val);
}
void pop_back()
{
erase(_finish-1);
}
iterator insert(iterator pos,const T& val)
{
assert(pos >=_start);
assert(pos <=_finish);
if(_finish == _en_of_storage)//判断扩容
{
size_t len = pos - _start;
reserve(capacity()==0?4:capacity()*2);
pos = _start + len;//更新扩容后pos的位置
}
iterator end = _finish-1;
while(end >= pos)
{
*(end+1) = *(end);//用end = end-1在pos为_start时会越界
end--;
}
*pos = val;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos+1;
while(begin < _finish)
{
*(begin-1) = *begin;
begin++;
}
_finish--;
return pos;
}
T& operator[](size_t sz)
{
assert(sz < size());
return *(_start + sz);
}
const T& operator[](size_t sz)const
{
assert(sz < size());
return *(_start + sz);
}
T& front()
{
assert(size()>0);
return *_start;
}
T& back()
{
assert(size()>0);
return *(_finish-1);
}
private:
iterator _start;
iterator _finish;
iterator _en_of_storage;
};
void test_vector1()//测试基本功能
{
vector<int> v1;//构造
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1);//拷贝构造
for(auto ch : v1)//迭代器
{
cout << ch << " ";
}
cout << endl;
for(auto ch : v2)
{
cout << ch << " ";
}
cout << endl;
for(size_t i=0;i<v2.size();i++)//[]重载
{
cout << v1[i] << " ";
}
cout << endl;
vector<int> v3;
v3=v1;//赋值重载
for(auto ch : v3)
{
cout << ch << " ";
}
cout << endl;
v3.erase(v3.begin());//删除
v3.erase(v3.end()-1);
for(auto ch : v3)
{
cout << ch << " ";
}
cout << endl;
cout<< "size->"<<v1.size()<<endl;
cout<< "capacity->"<<v1.capacity()<<endl;
}
}
本文含有隐藏内容，请 开通VIP 后查看