做一个网站大概要多少钱,潍坊seo教程,手机wap网站制作,网络服务费交印花税吗文章目录 基本概念功能思路代码实现vector.htest.cpp 代码详解变量构造函数析构函数拷贝构造operatorpush_backoperator[]insertprintElements 本实现版本 和 C STL标准库实现版本的区别#xff1a; 基本概念
vector数据结构和数组非常相似#xff0c;也称为单端数组vector与… 文章目录 基本概念功能思路代码实现vector.htest.cpp 代码详解变量构造函数析构函数拷贝构造operatorpush_backoperator[]insertprintElements 本实现版本 和 C STL标准库实现版本的区别 基本概念
vector数据结构和数组非常相似也称为单端数组vector与普通数组区别 不同之处在于数组是静态空间而vector可以动态扩展动态扩展 并不是在原空间之后续接新空间而是找更大的内存空间然后将原数据拷贝新空间释放原空间
功能
设计一个 Vector 类该类应具备以下功能和特性
1、基础成员函数
构造函数初始化 Vector 实例析构函数清理资源确保无内存泄露拷贝构造函数允许通过现有的 MyVector 实例来创建一个新实例拷贝赋值操作符实现 MyVector 实例之间的赋值功能
2、核心功能
添加元素到末尾允许在 Vector 的末尾添加新元素获取元素个数返回 Vector 当前包含的元素数量获取容量返回 Vector 可以容纳的元素总数访问指定索引处的元素通过索引访问特定位置的元素在指定位置插入元素在 Vector 的特定位置插入一个新元素删除数组末尾元素移除 Vector 末尾的元素清空数组删除 Vector 中的所有元素重置其状态
3、遍历
遍历并打印数组元素提供一个函数通过迭代器遍历并打印出所有元素
4、高级特性
容器扩容当前容量不足以容纳更多元素时自动扩展 Vector 的容量以存储更多元素
思路
内存分配
当容量不足以容纳新元素时std::vector 会分配一块新的内存空间将原有元素复制到新的内存中然后释放原内存。这个过程确保了元素的连续存储。
动态扩容
当需要进行扩容时std::vector 通常会将容量翻倍以避免频繁的内存分配操作从而减少系统开销。
涉及以下步骤
分配一个更大的内存块通常是当前大小的两倍这个增长因子取决于实现。将当前所有元素移到新分配的内存中。销毁旧元素并释放旧内存块。插入新元素。 在上图中, 有一个vectorint v对象, 其成员变量存储在在了栈上, 包括size, capacity, data pointer,分别表示数组已经使用的大小、数组的容量、数组的首地址, 最左边表示初始时刻的堆栈状态,某时刻调用v.push_back(20), 检查发现此操作不会超出容量上限, 因此在中间的堆栈示意图中插入了20, 并更新控制结构中的size 2下一时刻调用v.push_back(30), 此时检查发现此操作要求的容量不足, 因此需要重新在堆内存申请容量为4的内存空间, 如右边的示意图所示, 并且复制原来的内容到新的地址, 完成此操作后可以丢弃原来的堆内存空间, 并插入30
代码实现
vector.h
#include iostream
#include algorithm
#include sstream
#include string
#include stdexceptnamespace mystl{
template typename T
class Vector
{
private:T *elements; size_t capacity; size_t size; public:Vector():elements(nullptr), capacity(0), size(0){};~Vector(){delete[] elements; }Vector(const Vector other):capacity(other.capacity),size(other.size){elements new T[capacity];std::copy(other.elements, other.elementssize, elements);}Vector operator(const Vector other) {if(this ! other) {delete[] elements; capacity other.capacity;size other.size;elements new T[capacity];std::copy(other.elements, other.elementssize, elements);}return *this; }void push_back(const T value){if(size capacity){reserve(capacity0? 1:2*capacity);}elements[size] value;}size_t getSize() const{return size;}size_t getCapacity() const{return capacity;}T operator[](size_t index){if(index size){throw std::out_of_range(Index out of range);}return elements[index];}void insert(size_t index, const T value){if(index size){throw std::out_of_range(Index out of range);}if(size capacity){reserve(capacity 0? 1:capacity*2);}for(size_t i size; iindex;--i) // TODO:为什么不是i--{elements[i] elements[i-1];}elements[index] value;size;}void pop_back(){if(size 0){--size; }}void clear(){size 0;}T* begin(){return elements;}T* end(){return elementssize;}const T* begin() const{return elements;}const T* end() const{return elementssize;}void printElements() const {for(size_t i 0; isize; i){std::cout elements[i] ;}std::cout std::endl;}private:void reserve(size_t newCapacity){if(newCapacity capacity){T* newElements new T[newCapacity];std::copy(elements,elementssize,newElements);delete[] elements;elements newElements;capacity newCapacity;}}};
}test.cpp
#include vector.h
#include list.h
#include deque.hvoid vectorTest()
{mystl::Vectorint v1;v1.push_back(10);mystl::Vectorint v2(v1);mystl::Vectorint v3 v2;for(int i 0; i 5; i){v3.push_back(i);}int size v3.getSize();int cap v3.getCapacity();int t v3[3];std::cout t std::endl;v3.insert(2,88);v3.pop_back();int* ptr v3.begin();v3.printElements();v3.clear();
}int main()
{vectorTest();system(pause);return 0;
}代码详解
变量
T *elements; // 指向动态数组的指针
size_t capacity; // 数组的容量, size_t unsigned int
size_t size; // 数组中元素的个数elements 指向动态数组的指针capacity数组的容量, size_t unsigned intsize 数组中元素的个数
构造函数
Vector():elements(nullptr), capacity(0), size(0){};构造函数初始化Vector对象默认设置指针悬空容量设置为0当前元素的数量也为0
析构函数 ~Vector(){delete[] elements; // elements是数组指针}析构函数销毁Vector对象释放指针
拷贝构造
Vector(const Vector other):capacity(other.capacity),size(other.size)
{// 找一块地方开辟地址空间elements new T[capacity];std::copy(other.elements, other.elementssize, elements);
}拷贝构造函数cap、size都默认和副本相同
std::copy()
作用从一个容器复制元素到另一个容器。std::copy需要三个参数两个指定要复制的元素范围的迭代器起始迭代器和结束迭代器以及一个指向目标位置开始的迭代器。 指针也是一种天然的迭代器
operator // 拷贝复制运算符重载Vector operator(const Vector other) {{delete[] elements; // 获取副本的数据capacity other.capacity;size other.size;elements new T[capacity];// 分配新内存并复制所有元素std::copy(other.elements, other.elementssize, elements);}return *this; }if(this ! other)通过判断两个指针是否相同检查是不是自赋值的情况delete[] elements;删除这一块地址的数据、指针return *this; 返回当前对象的引用
push_back // push_back函数void push_back(const T value){if(size capacity){reserve(capacity0? 1:2*capacity);}elements[size] value;}if(size capacity)如果内存将要溢出则开辟更大的空间reserve(capacity0? 1:2*capacity);不能简单的将capacity容量翻倍, 需要考虑0的边界情况如果是开始时刻没有分配内存则分配1块内存否则内存空间加倍
operator[]
下标操作符重载允许通过下标访问Vector中的元素
T operator[](size_t index)
{// 如果指定的下标越界大于或等于 size则抛出 std::out_of_range 异常if(index size){throw std::out_of_range(Index out of range);}return elements[index];
}当 int arr[] { 99, 15, 100, 888, 252 } 时arr是指向数组首地址的指针。可以采用 arr[i] 的形式访问数组元素。如果 p 是指向数组 arr 的指针那么也可以使用 p[i] 来访问数组元素它等价于 arr[i]。因此elements[index]等同于vector v[index]
insert void insert(size_t index, const T value)
{if(index size){throw std::out_of_range(Index out of range);}if(size capacity){reserve(capacity 0? 1:capacity*2);}// 后续元素后移for(size_t i size; iindex;--i){elements[i] elements[i-1];}elements[index] value;size;
}在 Vector 的指定位置 index 插入一个元素 value如果 index 大于 size则抛出 std::out_of_range 异常如果当前没有足够的容量来存储新元素则通过 reserve 函数扩展数组的容量将 index 之后的所有元素向后移动一个位置为新元素腾出空间将新元素放置在 index 位置增加 Vector 的 size
for(size_t i size; iindex;--i)
{elements[i] elements[i-1];
}for循环执行顺序如图 printElements
void printElements() const
{for(size_t i 0; isize; i){std::cout elements[i] ;}std::cout std::endl;
}const 关键字在成员函数声明之后表示该函数不会修改类的任何成员变量
本实现版本 和 C STL标准库实现版本的区别
内存分配策略不同、无范围检查和异常处理、只实现了一些基本的功能例如插入、删除、访问元素等而没有涵盖 std::vector 的所有功能和特性
