C++模拟实现vector的示例代码

　　一、迭代器

　　定义

　　vector类型的迭代器就是原生态的指针，对T*进行重命名即可

　　typedef T* iterator;

　　typedef const T* const_iterator;

　　普通迭代器

　　iterator begin()

　　{

　　return start;

　　}

　　iterator end()

　　{

　　return finish;

　　}

　　const类型迭代器

　　const类型迭代器可以访问const成员变量

　　const iterator cbegin()const

　　{

　　return start;

　　}

　　const iterator cend()const

　　{

　　return finish;

　　}

　　二、构造类

　　构造函数

　　构造空对象

　　在初始化列表中对三个成员变量进行初始化

　　vector()

　　:start(nullptr)

　　, finish(nullptr)

　　, endOfStorage(nullptr)

　　{}

　　n个T类型

　　开辟空间以后，对finish进行自增，在空间填充元素

　　vector(size_t n, const T& value = T())

　　:start(new T[n])

　　, finish(start)

　　, endOfStorage(start + n)

　　{

　　for (int i = 0; i < n; i++)

　　{

　　*finish++ = value;

　　}

　　重载前一个构造函数，将第一个参数设置为int类型

　　vector(int n, const T& value = T())

　　:start(new T[n])

　　, finish(start)

　　, endOfStorage(start + n)

　　{

　　for (int i = 0; i < n; i++)

　　{

　　*finish++ = value;

　　}

　　之所以要对这种类型的构造函数进行重载，是因为在调用构造函数时，如果实参传两个整型数字，编译器会默认为int类型数据，进行推演之后与前面的size_t类型不匹配，则会调用下面的区间构造的方法，导致程序报错，如图：

　　迭代器构造

　　将构造方法中迭代器的类型写成模板类型，这样便可以接收其它类型的迭代器，如：T类型为char，Iterator迭代器为string类型，便可以从字符串中截取字符，构造vector类型的对象。

　　//写成函数模板，可以接受任意类型的迭代器

　　template

　　vector(Iterator first, Iterator last)

　　{

　　size_t n = ZH::distance(first, last);//获取长度

　　start = new T[n];

　　finish = start;

　　endOfStorage = start + n;

　　while (first != last){

　　*finish = *first;

　　first++;

　　finish++;//完成赋值的同时也移动了finish的位置

　　}

　　将distance方法写到另一个.hpp头文件中

　　template

　　//此处的Iterator是模板参数，表示可以传任意类型的迭代器

　　size_t distance(Iterator first, Iterator last)

　　{

　　//获取元素个数，暂时只考虑底层空间连续的情况

　　int count = 0;

　　while (first != last)

　　{

　　first++;

　　count++;

　　}

　　return count;

　　}

　　拷贝构造函数

　　拷贝构造函数的形参必须是const类对象的引用，必须使用const类型的迭代器才能访问，复用迭代器构造的方法定义一个临时变量temp，交换temp与当前对象

　　//此处拷贝构造函数的形参是const类型

　　vector(const vector& v)

　　:start(nullptr)

　　, finish(nullptr)

　　, endOfStorage(nullptr)

　　{

　　//▲用const类型的迭代器访问const变量

　　vector temp(v.cbegin(), v.cend());

　　this->swap(temp);

　　}

　　赋值运算符重载

　　形参设置为类类型对象，调用赋值运算符重载函数时，形参会拷贝实参，交换当前对象与形参的值。

　　vector& operator=(const vector v)

　　{

　　this->swap(v);

　　return *this;

　　}

　　析构函数

　　释放空间，将三个迭代器赋值为空

　　~vector()

　　{

　　delete[]start;

　　start = nullptr;

　　finish = nullptr;

　　endOfStorage = nullptr;

　　}

　　三、容量相关操作

　　size、capacity

　　size_t size()

　　{

　　return finish - start;

　　}

　　size_t capacity()

　　{

　　return endOfStorage - start;

　　}

　　empty

　　判断fiinsh与start是否相等即可，相等则为空

　　size_t empty()

　　{

　　return finish == start;

　　}

　　resize

　　定义一个变量保存旧的size的值‘判断是减小还是增加size；判断是否需要扩容，需要则调用reserve函数，从旧空间的结束位置开始，给新增加的空间填充元素；最后改变finish的值。

　　void resize(size_t newsize, const T& value = T())

　　{

　　size_t oldsize = size();

　　if (newsize > oldsize){

　　if (newsize > capacity()){

　　reserve(newsize);

　　}

　　for (size_t i = oldsize; i < newsize; i++)

　　{

　　start[i] = value;

　　}

　　finish = start + newsize;//不用考虑增加或减小

　　}

　　reserve

　　reserve的步骤：申请新空间，拷贝旧空间的元素，释放旧的空间。

　　void reserve(size_t newcapacity)

　　{

　　size_t oldcapacity = capacity();

　　if (newcapacity > oldcapacity)

　　{

　　size_t n = size();//保存size()的值

　　T* temp = new T[newcapacity];

　　//start不为空时才进行拷贝旧空间元素和释放的操作

　　if (start)

　　{

　　//memcpy浅拷贝，当vector中存放的对象内部设计资源管理

　　// 会有内存泄漏和野指针问题

　　//memcpy(temp, start, sizeof(T) * n);

　　for (size_t i = 0; i < n; i++)

　　{

　　temp[i] = start[i];//调用赋值运算符重载

　　}

　　delete[] start;

　　}

　　start = temp;

　　//▲此处不能用satart+size(),因为size方法中有finish-start,而start值已经改变

　　finish = start + n;

　　endOfStorage = start + newcapacity;

　　}

　　易错点：

　　判断start的值是否为空，如果原来的start为空，则不需要再拷贝元素和释放

　　浅拷贝问题

　　finish更新问题

　　size()的方法内部finish-start，而此时start已经发生改变，finish还是旧的，所以要提前定义一个临时变量保存size()的值

　　三、元素访问

　　[ ]重载

　　重载成普通类型和const类型，const类型可以访问const成员

　　T& operator[](size_t index)

　　{

　　assert(index < size());

　　return start[index];

　　}

　　const T& operator[](size_t index)const

　　{

　　assert(index < size());

　　return start[index];

　　}

　　front

　　返回动态数组第一个元素

　　T& front()

　　{

　　return start[0];

　　}

　　const T& front()const

　　{

　　return start[0];

　　}

　　back

　　返回最后一个位置前一个元素

　　T& back()

　　{

　　return *(finish - 1);

　　}

　　const T& back()const

　　{

　　return *(finish - 1);

　　}

　　四、修改类接口

　　push_back

　　插入前先判断空间是否已满，空间若满则进行扩容，扩容时，要原来的空间容量为0的情况；将value放置到末尾位置，并将finish向后移动一个单位

　　void push_back(const T& value)

　　{

　　if (finish == endOfStorage)

　　{

　　//因为原来的capacity可能为0,所以要+3

　　reserve(capacity() * 2 + 3);

　　}

　　*finish++ = value;

　　}

　　pop_back

　　尾删，先判断对象是否为空，若不为空则将finish位置前移一个单位

　　void pop_back()

　　{

　　if (empty())

　　{

　　return;

　　}

　　finish--;

　　}

　　insert

　　任意位置插入，insert的返回值为新插入的第一个元素位置的迭代器；因为插入可能会进行扩容，导致start的值改变，所以先定义一个变量保存pos与start的相对位置；判断是否需要扩容；从插入位置开始，将所有元素向后搬移一个位置；将pos位置的值置为要插入的值；更新finish的值。

　　//第二个参数用const修饰，常量引用

　　//不用const修饰则为非常量引用

　　iterator insert(iterator pos, const T& value)

　　{

　　int index = pos - start;

　　assert(pos >= start && pos < finish);

　　//判断空间是否足够

　　if (finish == endOfStorage)

　　{

　　reserve(capacity() * 2);

　　}

　　pos = start + index;

　　for (auto it = finish; it > pos; it--)

　　{

　　*it = *(it - 1);

　　}

　　*pos = value;

　　finish++;

　　return pos;

　　}

　　erase

　　判断下标合法性；从pos位置下一个位置开始，将所有元素向前搬移一个位置；更新finish的值

　　iterator erase(iterator pos)

　　{

　　assert(pos >= start && pos < finish);

　　auto it = pos;

　　while (it < finish - 1)

　　{

　　*it = *(it + 1);

　　it++;

　　}

　　finish--;

　　return pos;

　　}

　　clear

　　清空所有元素，令finish=start即可

　　void clear()

　　{

　　finish = start;

　　}

　　swap

　　vector内置的swap函数，调用标准库中的swap交换vector的三个成员变量的值

　　void swap(vector& v)

　　{

　　std::swap(start, v.start);

　　std::swap(finish, v.finish);

　　std::swap(endOfStorage, v.endOfStorage);

　　}

　　五、成员变量

　　private:

　　iterator start;

　　iterator finish;

　　iterator endOfStorage;

　　vector内部有三个成员变量，start表示起始位置，finish表示有效元素的末尾位置，endOfStorage表示空间的末尾位置；通过这三个成员变量可以得到size和capacity等值，如图：

　　以上就是C++模拟实现vector的示例代码的详细内容，更多关于C++ vector的资料请关注脚本之家其它相关文章！

　　您可能感兴趣的文章:

您可能感兴趣的文章:

C++模拟实现vector的示例代码

相关文章

大家感兴趣的内容

最近更新的内容