一、容器vector
vector类模板提供了一种占用连续内存地址的数据结构。这使得它可以高效,直接的利用下标运算符[]访问vector中的任一元素,当一个vecto的内存空间耗尽时,它会分配一个更大的连续空间(数组),把原先的数据复制(或移动)到新的空间(数组),并把原来的空间(数组)释放。
其中的#0,#1…就是容器内的元素。从上图可以看出vector维护的是一个连续的线性空间,和数组是一样的。所以不论其元素为何种型别,普通指针就可以作为vector的迭代器!因为vector迭代器所需要的操作如operator*,operator->,operator++,operator+,operator-,operator+=,operator-=,普通指针天生就具备。查看vector的源码,我们可以看到vector的迭代器并没有另外定义为一个模版类,而是直接 typedef value_type* iterator。 更可以看出 vector 的迭代器就是一个普通指针。
实现vector容器的类名为vector,包含类vector的头文件是,并且命名空间为std
二、迭代器Iterator
一个标准化遍历各类容器里面的所有对象的方法类(典型的设计模式),把访问逻辑从不同类型的集合类中抽象出来,从而避免向客户端暴露集合的内部结构
三、实现的功能
1.创建vector对象
定义了一个存储Vector类型的对象iterator
typedef Iterator<Vector<T>> iterator; //类类型的重定义
用构造函数创建对象
Vector()
{
mdata = new T[2];
cursize = 0;
totalsize = 2;
}
2.vector对象不等关系的比较
bool operator!=(const Iterator<Container>& rhs)
{
return mpos != rhs.mpos;
}
3.使用指针输出数组
数组中的指针可视为迭代器,函数begin返回指向数组第一个元素的迭代器,函数end返回数组末端最后一位的迭代器
//返回数组第一个元素的迭代器
iterator begin()
{
return iterator(this, 0);
}
//返回数组末端最后一位的迭代器
iterator end()
{
return iterator(this, cursize);
}
4.使用运算符[]访问和修改vector元素的下标
char& operator[](int index)
{
return mpstr[index];
}
5.一个vector对象用另外一个vector对象初始化
String(char* pstr) :mpstr(new char[strlen(pstr) + 1]())
{
strcpy(mpstr, pstr);
}
6.vector的成员函数 push_back:尾插入元素,如果在已满的vector插入元素,vevtor会扩容
void push_back(T val)
{
if (IsFull())
{
resize();
}
mdata[cursize++] = val;
}
7.扩容
void resize()
{
T* pnewspace = new T[totalsize * 2];
memcpy(pnewspace, mdata, sizeof(T)*totalsize);
delete[]mdata;
mdata = pnewspace;
totalsize *= 2;
}
7.vector的成员函数 pop_back:尾删除元素,若访问一个无效的下标或无效的实参,抛出异常 throw exception
void pop_back()
{
if (IsEmpty())
{
throw exception("vector is empty !");
}
cursize--;
}