vector的数据安排以及操作方式与array非常类似。两者唯一的差别就是在于空间的运用灵活性，array是静态空间，一旦分配了就是固定的，无法改变其大小。需要用户重新申请更大的空间，移动数据，释放原来的空间。而vector是动态空间，有其内部的空间分配机制来及时调整空间大小，其实就是vector把申请空间，移动数据，释放原来的空间等操作封装在内部，不需要用户去处理。
接下来我们自己实现一下vector，并给其加上空间配置器。
// 简单的vector容器实现，主要查看其嵌套类iterator迭代器的实现
template<typename T,typename Alloc = allocator<T>>
class MyVector
{
public:
MyVector(const Alloc &alloc = Alloc())
:_allocator(alloc)
{
_first._ptr = _last._ptr = _end._ptr = nullptr;
}
template<typename T>
void push_back(T &&val)
{
if (full())
resize();
_allocator.construct(_last._ptr, std::forward<T>(val));
_last._ptr++;
}
void pop_back()
{
if (empty())
return;
_last._ptr--;
_allocator.destroy(_last._ptr);
}
bool full()const { return _last._ptr == _end._ptr; }
bool empty()const { return _first._ptr == _last._ptr; }
// 容器迭代器的实现
class iterator
{
public:
friend class MyVector;
iterator(T *ptr = nullptr)
:_ptr(ptr) {}
void operator++() { ++_ptr; }
bool operator!=(const iterator &it) { return _ptr != it._ptr; }
T& operator*() { return *_ptr; }
T* operator->() { return _ptr; }
private:
T *_ptr;
};
// 容器的begin方法返回首元素迭代器
iterator begin() { return iterator(_first._ptr); }
// 容器的end方法返回末尾元素后继位置的迭代器
iterator end() { return iterator(_last._ptr); }
private:
iterator _first; // 指向数组其实地址
iterator _last; // 指向最后一个有效元素的后继位置
iterator _end; // 指向数据空间末尾元素的后继位置
Alloc _allocator;// 容器底层的空间配置器
// 容器的扩容函数
void resize()
{
if (_first._ptr == nullptr)
{
_first._ptr = _allocator.allocate(1);
_last._ptr = _first._ptr;
_end._ptr = _first._ptr + 1;
}
else
{
int size = _last._ptr - _first._ptr;
T *ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first._ptr[i]);
_allocator.destroy(_first._ptr + i);
}
_allocator.deallocate(_first._ptr, size);
_first._ptr = ptmp;
_last._ptr = _first._ptr + size;
_end._ptr = _first._ptr + 2 * size;
}
}
};vector的源码；
//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内部只有四个成员变量，三个迭代器和1个空间配置器。
vector维护的是一个连续的线性空间，所以不论其元素类型是什么，普通指针都可以作为vector的迭代器并且满足迭代器的所有必要条件。
实际上，vector的迭代器就是原生指针，只不过换了个名字。在x86系统下，sizeof(vector<int>) 的结果为32。
vector存储数据的空间是线性连续的，因此支持随机的下标访问。
typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
运用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的内存动态增长：当插入新元素时，空间已经不够用的时候，会申请一个新的空间，新空间的大小为当前空间大小的2倍，然后将原来的元素逐个拷贝到新空间里，释放原来的空间，插入新元素。
即 1、2、3、4、6、9…依次增长。在删除元素的时候并不会动态的调整空间的大小
vector内部空间变化：由于vector维护的空间是线性的连续的，因此也就引入一个新的问题，当在某个地方插入或删除新的元素的时候，会导致后面的元素需要逐个后移或前移，让出足够空间来插入这个新元素或者后面的元素前移来覆盖掉要删除的元素。
这些内部的空间变化都会导致相应的迭代器失效，即原先迭代器指向的数据发生了变化，需要注意。
下面是vector提供的一些具体函数：
例：
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int>obj;//创建一个向量存储容器 int
for(int i=0;i<10;i++) // push_back(elem)在数组最后添加数据
{
obj.push_back(i);
cout<<obj[i]<<",";
}
for(int i=0;i<5;i++)//去掉数组最后一个数据
{
obj.pop_back();
}
cout<<"\n"<<endl;
for(int i=0;i<obj.size();i++)//size()容器中实际数据个数
{
cout<<obj[i]<<",";
}
return 0;
}输出结果为：
0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,
clear()清除容器中所有数据
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int>obj;
for(int i=0;i<10;i++)//push_back(elem)在数组最后添加数据
{
obj.push_back(i);
cout<<obj[i]<<",";
}
obj.clear();//清除容器中所以数据
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<endl;
}
return 0;
}输出结果为：
0,1,2,3,4,5,6,7,8,9,排序
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<int>obj;
obj.push_back(1);
obj.push_back(3);
obj.push_back(0);
sort(obj.begin(),obj.end());//从小到大
cout<<"从小到大:"<<endl;
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<",";
}
cout<<"\n"<<endl;
cout<<"从大到小:"<<endl;
reverse(obj.begin(),obj.end());//从大到小
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<",";
}
return 0;
}输出结果为：
从小到大:0,1,3,
从大到小:3,1,0,
访问（直接数组访问&迭代器访问）
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
//顺序访问
vector<int>obj;
for(int i=0;i<10;i++)
{
obj.push_back(i);
}
cout<<"直接利用数组：";
for(int i=0;i<10;i++)//方法一
{
cout<<obj[i]<<" ";
}
cout<<endl;
cout<<"利用迭代器：" ;
//方法二，使用迭代器将容器中数据输出
vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素
for(it=obj.begin();it!=obj.end();it++)
{
cout<<*it<<" ";
}
return 0;
}直接利用数组：0 1 2 3 4 5 6 7 8 9
利用迭代器：0 1 2 3 4 5 6 7 8 9
二维数组两种定义方法（结果一样）
方法一
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N=5, M=6;
vector<vector<int> > obj(N); //定义二维动态数组大小5行
for(int i =0; i< obj.size(); i++)//动态二维数组为5行6列，值全为0
{
obj[i].resize(M);
}
for(int i=0; i< obj.size(); i++)//输出二维动态数组
{
for(int j=0;j<obj[i].size();j++)
{
cout<<obj[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}方法二
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N=5, M=6;
vector<vector<int> > obj(N, vector<int>(M)); //定义二维动态数组5行6列
for(int i=0; i< obj.size(); i++)//输出二维动态数组
{
for(int j=0;j<obj[i].size();j++)
{
cout<<obj[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}