c++STL 容器讲解 (二)
我们今天讲解顺序容器vector，英文为向量，他在内存中是连续的，他既有数组的特性又有数组不具备的特性，那就是他的动态增长，vector可以理解为动态的数组，但是不能缩小
对于vector来说他支持尾部插入而且是非常高效的，但也支持头部或中间插入（非常的低效），因为我们可以想象以下如果对一个数组来说从他的中间或头部插入那将是一个噩梦
因为插入之前必须要把要插入的位置之前的元素往后移一个单元 ，然后在插入，复杂度将会是O（n），而在尾部插入只是O（1）的复杂度，对于500或1000个元素我们可能体会不到，然而一旦数据达到上亿那么无法想象
如果我们要进行大量的删除（一大部分不是尾部删除）和插入（一大部分不是尾部插入），那么我们最好不要用vector，那么list或forword-List 或deque将进入你的选择范围
vector他重载了[ ]支持可以像数组似的随机访问，没错他的随机访问是高效的，这也正是人们喜爱的原因之一
下面我们将列出他的测试代码
//初始化操作
vector<int> vc(a); //a是一个vector<int> 进行拷贝操作
vector<int> vc(10,1); //10个1
int arr[3]={1,2，3}；
vector<int> vc(begin(a),end(a));
vector<int> vc2(a,a+3);
vector<int> vc(100); //100个不定值
//vector<int> 不仅可以装int 开可以装其他数据 以及类
vector<string> vstr; //空的二维vector
vector<vector<int> >vvc; //有一个空格，老的编译器要加
sort(vc.begin(),vc.end()) ; //从小到大排序
find(vc.begin(),vc.end(),value); //找一个元素
#include<vector>
#include<iostream>
using namespace std;
void test4()
{
vector<int,allocator<int > > vc; //我们这里显示的调用vector的分配器，当然也有其他的分配器
for (int i = 0;i < 100;i++)
{
vc.push_back(i);
}
//遍历数组
vector<int>::iterator it = vc.begin();
while (it != vc.end())
{
cout << *it++ << endl;
}
vc.assign(100,2);//将区间[first,last)的元素赋值到当前的vector容器中
//，或者赋n个值为x的元素到vector容器中，这个容器会清除掉vector容器中以前的内容。
/*这是源码实现的assign 这是其中的一个重载 再举两个
void assign(_CRT_GUARDOVERFLOW const size_type _Newsize, const _Ty& _Val)
{ // assign _Newsize * _Val
this->_Orphan_all();
const size_type _Oldsize = size();
const size_type _Oldcapacity = capacity();
if (_Newsize > _Oldcapacity)
{ // reallocate
if (_Newsize > max_size())
{
_Xlength();
}
const size_type _Newcapacity = _Calculate_growth(_Newsize);
if (this->_Myfirst() != pointer())
{ // destroy and deallocate old array
_Destroy(this->_Myfirst(), this->_Mylast());
this->_Getal().deallocate(this->_Myfirst(), _Oldcapacity);
}
_Buy(_Newcapacity);
this->_Mylast() = _Ufill(this->_Myfirst(), _Newsize, _Val);
}
else if (_Newsize > _Oldsize)
{
_Fill_unchecked(this->_Myfirst(), this->_Mylast(), _Val);
this->_Mylast() = _Ufill(this->_Mylast(), _Newsize - _Oldsize, _Val);
}
else
{
const pointer _Newlast = this->_Myfirst() + _Newsize;
_Fill_unchecked(this->_Myfirst(), _Newlast, _Val);
_Destroy(_Newlast, this->_Mylast());
this->_Mylast() = _Newlast;
}
}
*/
cout << vc.data();
/* 返回第一个元素的地址
_NODISCARD _Ty * data() noexcept
{ // return address of first element
return (_Unfancy_maybe_null(this->_Myfirst()));
}
*/
cout<< *( vc.begin());
/*
_NODISCARD iterator begin() noexcept
{ // return iterator for beginning of mutable sequence
return (iterator(this->_Myfirst(), _STD addressof(this->_Get_data())));
}
*/
cout<<*vc.end();
/*
_NODISCARD iterator end() noexcept
{ // return iterator for end of mutable sequence
return (iterator(this->_Mylast(), _STD addressof(this->_Get_data())));
}
*/
cout << vc.at(0); //vc[0]
cout << vc.back(); //返回最后一个元素
cout << vc.capacity(); //返回最大容量
cout << vc.size(); //返回当前元素个数
cout << vc.empty(); //是否为空
vc.clear(); //清空元素 就是删除所有元素
}
int main()
{
test4();
return 0;
}
vector的实现好像一个数组，但当数组用完之后，vector就会自动增长，那么他到底是怎么增长的呢？
我们知道c++中是没有让内存原地增长的机制的，但我们可以制造这样的假象
其实vector是这样的，当vector用光之后，分配器(alloctor)将会分配一块更大的内存，然后将原来的数据赋值过来，在把原来的数据释放掉，那么我们的问题来了，该分配多大的内存呢？ 分配太大又浪费，分配太小下一次插入又会分配，这是一个数组问题
而STL采用的是二倍增长（我学到的） ，这可以说是采用了一个折中的方法
我们可以假设有vector那么一个对象模拟一下
vector一开始为空 插入一个元素，vector内存为1，在插入发现内存不够，二倍扩充变成2，然后在插入发现不够变成4，在插入(插入到4个元素) ，vector内存就会变成8,以此类推
下面我截取了vs的vector源码
// CLASS TEMPLATE vector
template<class _Ty,
class _Alloc = allocator<_Ty>> //这个就是第二模板参数 分配器
class vector
: public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>> //继承了一个父类，至于这个父类有什么，我们暂且不追
{ // varying size array of values
private:
using _Mybase = _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>;
using _Alty = typename _Mybase::_Alty;
using _Alty_traits = typename _Mybase::_Alty_traits;
public:
static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
_MISMATCHED_ALLOCATOR_MESSAGE("vector<T, Allocator>", "T"));
using value_type = _Ty;
using allocator_type = _Alloc;
using pointer = typename _Mybase::pointer;
using const_pointer = typename _Mybase::const_pointer;
using reference = _Ty&;
using const_reference = const _Ty&;
using size_type = typename _Mybase::size_type;
using difference_type = typename _Mybase::difference_type;
using iterator = typename _Mybase::iterator;
using const_iterator = typename _Mybase::const_iterator;
using reverse_iterator = _STD reverse_iterator<iterator>;
using const_reverse_iterator = _STD reverse_iterator<const_iterator>;
//下面几个是构造函数
vector() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Alty>)
: _Mybase()
{ // construct empty vector
}
explicit vector(const _Alloc& _Al) noexcept
: _Mybase(_Al)
{ // construct empty vector, allocator
}
explicit vector(_CRT_GUARDOVERFLOW const size_type _Count, const _Alloc& _Al = _Alloc())
: _Mybase(_Al)
{ // construct from _Count * _Ty(), optional allocator
if (_Buy(_Count))
{ // nonzero, fill it
_TRY_BEGIN
this->_Mylast() = _Udefault(this->_Myfirst(), _Count);
_CATCH_ALL
_Tidy();
_RERAISE;
_CATCH_END
}
}
在实现vector中他是有两个指针维持着的
头指针和尾指针
this->_Mylast() ;
this->_Myfirst();
事实上这个两个指针是public的
当有了这两个指针其他操作就变得简单了
例如当this->_Mylast() = this->_Myfirst();
表示为空 即size（）==0；
源码：
_NODISCARD bool empty() const noexcept
{ // test if sequence is empty
return (this->_Myfirst() == this->_Mylast());
}
size()就是两个指针的差，在类型转化
_NODISCARD size_type size() const noexcept
{ // return length of sequence
return (static_cast<size_type>(this->_Mylast() – this->_Myfirst()));
}
//对this->_Myfirst()解引用就会得到第一个元素的值
_NODISCARD _Ty& front()
{ // return first element of mutable sequence
#if _ITERATOR_DEBUG_LEVEL != 0
_STL_VERIFY(!empty(), “front() called on empty vector”);
#endif /* _ITERATOR_DEBUG_LEVEL != 0 */
return (*this->_Myfirst());
}
至于这个 this->_Mylast() ; 和this->_Myfirst();
c++源码是一层套一层 我服了！
以this->_Myfirst();为例
myfirst是一个这个
pointer& _Myfirst() noexcept
{ // return reference to _Myfirst
return (_Get_data()._Myfirst);
}
_Get_data()是一个这个
_Vector_val<_Val_types>& _Get_data() noexcept
{ // return reference to _Vector_val
return (_Mypair._Get_second());
}
有这么一个模板类_Vector_val
{
-
_Vector_val()
-
_Myfirst(),
_Mylast(),
_Myend()
{ // initialize values
}
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
}
_Mypair是一个这个_Compressed_pair<_Alty, _Vector_val<_Val_types>> _Mypair; 并且是
_Vector_alloc的私有的模板数据对象
你可以往上翻vector模板，里面有
class vector
: public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>
没错vector继承了_Vector_alloc
，连我自己都有点迷糊了
以上只是我粗略的理解，如果有个高明的理解可以告诉我