目录
1. vector介绍
1.1. 什么是vector
1.2. vector常用接口
2. vector常用接口模拟实现
2.1. 构造函数+析构函数+operator=
2.2. 迭代器
2.3. 其他常用接口
2.4. 迭代器失效 and memcpy问题
2.4.1.pos位置之前插入
2.4.2erase删除pos位置
2.4.3.memcpy问题
1. vector介绍 1.1. 什么是vector
1.2. vector常用接口1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。
也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。
但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。
当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。
其做法是，分配一个新的数组，然后将全部元素移到这个数组。
就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。
不同的库采用不同的策略权衡空间的使用和重新分配。
但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在 末尾添加和删除元素相对高效。
对于其它不在末尾的删除和插入 *** 作，效率更低。
| 构造函数 | 说明 |
| (★)vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| (★)vector (const vector& x) | 拷贝构造 |
| vector (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
| 类成员函数 | 说明 |
| begin + end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置reverse_iterator |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找 |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 重载[]，使vector像数组一样访问 |
| operator= | 重载= |
对于像vector这样的模板容器，一般不采用声明和定义分离的形式实现！
2.1. 构造函数+析构函数+operator=对于vector在STL源代码的SGI版本中，不同于string的实现，在定义类中的私有变量时不会定义一个指针两个整形的方法；而是定义三个指针，分别指向数组的开头，最后一个有效元素的下一个位置，数组末尾。
#pragma once
#include
#include
#include
using namespace std;
namespace wt
{
template
class vector
{
public:
vector() // 空构造
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
template // 迭代器构造
vector(Intputiterator first, Intputiterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
while (first != last)
{
push_back(*first); // 这里不能采用直接赋值指针的方法，需一个一个尾插
++first;
}
}
void swap(vector& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector(const vector& v) //拷贝构造
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector tmp(v.begin(), v.end()); // 利用迭代器构造临时对象
swap(tmp); // 将临时对象与目标对象交换
}
~vector() // 析构函数
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
vector& operator=(vector v) // 赋值运算符重载
{
swap(v); // 这使用的是传值传参，所以直接将临时对象交换给目标对象即可
return *this;
}
private:
iterator _start; // 记录数组起始位置
iterator _finish; // 记录最后一个有效元素下一个位置
iterator _endofstorage; // 记录数组最大容量位置
};
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;
} // 重载[]
T& operator[](size_t i)
{
return *(_start + i);
}
const T& operator[](size_t i)const
{
return *(_start + i);
}
// 返回vector有效元素个数
size_t size()const
{
return _finish - _start;
}
// 返回vector容量
size_t capacity()const
{
return _endofstorage - _start;
}
// 改变vector有效元素个数
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
*_finish = val;
}
else
{
if (n > capacity()) // 容量不够需要扩容
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
// 扩容
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n]; // 创建临时数组
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size()); // 将原vector中的数据拷贝到tmp中
delete[] _start; // 释放原vector
}
size_t sz = size();
_start = tmp; // 将tmp赋值给vector
_finish = _start + sz;
_endofstorage = _start + n;
}
}
// 尾插
void push_back(T val)
{
if (_finish == _endofstorage) // 检查容量
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = val;
++_finish;
}
// 尾删
void pop_back()
{
assert(_finish != _start); // vector不能为空
--_finish;
}
// pos位置之前插入
iterator insert(iterator pos, T val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
iterator end = _finish + 1;
while (end > pos)
{
*end = *(end - 1);
--end;
}
*pos = val;
return pos;
}
// 删除pos位置
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos;
while (begin < _finish)
{
*begin = *(begin + 1);
++begin;
},
--_finish;
return pos;
}当使用insert时，如果涉及到增容，上面的insert就会出现问题。
例如：
void test()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.insert(v.end(), 5);
vector::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
} 因为，在增容之后，原来的空间被释放掉了，申请了新空间，而迭代器pos没有改变，依然指向原来的位置，就成了野指针！所以，在扩容之后，需改变pos指针！
iterator insert(iterator pos, T val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len; // 扩容后迭代器会失效
}
iterator end = _finish + 1;
while (end > pos)
{
*end = *(end - 1);
--end;
}
*pos = val;
return pos;
}erase也会导致迭代器失效的问题：
void test5()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
} 所以，在使用erase时，删除了元素就不移动迭代器！
void test()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
else
{
++it;
}
}
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
} 2.4.3.memcpy问题
在上面扩容时，使用了memcpy，在这里会存在一些问题。
例如：在vector中存放字符串
void test6()
{
vector v;
v.push_back("111111111");
v.push_back("111111111");
v.push_back("111111111");
v.push_back("111111111");
for (auto& e : v)
{
cout << e << endl;
}
} 现在是没有问题的
再继续尾插时，就会开始增容，增容时会出现崩溃：
void test6()
{
vector v;
v.push_back("111111111");
v.push_back("111111111");
v.push_back("111111111");
v.push_back("111111111");
v.push_back("111111111");
for (auto& e : v)
{
cout << e << endl;
}
} 这是因为在扩容时使用了memcpy，而memcpy只是简单的浅拷贝，如果拷贝像string这样的类，在析构时会导致一块空间被析构两次！
所以扩容时不能使用memcpy，可通过其类型自己的赋值运算符重载完成拷贝。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
size_t sz = size();
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）