c++: 容器vector
文章目录
- 介绍
- initializer_list
- 与string的不同
- 底层
- 总代码
介绍
C++ 中的 vector 是一种序列容器，它允许你在运行时动态地插入和删除元素。
vector 是基于数组的数据结构，但它可以自动管理内存，这意味着你不需要手动分配和释放内存。
与 C++ 数组相比，vector 具有更多的灵活性和功能，使其成为 C++ 中常用的数据结构之一。
vector 是 C++ 标准模板库（STL）的一部分，提供了灵活的接口和高效的操作。
C++ 中的 vector 是一种序列容器，它允许你在运行时动态地插入和删除元素
vector本质和 string一样也是模板
写法是vector< T > 名称 （T是类型）
他与string的接口差不多，但也有一点不同 。
我们来 看一下vector的构造，第一个是默认构造（看不懂的是内存池先不用管），第二个是n个 val的构造，第三个是迭代器区间的构造，第四个是拷贝构造。
initializer_list
vector 中和string比较增加了 initializer_list容器，这个容器可以作为接口的形参出现。
本身我们的{ }里面的内容就是initializer_list类型的
如
这3段代码 不同，d1本身是是vector< int >型的接受的类型类似于d3 是initializer_list< int >型但是它进行了隐式类型转化。
d2就是{1，2，3，4}作为形参传过去，d3则是{ }的真正类型。
与string的不同
此外vector和string类不同就是vector没有append函数就是不能加一个字符串，即使是vector< string >也只能一个一个加。
从两边形参上看vector只支持迭代器位置的修改，而string还支持下标位置pos的修改，同理其他接口 如erase也是这样
底层
首先我们要知道 和string不一样，定义char ,capacity,size。vector的成员变量都是 用迭代器定义的，我们 又可以把迭代器看作是T 就是类似于指针的东西，所以vector 就是 用指针定义的成员变量。
namespace Z
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
privite:
iterator _start;//头指针类似于.begin()
iterator _finish;//结尾元素的下一位置，类似于.end()
iterator _endofstorage;//类似capacity，_start-_finish得来
};
我们再来写构造函数有默认构造，还有无参构造还有initializer_list构造，析构，还有拷贝构造
vector()//默认
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
vector(initializer_list<T> il)//initializer_list构造
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
~vector()//析构
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
vector(initializer_list<T> il)//initializer_list类型
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
其中initializer_list类型的reserve和 push_back都是省略this指针的。
常见 的一些接口
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)
{
assert(i < size());
return _start[i];
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
// 21:12
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * oldSize);
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;*/
insert(_finish, x);
}
bool empty()
{
return _start == _finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator i = _finish - 1;
while (i >= pos)
{
*(i + 1) = *i;
--i;
}
*pos = x;
++_finish;
}
总代码
namespace Z
{
template<class T>
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)
, _endofstorage(nullptr)
{}
vector(initializer_list<T> il)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
// 21:12
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * oldSize);
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;*/
insert(_finish, x);
}
bool empty()
{
return _start == _finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator i = _finish - 1;
while (i >= pos)
{
*(i + 1) = *i;
--i;
}
*pos = x;
++_finish;
}
void erase(iterator pos);
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};