- vector的使用语法可以参考文章：https://blog.csdn.net/qq_41453285/article/details/86624816
一、vector概述
- 总的来说：vector是可变大小数组
- 特点：
- 支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
- 元素保存在连续的内存空间中，因此通过下标取值非常快
- 在容器中间位置添加或删除元素非常耗时
- 一旦vector内存不足，重新申请内存之后，和原vector相关的指针，引用，迭代器都失效。内存重分配耗时很长
- 通常，使用vector是最好的选择，如果没有什么特殊要求，最好使用vector
- 与其他容器的比较：
| vector | 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢 |
| deque | 双端队列。支持快速随机访问。在头尾插入/删除速度很快 |
| list | 双向链表。只支持双向顺序访问。在list中任何位置进行插入和删除的速度都很快 |
| forward_list | 单向链表。只支持单向顺序访问。在链表任何位置进行插入和删除操作速度都很快 |
| array | 固定大小数组。支持快速随机访问。不能添加或删除元素 |
| string | 与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入或删除速度快 |
二、vector定义摘要
- vector定于与<stl_vector.h>头文件中
-
//alloc是SGI STL的空间配置器
-
template <
class T, class Alloc = alloc>
-
class
vector {
-
public:
-
// vector 的嵌套类型定义
-
typedef T value_type;
-
typedef value_type* pointer;
-
typedef value_type* iterator;
-
typedef value_type& reference;
-
typedef
size_t size_type;
-
typedef
ptrdiff_t difference_type;
-
-
protected:
-
// simple_alloc是SGI STL的空间配置器，见前面空间适配器文章的介绍
-
typedef simple_alloc<value_type, Alloc> data_allocator;
-
iterator start;
// 表示目前使用空间的头
-
iterator finish;
// 表示目前使用空间的尾
-
iterator end_of_storage;
// 表示目前可用空间的尾
-
-
void insert_aux(iterator position, const T& x);
-
void deallocate() {
-
if (start)
-
data_allocator::deallocate(start, end_of_storage - start);
-
}
-
-
void fill_initialize(size_type n, const T& value) {
-
start = allocate_and_fill(n, value);
-
finish = start + n;
-
end_of_storage = finish;
-
}
-
-
public:
-
iterator begin() {
return start; }
-
iterator end() {
return finish; }
-
size_type size() const {
return size_type(end() - begin()); }
-
size_type capacity() const {
-
return size_type(end_of_storage - begin());
-
}
-
bool empty() const {
return begin() == end(); }
-
reference
operator[](size_type n) {
return *(begin() + n); }
-
-
vector() : start(
0), finish(
0), end_of_storage(
0) {}
-
vector(size_type n,
const T& value) { fill_initialize(n,value); }
-
vector(
int n,
const T& value) { fill_initialize(n,value); }
-
vector(
long n,
const T&value) { fill_initialize(n,value); }
-
explicit vector(size_type n) { fill_initialize(n,T()); }
-
-
~
vector()
-
destroy(start, finish);
//全局函式，见前面文章destroy函数的介绍
-
deallocate();
//这是 vector的㆒个 member function
-
}
-
-
reference front() {
return *begin(); }
// 第一个元素
-
reference back() {
return *(end() -
1); }
// 最后一个元素
-
void push_back(const T& x) {
// 将元素安插至最尾端
-
if (finish != end_of_storage) {
-
construct(finish, x);
//全局函式，见前面文章construct函数的介绍
-
++finish;
-
}
-
else
-
insert_aux(end(), x);
//这是 vector的一个member function
-
}
-
-
void pop_back() {
// 将最尾端元素取出
-
--finish;
-
destroy(finish);
// 全局函式，见前面文章destroy函数的介绍
-
}
-
-
iterator erase(iterator position) {
// 清除某位置上的元素
-
if (position +
1 != end())
-
copy(position +
1, finish, position);
// 后续元素往前搬移
-
--finish;
-
destroy(finish);
// 全局函式，见前面文章destroy函数的介绍
-
return position;
-
}
-
-
void resize(size_type new_size, const T& x) {
-
if (new_size < size())
-
erase(begin() + new_size, end());
-
else
-
insert(end(), new_size - size(), x);
-
}
-
void resize(size_type new_size) { resize(new_size, T()); }
-
void clear() { erase(begin(), end()); }
-
-
protected:
-
// 配置空间并填满内容
-
iterator allocate_and_fill(size_type n, const T& x) {
-
iterator result = data_allocator::allocate(n);
-
uninitialized_fill_n(result, n, x);
// 全局函式，见前面uninitialized_fill_n函数的介绍
-
return result;
-
}
三、vector的迭代器
- vector维护的是一个连续线性空间，所以不论其元素类别是什么，普通指针都可以作为vector的迭代器而满足所有必要条件
- vector迭代器支持有操作有（普通指针也具备）：
- operator*、operator->、operator++、operator--、operator+、operator-、operator+=、operator-=
- vector支持随机存取，而普通指针正有着这样的能力，所以，vector提供的是随机访问迭代器（Random Access iterators）
- vector的迭代器定义如下：
-
template <
class T, class Alloc = alloc>
-
class
vector {
-
public:
-
typedef T value_type;
-
typedef value_type* iterator;
//vector的迭代器是原生指标
-
...
-
};
- 例如：
-
vector<
int>::iterator ivite;
//等同于int* ivite;
-
vector<Shape>::iterator svite;
//等同于Shape* svite;
四、vector的数据结构
- vector的数据结构非常简单：一个线性连续空间
- 下面介绍vector的3个数据结构：
- start：表示目前使用空间的头
- finish：表示目前使用空间的尾
- end_of_storage：表示目前可用空间的尾
-
template <
class T, class Alloc = alloc>
-
class
vector {
-
...
-
protected:
-
iterator start;
//表示目前使用空间的头
-
iterator finish;
//表示目前使用空间的尾
-
iterator end_of_storage;
//表示目前可用空间的尾
-
...
-
};
- 说明：为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量的概念。也就是说，一个vector的容量永远大于或等于其大小。一旦容量等于大小，下次再新增元素时就需要新开辟一块空间。如下图所示
- 运用start、finish、end_of_storage三个迭代器，vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值....等机能，如下：
-
template <
class T, class Alloc = alloc>
-
class
vector {
-
...
-
public:
-
iterator begin() {
return start; }
-
iterator end() {
return finish; }
-
size_type size() const {
return size_type(end() - begin()); }
-
size_type capacity() const {
-
return size_type(end_of_storage - begin());
-
}
-
bool empty() const {
return begin() == end(); }
-
reference
operator[](size_type n) {
return *(begin() + n); }
-
reference front() {
return *begin(); }
-
reference back() {
return *(end() -
1); }
-
...
-
};
五、vector的构造与内存管理（constructor、push_back）
vector的内存管理
- vector默认使用alloc做为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位：
- 于是，data_allocator::allocate(n) 表示配置n个元素空间
构造函数
- vector提供许多构造函数，其中一个允许我们指定空间大小及初值：
push_back()函数
- 当我们以push_back() 将新元素安插入于vector尾端时，该函式首先检查是否还有备用空间，如果有就直接在备用空间上建构元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间（重新配置、搬移数据、释放原空间）
- push_back()原型如下：
vector内存重分配及注意事项
- 注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间
- 注意（重点）： 对vector 的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心
vector内存重分配即容量的增长是有规律的，可以通过下面的公式描述：
- maxSize=maxSize+((maxSize>>1)>1?(maxSize>>1):1)
- 图解：就是由1、2、3、4、6、9...依次增长
- 下面用一个程序测试即可
六、vector的元素操作（pop_back、erase、clear、insert）
- 所提供的元素操作动作很多，不就在此文章中一一说明
pop_back
erase
- 下图是上面这个erase函数的版本
clear
insert
- 注意，插入完成后，新节点将位于哨兵迭代器（即上缪按的position，标示出插入点） 所指之节点的前方——这是STL对于“插入操作”的标准规范。下面的图片展示了insert(position,n,x)的操作
备用空间>=新增元素个数的情况：
- ①备用空间2>=新增元素个数2
- ②插入点之后的现有元素个数3>新增元素个数2
- ③插入点之后的现有元素个数2<=新增元素个数3
备用空间>=新增元素个数的情况：
- 例如下面备用空间2<新增元素个数n==3
转载：https://blog.csdn.net/qq_41453285/article/details/103565158
查看评论