目录
- 基本接口函数介绍
-
- vector模拟实现
- reserve
- 迭代器
- 空间容量
- 删除
- insert
- 析构函数
- vector拷贝构造函数
- 拷贝赋值运算符
基本接口函数介绍
函数名 | 功能 |
---|
vector()(重点) | 无参构造,构造一个空容器,没有元素。 |
vector(size_type n, const value_type& val = value_type()) | 构造并初始化n个val |
vector (const vector& x); (重点) | 拷贝构造 |
vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
测试:
void func()
{
int arr[] = {8,4,3,6,1};
vector<int> vc;
vector<int> vc1(10,5);
vector<int> vc2(vc1);
vector<int> vc3(arr ,arr + sizeof(arr) / sizeof(arr[0]));
test(vc);
test(vc1);
test(vc2);
test(vc3);
}
测试效果
调用不带参数的构造函数,成员属性初始值值会给0
迭代器
迭代器分类
iterator的使用 | 接口说明 |
---|
begin +end(重点) | 获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置 |
rbegin + rend | 获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的 |
void test1(vector<int> &v)
{
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it++ << " ";
}
cout << endl;
}
void test2(vector<int>& v)
{
vector<int>::reverse_iterator it = v.rbegin();
while (it != v.rend())
{
cout << *it++ << " ";
}
cout << endl;
}
空间容量
容量空间 | 接口说明 |
---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize(重点)
1、调整容器大小,使其包含n个元素。
2、如果n小于当前容器的大小,则将内容减少到其前n个元素,并删除(并销毁)超过的元素。
3、如果n大于当前容器的大小,则在容器的末尾插入足够多的元素来扩展容器的内容,使容器的大小达到n。如果指定了val,则将新元素初始化为val的副本,否则将对它们进行值初始化。
reserve (重点)
请求向量容量至少足以容纳n个元素。
如果n大于当前的容量,该函数将导致容器重新分配其存储空间,将其容量增加到n(或更大)。
在所有其他情况下,函数调用不会导致重新分配,vector容量也不会受到影响。 也不能改变它的元素。
1、capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,顺序表增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
2、reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
3、resize在开空间的同时还会进行初始化,影响size
用一份测试代码去观察:
void func1()
{
vector<int> v;
int size = v.capacity();
cout << size << endl;
for (int i = 0; i < 100; i++)
{
v.push_back(i);
if (v.capacity() != size)
{
size = v.capacity();
cout << "扩容后:" << size << endl;
}
}
}
vs下capacity是按1.5倍增长的
在linux下以2倍增长
增删查改
vector增删查改 | 接口说明 |
---|
push_back(重点) | 尾插 |
pop_back (重点) | 尾删 |
find | 查找。(注意这个是算法模块实现,不是vector的成员接口) |
insert | 在position之前插入val |
erase | 删除position位置的数据 |
swap | 交换两个vector的数据空间 |
operator[] (重点) | 返回此下标位置的值 |
void func1()
{
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 val : v)
{
cout << val << " ";
}
cout << endl;
vector<int>::iterator pos = find(v.begin(),v.end(),2);
if (pos != v.end())
{
v.insert(pos,30);
}
for (auto val : v)
{
cout << val << " ";
}
cout << endl;
pos = find(v.begin(), v.end(), 30);
if (pos != v.end())
{
v.erase(pos);
}
for (auto val : v)
{
cout << val << " ";
}
}
迭代器失效问题探讨
野指针问题
void func2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
v.insert(pos,10);
it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
v.erase(pos);
it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
}
这个程序的运行是会存在错误的,错误的原因是pos还在访问那块旧的空间,pos迭代器却早已经失效了,旧空间释放后内存使用权限已经归还给操作系统了,而pos还指向那块旧的空间,v.erase(pos);这句代码就是去访问一块非法内存,所以就会程序崩溃
图解:
下面这块程序的功能是将容器中所有的偶数都删除掉,只保留奇数数据
这段程序在不同的平台上是不一样的
void func1()
{
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);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
it++;
}
for (auto e : v)
{
cout << e << " ";
}
}
在vs上,程序就直接崩溃了
在linux上出现段错误
图解析:
从图中我们可以看出it每次删元素的时候都会跳过一个元素,end的位置每次也都在发生变化,直到删除6的时候 it 和 end已经开始错开了,分道扬镳,此后再也不会相遇,it此时就是野指针了,访问了一块非法的内存,但是在linux上平台上我们只需要将尾插一个7(奇数)就能解决这个问题,vs下无论是最后一个值是奇数还是偶数都会报错,it已经失效,编译器会直接对it++检查
是因为当插入7的时候刚好检查到最后一个位置不会再erase掉,it再往后迭代的时候就遇到了end,循环也就终止了,但是这段代码还是错误的代码,因为不同的平台跑出的结果是不一样的
解决方案
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
it++;
}
}
总结:
insert和erase都会导致迭代器失效
1、insert(it, x) 或者 erase(it) 以后迭代器的意义变了
2、insert(it, x) 或者 erase(it) 以后it变成了野指针
vector模拟实现
namespace mzt
{
template<class T>
class vector
{
public:
typedef T* iterator;
iterator begin() { return _start; }
iterator end() { return _finish; }
size_t capacity() { return _endofstroage - _start; }
size_t size() { return _finish - _start; }
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstroage(nullptr)
{ }
vector(vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstroage(nullptr)
{
reserve(v.capacity());
for (auto &e : v)
{
push_back(e);
}
}
void swap(vector<T>& v)
{
::swap(_start,v._start);
::swap(_finish,v._finish);
::swap(_endofstroage,v._endofstroage);
}
vector<T>& operator=(vector<T> v)
{
if (this != &v)
{
swap(v);
}
return *this;
}
void reserve(size_t n)
{
size_t sz = size();
T* tmp = new T[n];
if (n > capacity())
{
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_endofstroage = _start + n;
}
}
void push_back(const T& v)
{
if (_finish == _endofstroage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish++ = v;
}
void erase()
{
assert(!empty());
--_finish;
}
void resize(size_t n,T a = T())
{
if (n < capacity())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish < _endofstroage)
{
*_finish++ = a;
}
}
}
size_t operator[](size_t n)
{
assert(n < size());
return _start[n];
}
iterator insert(iterator pos, const T& x)
{
if (_finish == _endofstroage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(!empty());
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
--_finish;
return pos;
}
bool empty() { return _start == _finish; }
~vector()
{
if (_start)
{
delete[] _start;
}
_start = _finish = _endofstroage = __nullptr;
}
private:
iterator _start;
iterator _finish;
iterator _endofstroage;
};
}
私有成员
iterator _start;
iterator _finish;
iterator _endofstroage;
reserve
size_t size()const
{
return _finish - _start;
}
void reserve(size_t n)
{
if(n > capapcity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for(size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstroage = _start + n;
}
}
这里需要注意的是_start = tmp;的时候_start 就已经指向新的空间了,如果使用_start + size()回去调用size函数
那就成了这样了:_start + (_finish - _start),那就会很有可能是一个负数了,当然我们的编译器也不会这么傻
当断点执行到这一行的时候_finish指向的位置还是0x00000000,那么_finish压根就没变,解决办法,防止_start指向新空间后地址变了,我们先提前备份好size个数据
void push_back(const T& v)
{
if (_finish == _endofstroage)
{
size_t newcapacity = capacity() == 0 ? 4
: capacity() * 2;
reserve(newcapacity);
}
*_finish = v;
_finish++;
}
跟顺序表的尾插类似,考虑扩容就行
迭代器
typedef T* iterator;
iterator begin() const
{ return _start; }
iterator end() const
{ return _finish; }
提一句,范围for的底层是支持迭代器的,迭代器原理类似指针
空间容量
下面的接口函数我们直接对照图就可以清晰地理解
size_t capacity() const
{
return _endofstroage - _start;
}
size_t size()const
{
return _finish - _start;
}
删除
void erase()
{
assert(!empty());
--_finish;
}
bool empty() const{ return _start == _finish; }
resize
void resize(size_t n,T a = T())
{
if (n < capacity())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish < _endofstroage)
{
*_finish++ = a;
}
}
}
resize的3个情况
1、指定空间小于实际空间容量,那么就做缩容处理,将空间调整到n个大小
2、size() < n < capacity() ,那么就对这段区间的空间初始化
3、n > capacity() ,先扩容到n个大小的空间,再对这段空间初始化
insert
insert在指定pos位置插入一个数据,并返沪pos位置的迭代器
iterator& insert(iterator pos, const T &x)
{
if (_finish == _endofstroage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 :
capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
return pos ;
}
需要注意的是这里的insert会引发迭代器失效的问题,即使在函数内部将pos迭代器的位置处理了,但是值传递并不会影响到实参,所以外面的pos 还是失效了,需要再次重新给pos赋值,
析构函数
~vector()
{
if (_start)
{
delete[] _start;
}
_start = _finish = _endofstroage = __nullptr;
}
释放空间,将_start、_finish 、_endofstroage 这三个指针置空
vector拷贝构造函数
不复用接口写法
vector(vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstroage(nullptr)
{
_start = new T[v.capacity()];
memcpy(_start,v._start,sizeof(T) * v.size());
_finish = _start + v.size();
_endofstroage = _start + v.capacity();
}
复用接口的写法
vector(vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstroage(nullptr)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
区别不大,都是为了先给_start开一块新的空间,再将原数据拷贝过来,推荐第二种写法,代码更简洁
拷贝赋值运算符
vector<T>& operator=(const vector<T> v)
{
if (this != &v)
{
swap(v);
}
return *this;
}
vector<T>& operator=(const vector<T> &v)
{
if (this != &v)
{
delete[]_start;
_start = new T[v.capacity()];
memcpy(_start,v._start,sizeof(T)* v.size());
_finish = _start + v.size();
_endofstroage = _start + v.capacity();
}
return *this;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)