• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++vector解析(C++11)

原作者: [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 random access iterator to value_type convertible toconst_iterator
const_iterator 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 //默认的初始容量(实际应用中可设置为更大)


附来自C++ Reference的:Modifiers 接口

 
 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap