1.描述
vector的基本操作实现(包括迭代器)
2.基本操作
3.代码
#ifndef DS_EXCEPTIONS_H
#define DS_EXCEPTIONS_H
class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };
#endif
#ifndef VECTOR_H
#define VECTOR_H
#include <cstdio>
#include "dsexceptions.h"
template <typename Object>
class Vector
{
public:
explicit Vector( int initSize = 0 )
: theSize( initSize ), theCapacity( initSize + SPARE_CAPACITY ), currentIndex(0)
{ objects = new Object[ theCapacity ]; }
Vector( const Vector & rhs ) : objects( NULL )
{ operator=( rhs ); }
~Vector( )
{ delete [ ] objects; }
bool empty( ) const
{ return size( ) == 0; }
int size( ) const
{ return theSize; }
int capacity( ) const
{ return theCapacity; }
//操作符[]重载
Object & operator[]( int index )
{
#ifndef NO_CHECK
if( index < 0 || index >= size( ) )
throw ArrayIndexOutOfBoundsException( );
#endif
return objects[ index ];
}
//const操作符[]重载
const Object & operator[]( int index ) const
{
#ifndef NO_CHECK
if( index < 0 || index >= size( ) )
throw ArrayIndexOutOfBoundsException( );
#endif
return objects[ index ];
}
//操作符=重载,实现对象复制
const Vector & operator= ( const Vector & rhs )
{
if( this != &rhs )
{
delete [ ] objects;
theSize = rhs.size( );
theCapacity = rhs.theCapacity;
objects = new Object[ capacity( ) ];
for( int k = 0; k < size( ); k++ )
objects[ k ] = rhs.objects[ k ];
}
return *this;
}
//重新设置vector尺寸(两倍)
void resize( int newSize )
{
if( newSize > theCapacity )
reserve( newSize * 2 );
theSize = newSize;
}
//设置vector尺寸(修改大小,并拷贝所有元素到新的数组,并销毁原来的数组)
void reserve( int newCapacity )
{
Object *oldArray = objects;
//1.重设size,capacity
int numToCopy = newCapacity < theSize ? newCapacity : theSize;
//capacity是在size的基础上加一个常数
newCapacity += SPARE_CAPACITY;
//2.建立新的数组,并拷贝元素到新数组
objects = new Object[ newCapacity ];
for( int k = 0; k < numToCopy; k++ )
objects[ k ] = oldArray[ k ];
theSize = numToCopy;
theCapacity = newCapacity;
//删除原来的数组
delete [ ] oldArray;
}
// Stacky stuff
//放置元素,一旦容量达到最大就重置大小
void push_back( const Object & x )
{
if( theSize == theCapacity )
reserve( 2 * theCapacity + 1 );
objects[ theSize++ ] = x;
}
//删除最后元素
void pop_back( )
{
if( empty( ) )
throw UnderflowException( );
theSize--;
}
//最后元素
const Object & back ( ) const
{
if( empty( ) )
throw UnderflowException( );
return objects[ theSize - 1 ];
}
//为了遍历vector中的元素,实现一个iterator迭代器(迭代器其实就是指向数组的指针,并对指针操作进行了封装)
// Iterator stuff: not bounds checked
typedef Object * iterator;
typedef const Object * const_iterator;
iterator begin( ){
currentIndex = 0;
return &objects[ currentIndex ];
}
const_iterator begin( ) const{
currentIndex = 0;
return &objects[ currentIndex ];
}
iterator end( ){
return &objects[size( )];
}
const_iterator end( ) const{
return &objects[size( )];
}
iterator next(){
currentIndex++;
if( currentIndex < 0 || currentIndex > size( ) )
throw ArrayIndexOutOfBoundsException( );
return &objects[currentIndex];
}
//插入操作
void insert(int position, const Object & x ){
//从这里我们也可以看出,插入操作会导致迭代器失效的原因所在(从新分配了空间,原迭代器变成了悬垂指针)
if( theSize == theCapacity )
reserve( 2 * theCapacity + 1 );
if(position > theSize || position < 0){
throw ArrayIndexOutOfBoundsException( );
}else{
for(int i=theSize-1; i>=position; i--){
objects[i+1] = objects[i];
}
objects[ position ] = x;
theSize++;
}
}
//插入(利用迭代器)
iterator insert(iterator position, const Object& x ){
if( theSize == theCapacity )
reserve( 2 * theCapacity + 1 );
if(position<begin() || position>end())
throw ArrayIndexOutOfBoundsException( );
iterator ite = end();
while(ite != position){
*ite = *(ite-1);
ite--;
}
*position = x;
theSize++;
return begin();
}
//擦除从指定位置起数据
iterator erase(iterator position){
if(position<begin() || position>end())
throw ArrayIndexOutOfBoundsException( );
while(position != end()){
theSize--;
}
return begin();
}
//擦除从指定范围内的数据
iterator erase(iterator first, iterator last){
if((first < begin() || first>end()) || (last < begin() || last>end()) || first>last)
throw ArrayIndexOutOfBoundsException( );
if(last == end()) erase(first);
//1.先将指定范围内的数据覆盖
int i=1;
while(first != last+1){
*first = *(last+i);
first++;
theSize--;
i++;
}
//2.将覆盖所用数据剩余部分前移(如1,2,3,4,5,6要删除2,3先用4,5覆盖2,3-->1,4,5,4,5,6-->然后6前移到4的位置-->1,4,5,6)
i--;
while(last <= end()){
last++;
*last = *(last+i);
}
return begin();
}
bool isEnd(){
if(currentIndex < 0 || currentIndex >= size( ))
return true;
return false;
}
//操作符++重载(前增量,++a),注还有后增量的重载差不多,只是Object & operator++(int a)有参数
Object & operator++()
{
currentIndex++;
if( currentIndex < 0 || currentIndex > size( ) )
throw ArrayIndexOutOfBoundsException( );
return objects[ currentIndex ];
}
//操作符--重载
Object & operator--()
{
currentIndex--;
if( currentIndex < 0 || currentIndex > size( ) )
throw ArrayIndexOutOfBoundsException( );
return objects[ currentIndex ];
}
enum { SPARE_CAPACITY = 16 };
private:
int theSize;
int theCapacity;
int currentIndex;//仅用于iterator
Object * objects;
};
#endif
#include "vector.h"
#include <iostream>
using namespace std;
int main( )
{
Vector<int> v;
for( int i = 0; i < 10; i++ )
v.push_back( i );
for( int i = 0; i < 10; i++ )
cout << v[ i ] << " ";
//利用操作符--输出
Vector<int>::iterator t = v.end()-1;//注意end()返回的是最后元素之后的位置
cout<<endl;
for(; t >= v.begin(); t--){
cout<< *t <<" ";
}
cout<<endl;
Vector<int>::iterator k = v.begin();
while(!v.isEnd()){
cout<< *k <<" ";
k = v.next();
}
Vector<int>::iterator m = v.begin()+6;
//m = v.erase(m);//正确用法
v.erase(m); //这样是错误的,会使当前迭代器m失效,必须返回新的迭代器,像上面那样用
cout<<"\nerase:"<<*m<<endl;
for(m=v.begin(); m != v.end(); ){
cout<< *m <<" ";
m = v.next();
}
Vector<int>::iterator mm = v.begin()+2;
mm = v.insert(mm, 5);
cout<<endl;
for(; mm != v.end(); ++mm){
cout<< *mm <<" ";
}
return 0;
}
4.从上面的迭代器实现,可以看出,为了方便指针操作,使用了迭代器封装指针操作,这样使得指针操作变得简单
明白两点:a.迭代器的原理,从上面代码可以看出,就是指针操作
b.迭代器自增原理,当size=capacity的时候,长度会增长一倍
c.size和capacity的区别?为什么用capacity?(使用capacity是为了避免空间浪费,譬如size=20,capacity=30,如果没有capacity
那么大小为21的数据就会使用41个空间的长度(当插入最后一个元素的时候从新分配空间),而有了capacity就不用重新分配)
分享到:
相关推荐
纯c语言的向量vector实现,实现c++中vector的一些基本的特性和操作,适用于一些只支持c语言的平台上使用vector数据结构,包含测试用例以及函数的使用范例
用c++开发语言,模拟是下std标准库中的Vector基本的功能,复习下Vector标准库的相关知识,特留下此笔记
vector 是 C++ 标准库中定义的一种动态数组,它可以自动管理内存并根据需要调整大小。它是一种非常有用的数据结构,用于存储和管理一组元素。 用途 vector 可以用于各种目的,包括: 存储一组相关数据,例如学生...
虽然用C++实现神经网络会比较麻烦,不过如果注意到以下下的trick, 在用C++实现神经网络时会舒服很多,代码也会非常简明,...我最近实现了一把基本的神经网络,包括LR和多层NN模型, 使用C++11, Visual Studio 2017开发
自己学C++的时候,写的一个解释程序源代码。实现了若类型的vector,功能基本健全。学习交流而已。
1、如何实现一个类似于vector的容器myVector, 该容器能像vector一样可以实例化为存放某种数据数据的数据,并能对数据提供基本的管理, 如插入数据、删除某指定的数据、可以动态扩容、可以删除全部数据等。 2、如何...
array (C++11) − vector map − unordered_map (C++11) priority_queue − span (C++20) 其他容器: 顺序 − 关联 无序关联 − 适配器 迭代器库 范围库 (C++20) 算法库 数值库 常用数学函数 特殊数学函数 ...
之前学习C语言的时候,用链表实现过通讯录的基本功能。最近写了一个C++版本的通讯录,参考代码如下所示。 main.cpp /***************************************************** Copyright (C): 2017-2018 File name ...
C/C++,文件IO,类型转换,类,多态实现,LIST实现,VECTOR实现,二叉树实现,C语言文件IO,基本C和C++书本上的东西都有很精简的代码实现,STL使用等等等等。。。出自两个C/C++的高手,哈哈,分享一下,希望那两位...
2)数据结构里面两种非常重要的存储结构,线性结构中的连续存储结构(代表vector数组)和非连续存储结构(代表list链表),他们两者被广泛的应用在各个领域,是最基本最基础的两种存储结构; 3)之前的友元类只是...
已经执行的指令号存放在一个vector变量中,可以调用泛型算法来确定当前生成的随机数是否已经存在。 根据老师提供的指令访问次序原则,写了一个GetNext函数,根据当前已经执行的指令条数和上一条指令来生成下一条...
3.10 C++类与vector类 3.11 总结 3.12 练习 复习题 第4章 函数一:基础 4.1 C++中的函数 4.1.1 只由一个main函数构成的程序 4.1.2 包含多个函数的程序 4.1.3 函数是个好东西 4.1.4 三个重要的问题 4.2 函数:基本...
本书通过使用标准C++语言的新特性,如引用参数、流库、string类以及vector模板,从而最大限度地避免使用易于出错的程序结构。指针也只主要应用在多态和链表的实现上。 ● 较早引入对象。本书分两个阶段介绍对象。从...
8.2 C++异常处理的实现 35 8.2.1异常基本语法 35 8.2.2栈解旋(unwinding) 39 8.2.3异常接口声明 40 8.2.4异常类型和异常变量的生命周期 40 8.2.5异常的层次结构(继承在异常中的应用) 46 8.3标准程序库异常 47 8.4...
C++中当 vector 中的数据类型为基本类型时我们调用std::sort函数很容易实现 vector中数据成员的升序和降序排序,然而当vector中的数据类型为自定义结构体类型时,我们该怎样实现升序与降序排列呢?有两种方法,下面...
4.2 C++ STL的各种实现版本 49 4.2.1 HP STL 49 4.2.2 SGI STL 50 4.2.3 STLport 50 4.2.4 P.J.Plauger STL 50 4.2.5 Rouge Wave STL 50 4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 ...
用c++stl实现的学生成绩管理系统,代码简单明了,易懂,且该代码是安全可靠的
Jni中C++和Java的参数传递如何使用JNI的一些基本方法和过程在网上多如牛毛,如果你对Jni不甚了解,不知道Jni是做什么的,如何建立一个基本的jni程序,或许可以参考下面下面这些文章:利用VC++6.0实现JNI的最简单的...
对C++基本概念和技术全面而且权威的阐述,对现代C++编程风格的强调,使本书成为C++初学者的最佳指南;对于中高级程序员,本书也是不可或缺的参考书。本书的前言阐述了 第4版和前一版的不同之处。 【目录信息】 第1...