C++初阶(十四)--STL--vector的模拟实现

 

文章目录

一、vector的基本结构

二、默认成员函数的实现

1.构造函数

2.拷贝构造函数

3.赋值运算符重载

4. 析构函数

三、迭代器相关函数

 begin和end

四、容量和大小相关函数

size

capacity

reserve

resize

empty

五、修改容器的函数

push_back

pop_back

 insert

erase

swap

六、访问容器相关函数

operator[]

七、迭代器失效

1.迭代器失效的概念

2.列如我们的 vector容器

3.如何避免迭代器失效问题

---

一、vector的基本结构

首先定义一个vector模版类，其中三个成员变量均为迭代器，且此处vector的迭代器是一个原生指针，我们这里为其定义别名iterator。

namespace My_Vector
{template<class T>//此处为类模板，实现不同数据类型的存储class vector{public://vector迭代器为原生指针typedef T* iterator;//定义指针类型的别名iteratortypedef const T* const_iterator;//...函数接口的实现private:iterator _start;// 指向容器的开始iterator _finish;// 指向容器中最后一个有效数据的下一个位置iterator _endofstorage;  // 指向存储容量的结尾};
}

 

私有成员变量：

_start: 这是一个指针，指向容器的第一个元素。
_finish: 这个指针指向容器中最后一个有效数据的下一个位置。
_endofstorage: 这个指针指向分配给vector的内存块的末尾。这不是最后一个有效元素的位置，而是整个内存块的结束位置，在这之后可能会有额外的未初始化空间，预留以实现当vector增长时无需重新分配整个数组。

二、默认成员函数的实现

1.构造函数

构造函数1

vector首先支持一个无参的构造函数，对于这个无参的构造函数，我们直接将构造对象的三个成员变量都设置为空指针即可。

vector()//初始化列表构造:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}

构造函数2

其次，vector还支持使用一段迭代器区间进行对象的构造。因为该迭代器区间可以是其他容器的迭代器区间，也就是说该函数接收到的迭代器的类型是不确定的，这个类型也有可能是一个类，所以我们这里需要将该构造函数设计为一个函数模板，在函数体内将该迭代器区间的数据一个个尾插到容器当中即可。

	//构造函数3
// 类模板的成员函数，也可以是一个函数模板template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last)//左闭右开{push_back(*first);++first;}}

构造函数3

此外，vector还支持构造这样一种容器，该容器当中含有n个值为val的数据。对于该构造函数，我们可以先使用reserve函数将容器容量先设置为n，然后使用push_back函数尾插n个值为val的数据到容器当中即可。

vector(size_t n, const T& val)
{reseve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

 注意：
1）该构造函数知道其需要用于存储n个数据的空间，所以最好用reserve函数一次性开辟好空间，避免调用push_back函数时需要增容多次，导致效率降低。
2）该构造函数还需要实现两个重载函数。否则调用该构造函数的时候可能会出现一些问题。

vector(int n, const T& val)
{reseve(n);for (int i = 0; i < n; i++){push_back(val);}
}
vector(long n, const T& val)
{reseve(n);for (long i = 0; i < n; i++){push_back(val);}
}

可以看到，这两个重载函数与之不同的就是其参数n的类型不同，但这却是必要的，否则当我们使用以下代码时，编译器会优先与构造函数2相匹配。

vector<int> v(5, 7); //调用构造函数3 ？？？

构造函数4

 vecotrh还支持使用initializer_list<T>构造，initializer_list是一个类，支持{}初始化。这个是在C++11中新增的。

实现过程和构造函数3类似。

	vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}

2.拷贝构造函数

拷贝构造函数的写法也比较简单，使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来即可。

		vector(vector<T>& v){reserve(v.capacity);for (auto e : v){pushu_back(e);}}

 

 3.赋值运算符重载

这里的写法较为巧妙，可以参考前面的string模拟，首先在右值传参时并没有使用引用传参，因为这样可以间接调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。

vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

4. 析构函数

对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针即可。

~vector()
{if (_start)//避免对空指针释放{delete[] _start;_start = nullptr;_finish = nullptr;_endofstorage = nullptr;}
}

三、迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

//vector迭代器为原生指针
typedef T* iterator;//定义指针类型的别名iterator
typedef const T* const_iterator;

 begin和end

begin返回容器当中的首地址，end返回容器当中有效数据的下一个数据的地址

//可修改
iterator begin() 
{return _start;//返回首地址
}
iterator end()
{return _finish;//返回容器当中有效数据的下一个数据的地址
}
//不可修改

再重载一对适用于const的begin和end,使得const对象调用begin和end时只能对数据进行读而不能进行修改。

//不可修改
const_iterator begin() const
{return _start;//返回首地址
}
const_iterator end() const
{return _finish;//返回容器当中有效数据的下一个数据的地址
}

 四、容量和大小相关函数

size

两个指针相减的结果，就是这两个指针之间对应类型的数据个数，所以size可以由_finish - _start得到

szie_t size()
{return _finish-_start;
}

capacity

capacity可以由_endofstorage - _start得到。

size_t capacity()
{return _endofstorage - _start;
}

reserve

reserve规则：
 1、当n大于对象当前的capacity时，将capacity扩大到n或大于n。
 2、当n小于对象当前的capacity时，什么也不做。

reserve函数的实现思路也是很简单的，先判断所给n是否大于当前容器的最大容量（否则无需进行任何操作），操作时直接开辟一块可以容纳n个数据的空间，然后将原容器当中的有效数据拷贝到该空间，之后将原容器存储数据的空间释放，并将新开辟的空间交给该容器维护，最好更新容器当中各个成员变量的值即可。

void reserve(size_t n)
{if (n > capacity()){size_t OldSize = size();T* tmp = new T[n];if (_start){// memcpy(tmp, _start, sizeof(T) * oldSize);for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete _start;}_start = tmp;_finish = _start + OldSize;_endofstorage = _start + n;}
}

在reserve函数的实现当中有两个地方需要注意：
1）在进行操作之前需要提前记录当前容器当中有效数据的个数。
因为我们最后需要更新_finish指针的指向，而_finish指针的指向就等于_start指针加容器当中有效数据的个数，当_start指针的指向改变后我们再调用size函数通过_finish - _start计算出的有效数据的个数就是一个随机值了。

2）拷贝容器当中的数据时，不能使用memcpy函数进行拷贝。
可能你会想，当vector当中存储的是string的时候，虽然使用memcpy函数reserve出来的容器与原容器当中每个对应的string成员都指向同一个字符串空间，但是原容器存储数据的空间不是已经被释放了，相当于现在只有一个容器维护这这些字符串空间，这还有什么影响。
但是不要忘了，当你释放原容器空间的时候，原容器当中存储的每个string在释放时会调用string的析构函数，将其指向的字符串也进行释放，所以使用memcpy函数reserve出来的容器当中的每一个string所指向的字符串实际上是一块已经被释放的空间，访问该容器时就是对内存空间进行非法访问。

所以说我们还是得用for循环将容器当中的string一个个赋值过来，因为这样能够间接调用string的赋值运算符重载，实现string的深拷贝。 

resize

resize规则：
 1、当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
 2、当n小于当前的size时，将size缩小到n。

根据resize函数的规则，进入函数我们可以先判断所给n是否小于容器当前的size，若小于，则通过改变_finish的指向，直接将容器的size缩小到n即可，否则先判断该容器是否需要增容，然后再将扩大的数据赋值为val即可。

void resize(const T& n,const T& val = T())
{if(size()>=n){_finish = _start + n;}else{reserve(n);while (_finish <_start + n){*_finish = val;_finish++;}}
}

empty

empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。

bool empty() const
{return _finish == _start;
}

五、修改容器的函数

push_back

这里是老套路，插入数据先考虑要不要扩容，若已满，则扩容，然后将数据放到_finish指向的位置，_finish再往后移。

void push_back(const T& x)
{if (size() == capacity()){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;
}

pop_back

这里做一下判空处理

//尾删数据
void pop_back()
{assert(!empty()); //容器为空则断言_finish--; //_finish指针前移
}

 insert

insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。

 注意： 若需要增容，则需要在增容前记录pos与_start之间的间隔，然后通过该间隔确定在增容后的容器当中pos的指向，否则pos还指向原来被释放的空间。

iterator insert(iterator pos, const T& val)
{assert(pos <= _finish && pos <= _start);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//这个时候的_start已经改变，pos的对应位置也应该改变pos = _start + len;}iterator end = _finish;while (end > pos){*end = *(end - 1);end--;}*pos = val;_finish++;return pos;
}

这里我们给了返回值，涉及到迭代器失效问题，会在后面讲到，往下翻。

erase

erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器是否为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可。

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;++i;}_finish--;return pos;
}

swap

swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

void swap(vector<T> v)
{std::swap(_start, v._start);std::swap(_start, v._finish);std::swap(_endofstorage, v._endofstorage);
}

六、访问容器相关函数

operator[]

vector也是支持下标访问的。

T& operator[](size_t i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

七、迭代器失效

      1.迭代器失效的概念

• 在 C++ 中，迭代器是一种用于遍历容器（如vector、list、map等）中元素的对象。迭代器失效是指当容器的内部结构发生改变时，原来指向容器中元素的迭代器可能不再有效，使用这些失效的迭代器可能会导致程序出现未定义行为，如程序崩溃、错误的结果等。

     2.列如我们的 vector容器

• 插入操作导致的失效：
  • 当在vector中插入元素时，如果插入操作导致了容器的内存重新分配，那么所有指向该容器的迭代器都会失效。这是因为vector的存储结构是连续的内存空间，当元素数量增加到超过当前容量时，vector会重新分配一块更大的内存空间来存储元素，并将原来的元素复制（或移动）到新的内存空间中。
  • 例如，在一个vector<int> v中，如果v.capacity() < v.size() + n（n为要插入元素的数量），就会发生内存重新分配。假设vector原来有一些迭代器指向其中的元素，在重新分配内存后，这些迭代器所指向的原来的内存地址已经不再是vector元素的有效地址了。
  • 不过，如果插入操作没有导致内存重新分配，那么只有指向插入位置及之后元素的迭代器会失效。这是因为插入元素后，插入位置之后的元素会向后移动，原来指向这些元素的迭代器就不再指向正确的元素了。
• 删除操作导致的失效：
  • 当从vector中删除元素时，指向被删除元素的迭代器会立即失效。而且，指向被删除元素之后元素的迭代器也可能失效，因为删除元素后，后面的元素会向前移动，这些迭代器可能不再指向正确的元素

     3.如何避免迭代器失效问题

        方法一：及时更新迭代器

• 在进行可能导致迭代器失效的容器操作后，及时重新获取有效的迭代器。例如，在vector中插入元素后，如果担心迭代器失效，可以在插入操作后重新定位迭代器。假设it是一个指向vector元素的迭代器，在插入元素后，可以通过it = v.insert(it, value);（v是vector容器，value是要插入的值）来插入元素并更新迭代器it，这样it就会指向新插入的元素，之后可以继续安全地使用这个迭代器进行遍历等操作。

        方法二：使用返回值更新迭代器

        我们这里使用的是这个方法

• 很多容器的插入和删除操作会返回有用的信息，比如vector的erase操作会返回一个迭代器，指向被删除元素之后的元素。可以利用这个返回值来更新迭代器，避免使用已经失效的迭代器。例如，it = v.erase(it);，这里v是vector容器，it是指向要删除元素的迭代器，执行erase操作后，it就被更新为指向被删除元素之后的元素，这样可以继续安全地使用it进行后续操作。

 我们只有深入了解不同容器的内部结构和操作对迭代器的影响，才能真正有效的避免这个问题，比如，当使用vector时，要特别注意插入和删除操作可能导致的迭代器失效情况；而在使用list时，就可以相对放心地进行插入和删除操作，只要正确处理被操作元素的迭代器即可。对于map和unordered_map，在大多数情况下，迭代器失效的情况相对较少，但也要注意特殊情况。

---

 本篇博客到此结束，欢迎各位评论区留言~