最新消息:想得多,做的少。一天到晚瞎鸡巴搞。

STL自问自答之vector

大概数据结构与算法 阿虚 96浏览 0评论

.     需要使用vector需要包含<vector>头文件,<vector>里面只是包含其他几个头文件vector的真正实现实在<stl_vector.h>当中。其它的头文件分别为:<stl_algobase.h>基础算法、<stl_alloc.h>内存管理、<stl_construct .h>全局构造析构函数、<stl_uninitialized.h>内存处理工具、<stl_bvector.h>bit vector实现。除了<stl_bvector.h>这个头文件没有介绍,其他的都在书中前面几个字节介绍了。

vector有哪些操作

通过构造函数插入

//构造一个空的vector
inline vector();
//构造并填充一个vector,大小为n,填充数据为value
inline vector(size_type n, const T& value); 
inline vector(int n, const T& value);
inline vector(long n, const T& value);
//构造一个大小为n的数据为空的vector
explicit inline vector(size_type n);
//完整拷贝一份其他的vector数据
inline vector(const vector<T, Alloc>& x); 
//拷贝一份first开始,last结束的内容
inline vector(const_iterator first, const_iterator last); 
//析构没什么好说的
inline ~vector();插入到尾部

插入函数

//对尾部插入新的数据
inline void push_back(const T& x);
//在position的位置上插入X,并将原本position开始所有的值往后挪动一个位置。
inline iterator insert(iterator position, const T& x);
//在position的位置上插入空值,并将原本position开始所有的值往后挪动一个位置。
inline iterator insert(iterator position);
//在position的位置上插入一块区间范围的数据,并将原本position开始所有的值挪到last之后。
inline void insert(iterator position, const_iterator first, const_iterator last);
//在position的位置上插入n个x值,并将原本position开始所有的值挪到n之后。
inline void insert(iterator pos, size_type n, const T& x);
inline void insert(iterator pos, int n, const T& x);
inline void insert(iterator pos, long n, const T& x);

移除函数

//将最后一个值移除
inline void pop_back();
//移除迭代器所指向的位置上的值。
inline iterator erase(iterator position);
//移除区间从first到last结束的所有值
inline iterator erase(iterator first, iterator last);
//清空vector
inline void clear();

其他vector管理函数

.     不知道是不是错觉,我总感觉下面这三个函数执行的结果和我理解的最终结果不一致。感觉像是BUG一样。

//重新设置vector大小为new_size,并且填充x
inline void resize(size_type new_size, const T& x);
//重新设置vector大小为new_size,并且数据填空
inline void resize(size_type new_size); 
//交换两个vector
inline void swap(vector<T, Alloc>& x);

vector迭代器是什么样的

typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;

inline const_iterator begin() const; 
inline const_iterator end() const;      
inline reverse_iterator rbegin(); 
inline reverse_iterator rend();
inline const_reverse_iterator rbegin() const;
inline const_reverse_iterator rend() const;  
inline reference front(); 
inline reference back(); 
inline const_reference front() const;  
inline const_reference back() const;

.     vector迭代器实现了第三章说的迭代器必须实现的5种类型。但是我并没有在vector头文件中看到有对T*或者const T*做特化版本。那么如果是T*的话valye_type就是T*,而pointer则直接是“T**”了。vector头文件中的迭代器时直接返回T类型的指针给用户直接操作。

vector的内存管理

.     vector内存申请和释放是由typedef simple_alloc<value_type, Alloc> data_allocator;来管理,并使用二级空间分配器。当申请的大小不满足128时由内存池管理,超过128则直接malloc申请。vector的内存管理由三个指针来进行管理。

//表示目前使用空间的头
iterator start;
//表示目前使用空间的尾
iterator finish;
//表示目前可用空间的尾
iterator end_of_storage;

.     vector插入当内存不足那么vector如果此时为空,那么会申请内存大小为2*sizeof(T)大小的内存。如果当前vector的size不为空,那么每次申请的内存空间为size*2大小的空间量,但这只是vector所需要的空间。对于使用了二级空间配适器以下只拿第一次申请内存空间来描述。

.     如果vector申请的内存超过128则直接malloc,不满足的话就由内存池来管理。那么第一次申请空间,vector的空间管理需要满足2*sizeof(T)的空间大小。对于内存池来说它直接会先将2*sizeof(T)大小空间调整为8的倍数大小为N,然后申请空间大小为20*N。如果T为4那么就是8*20=160字节空间大小。其中8字节返回给vector使用,72字节由8字节对应的内存池管理索引进行管理。余下80字节内存池保留待分配。给其他任务。

vector内存不足时有哪些操作

.     vector每次空间不足都必须经历下面几个动作,从内存管理中获取所需要大小的新的内存空间,将旧空间内容数据挪动到新空间上,将旧buffer内存空间交还给内存池管理。

转载请注明:虚无 » STL自问自答之vector

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址