https://cplusplus.com/reference/vector/vector/
namespace zone
{
template<class T> //需要模板
class vector
{
public:
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
可见,vector内核是由三个指针实现的
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
//v1(v2)
vector(const vector<T>& t)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
for (auto& arr : t)
{
push_back(arr);
}
}
// v1=v2
void swap( vector<T>& t)//swap要求参数是&,且不带const
{
std::swap(_start, t._start);
std::swap(_finish, t._finish);
std::swap(_endofstorage, t._endofstorage);
}
vector<T>& operator=(vector<T> t) // 这里不能用const,因为要调用swap,如果是const会造成权限放大
{
swap(t);
return *this;
}
template <class InputIterator> //在类模板中再次使用模板
vector(InputIterator first, InputIterator last)
{
while (first != last) //记得是!= 不能写成<=,因为存储空间不一定连续!!!!!
{
push_back(*first);
first++;
}
} //可以使用别的类型的迭代器区间去初始化vector,不一定要用vector<T>类型
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t sz = size();
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz); //若类型为string,memcpy会调用浅拷贝,_start和tmp指向同一块空间,然后delete对于自定义类型调用析构函数,销毁空间
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i]; //若为string类型,相当于s1=s2;赋值,会调用拷贝构造,深拷贝
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T()) //若大于容量则扩容,并用val来填充扩容 //表达式会产生临时变量(!!!),有常性,需要用const &或者不用&
{
if (n <= size())
{
_finish = _start + n; //缩容
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
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;
}
void insert(iterator pos, const T& x) //在pos位置插入x,
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//扩容会导致原空间被删除,如果没有len记录长度并重新赋值pos,会导致pos失效(pos依旧指向被删除空间的某个位置而不是新空间的某个位置)
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
void push_back(const T& x)
{
insert(_finish, x);
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
1.capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2 倍增长的!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是 根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。 2.reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代 价缺陷问题。 3.resize在开空间的同时还会进行初始化,影响size。
假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问 题?
int main()
{
bite::vector<bite::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
问题分析: 1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存 空间中 2. 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型 元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅 拷贝。
// 以杨慧三角的前n行为例:假设n为5
void test2vector(size_t n)
{
// 使用vector定义二维数组vv,vv中的每个元素都是vector<int>
bit::vector<bit::vector<int>> vv(n);
// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)
vv[i].resize(i + 1, 1);
// 给杨慧三角出第一列和对角线的所有元素赋值
for (int i = 2; i < n; ++i)
{
for (int j = 1; j < i; ++j)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
bit::vector> vv(n); 构造一个vv动态二维数组,vv中总共有n个元素,每个元素 都是vector类型的,每行没有包含任何元素,如果n为5时如下所示:
vv中元素填充完成之后,如下图所示: