C++vector解析（C++11）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

Vector表示可以改变大小的数组容器。

就像数组，其元素的向量使用连续的存储位置，这意味着还可以访问其元素上使用偏移量经常指向元素的指针，和在数组中一样有效。但与数组不同，其大小可动态变化，他们的存储容器自动处理。

在vector内部，使用动态分配的数组向量来存储他们的内容。此数组可能需要重新分配，以便规模的扩大新元素被插入时，这意味着为它分配一个新的数组，并将所有元素。这是一种相对较昂贵的任务在处理时间方面，因此，向量不重新分配每个时间元素添加到容器。

Vector，Deque，List 三个容器同属序列容器，操作统一。

类型如下：

member type	definition	notes
`value_type`	The first template parameter (`T`)
`allocator_type`	The second template parameter (`Alloc`)	defaults to:`allocator<value_type>`
`reference`	`value_type&`
`const_reference`	`const value_type&`
`pointer`	`allocator_traits<allocator_type>::pointer`	for the default allocator:`value_type*`
`const_pointer`	`allocator_traits<allocator_type>::const_pointer`	for the default allocator:`const value_type*`
`iterator`	a random access iterator to `value_type`	convertible to`const_iterator`
`const_iterator`	a random access iterator to `const value_type`
`reverse_iterator`	`reverse_iterator<iterator>`
`const_reverse_iterator`	`reverse_iterator<const_iterator>`
`difference_type`	a signed integral type, identical to: `iterator_traits<iterator>::difference_type`	usually the same as ptrdiff_t
`size_type`	an unsigned integral type that can represent any non-negative value of `difference_type`	usually the same as size_t

Vector操作接口如下：

（部分来自其他实现）

上诉接口的实现：

//此处代码来自清华大学邓俊辉老师

typedef int Rank; //秩 
template <typename T> class Vector { //向量模板类
protected:
    Rank _size; int _capacity; T* _elem; //规模、容量、数据区
    void copyFrom ( T const* A, Rank lo, Rank hi ); //复制数组区间A[lo, hi)
    void expand(); //空间不足时扩容
    void shrink(); //装填因子过小时压缩
    bool bubble ( Rank lo, Rank hi ); //扫描交换
    void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
    Rank max ( Rank lo, Rank hi ); //选取最大元素
    void selectionSort ( Rank lo, Rank hi ); //选择排序算法
    void merge ( Rank lo, Rank mi, Rank hi ); //归并算法
    void mergeSort ( Rank lo, Rank hi ); //归并排序算法
    Rank partition ( Rank lo, Rank hi ); //轴点构造算法
    void quickSort ( Rank lo, Rank hi ); //快速排序算法
    void heapSort ( Rank lo, Rank hi ); //堆排序（稍后结合完全堆讲解）
public:
// 构造函数
    Vector ( int c = DEFAULT_CAPACITY, int s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v
    { _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
    Vector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //数组整体复制
    Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //区间
    Vector ( Vector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //向量整体复制
    Vector ( Vector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //区间
// 析构函数
    ~Vector() { delete [] _elem; } //释放内部空间
// 只读访问接口
    Rank size() const { return _size; } //规模
    bool empty() const { return !_size; } //判空
    int disordered() const; //判断向量是否已排序
    Rank find ( T const& e ) const { return find ( e, 0, _size ); } //无序向量整体查找
    Rank find ( T const& e, Rank lo, Rank hi ) const; //无序向量区间查找
    Rank search ( T const& e ) const //有序向量整体查找
    { return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
    Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量区间查找
// 可写访问接口
    T& operator[] ( Rank r ) const; //重载下标操作符，可以类似于数组形式引用各元素
    Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符，以便直接克隆向量
T remove ( Rank r ); //删除秩为r的元素
    int remove ( Rank lo, Rank hi ); //删除秩在区间[lo, hi)之内的元素
    Rank insert ( Rank r, T const& e ); //插入元素
    Rank insert ( T const& e ) { return insert ( _size, e ); } //默认作为末元素插入
    void sort ( Rank lo, Rank hi ); //对[lo, hi)排序
    void sort() { sort ( 0, _size ); } //整体排序
    void unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱
    void unsort() { unsort ( 0, _size ); } //整体置乱
    int deduplicate(); //无序去重
    int uniquify(); //有序去重
// 遍历
    void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）
    template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
    }; //Vector
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）