I can accept failure, but I can't accept that I haven't struggled.
🎓 vector introduction
- vector is a sequence container that represents a dynamic array of transform sizes.
- Like arrays, vectors use continuous storage space to store elements. This means that you can use subscripts to access the elements of a vector, which is as efficient as an array. But unlike an array, its size can be changed dynamically, and its size will be automatically processed by the container.
- Essentially, vector uses dynamically allocated arrays to store its elements. When new elements are inserted, the array needs to be resized to increase storage space. This is done by allocating a new array and then moving all the elements to the array. In terms of time, this is a relatively expensive task, because the vector does not reallocate the size every time a new element is added to the container.
🎓 vector constructor
Here we write three constructors, the first of which is the default constructor. The usage is as follows: vector < type T > variable name v;
vector() //Default constructor
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{}
The second constructor is convenient for us to initialize a vector with n elements whose value is value. The default initialization value of value is 0. Its use method is as follows:
Vector < type > variable name v (number of elements, size, initialized value);
//n --- number of elements value --- the default initialization value, and the initial value is 0
vector(int n, const T& value = T()) //Constructor with default value
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{
assert(n > 0);
reserve(n);
while (n--)
{
*this->m_finish = value;
++this->m_finish;
}
}
The third constructor initializes our vector with an iterator interval as follows:
Vector < type > variable name v (start iterator begin, end iterator end);
Here, the iterator interval is an interval [begin, end] that is closed before and open after.
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{
reserve(last - first);
while (first != last)
{
*this->m_finish = (*first);
++first;
++this->m_finish;
}
}
🎓 copy constructor
Since vector has pointer variables inside, copy constructor and assignment operator overloaded functions need to be copied deeply. If shallow copy is performed, an error will occur. Here is the traditional way of writing our copy constructor.
I. first, let's new a piece of space on the heap, the size of which is x.size(), in order to store data.
Secondly, assign the element in x to this object.
III. last m_m_finish and M_ The end of storage pointer points to modify to the correct location.
vector(const vector<T>& x) //copy constructor
{
this->m_start = new T[x.capacity()];
//memcpy cannot be used because if it is a built-in type or a user-defined type with a pointer, a shallow copy error will occur
for (size_t i = 0; i < x.size(); ++i)
{
this->m_start[i] = x[i];
}
this->m_finish = this->m_start + x.size();
this->m_endofstorage = this->m_start + x.capacity();
}
The above code block says that memcpy cannot be used for copying. Why?
A: This is because memcpy only copies simple values, which is equivalent to the function of the default copy constructor. If you encounter the type of vector, it will cause the shallow copy of the same block of memory to be destructed many times, resulting in program crash. Because the internal implementation of string is a char * pointer. Memcpy copies the value of the original space, as shown in the animation below.
How can we solve this problem? In fact, it is very simple to use the for loop to call the assignment operator of string to overload the function, so as to avoid the problem of shallow copy.
🎓 Assignment operator overloaded function
In the above copy constructor, we have explained that we should prevent shallow copy corpus and self assignment, but we use a new way to write here.
Principle: Based on the temporary local object, it initializes it with the existing object, then calls the copy constructor, and the local vector object also releases the memory by calling the destructor after the function is out.
① First, create a temporary variable and let it call the copy constructor.
② Exchange this object with temporary object temp.
vector<T>& operator=(const vector<T>& x) //Assignment function overload
{
if (this != &x)
{
vector<T>temp(x);
this->swap(temp);
}
return *this;
}
🎓 Destructor
The destructor has nothing to say, but it still has to deal with some space that has been delete d and released again, causing the program to crash.
~vector() //Destructor
{
if (this->m_start != nullptr)
{
delete[] this->m_start;
this->m_start = this->m_endofstorage = this->m_finish = nullptr;
}
}
🎓 iterator
In C + +, there are more than 8 iterators, but the difference is not bad. Here, we only simulate the most commonly used begin (start iterator) and end (end iterator). begin() points to the first element and end() points to the next position of the last element. As shown in the figure below:
iterator begin() //Start iterator
{
return this->m_start;
}
iterator end() //End iterator
{
return this->m_finish;
}
const_iterator begin() const //Constant start iterator
{
return this->m_start;
}
const_iterator end() const //Constant end iterator
{
return this->m_finish;
}
Some people may say why write a function with the same name as a member variable decorated with const?
A: This is because if our vector object is a constant object, the object cannot call begin and end without const. Because constant objects can only call constant functions.
🎓 Capacity correlation function
✏️size
Function: it is used to obtain the number of elements.
Return value: size_ T (unsigned integer).
size_t size() const //Get the number of elements function
{
return this->m_finish - this->m_start;
}
✏️capacity
Function: it is used to obtain the size of capacity.
Return value: size_ T (unsigned integer).
size_t capacity() const //Get the capacity size function
{
return this->m_endofstorage - this->m_start;
}
In the above capacity() and size() functions, we use the pointer minus pointer method to get the number of elements. Here, the pointer minus pointer must be the same continuous memory space to use the pointer minus pointer method.
✏️empty
Function: used to obtain whether the container is empty.
Return value: bool.
bool empty() const //Judge whether it is empty
{
return this->m_start == this->m_finish;
}
✏️reserve
Function: reserve is used to reserve space
Rules:
1. When the new size is greater than the current capacity of the object, expand the capacity to new size.
2. Do nothing when the newsize is less than or equal to the current capacity of the object.
After expanding the capacity here, we need to copy the data in the original array to the created temporary space temp. The same as the copy constructor above, we can't use memcpy to copy, but use the for loop to call the assignment operator of string to overload the function, so as to avoid the problem of shallow copy.
//newsize --- the size of the capacity to be expanded
void reserve(const size_t newsize)
{
if (this->capacity() < newsize) //Judge whether it is greater than the current capacity value. If it is greater than the current capacity value, it needs to be expanded
{
T* temp = new T[newsize];
int size = this->size(); //This temporary traversal size stores the number of data before capacity expansion
//If you do not store size, the following M_ An error occurs when finish + this - > size()
//Because our size() uses this - > M_ finish - this->m_ From start
//Because we changed m first_ Address of start, M_ The address of finish has not been changed. What you subtract here is a new size()
//And size() may be a large number, and the subsequent insertion may cause null pointer access errors
if (this->m_start != nullptr)
{
//memcpy(temp, this->m_start, sizeof(T) * size);
//memcpy cannot be used because if it is a built-in type or a user-defined type with a pointer, a shallow copy error will occur
for (size_t i = 0; i < this->size(); ++i)
{
temp[i] = this->m_start[i];
}
delete[] this->m_start;
}
this->m_start = temp;
this->m_finish = this->m_start+size;
this->m_endofstorage = this->m_start + newsize;
}
}
✏️resize
Function: adjust the string size to n characters.
Rules:
1. If the newsize is smaller than the current size(), the current valid value will be shortened to its first newsize, and the elements after the newsize will be deleted.
2. If the newsize is larger than the current size() but smaller than our current capacity(), the current content is expanded to reach the size of n by inserting the required number of elements at the end. The default value of the inserted elements is 0.
3. If the newsize is greater than the current size() and our current capacity(), we need to insert the required number of elements at the end to expand the size of the current container after capacity expansion. The default value of the inserted elements is 0.
//Newsize --- specified size val --- if newsize is larger than our size, the following values are val, and the default value is 0
/*
There are three situations:
1,newsize<size()，At this point, we just need to put our significant bit M_ Change finish to m_start+newsize
2,newsize>size()&&newsize<capacity(),At this point, we just need to put M_ The newsize element after finish can be given the value val
3,newsize>size()&&newsize>capacity(),At this time, we need to expand the capacity. After expanding the capacity, put M_ The newsize element after finish can be given the value val
*/
void resize(const size_t newsize, const T &val = T())
{
if (this->size() < newsize)
{
if (newsize > capacity())
{
reserve(newsize);
}
while (this->m_finish < this->m_start + newsize)
{
*this->m_finish = val;
++this->m_finish;
}
}
else
{
this->m_finish = this->m_start + newsize;
}
}
🎓 Element access
✏️ front
Function: get the value of the first element.
Return value:
T& front()
{
assert(!this->empty());
return *(this->m_start);
}
const T& front()const
{
assert(!this->empty());
return *(this->m_start);
}
✏️ back
Function: get the value of the last element.
T& back()
{
assert(!this->empty());
return *(this->m_finish-1);
}
const T& back() const
{
assert(!this->empty());
return *(this->m_finish - 1);
}
✏️ at
Function: returns the reference to the element at position n in the vector.
T& at(const size_t& index)
{
assert(index < this->size());
return this->m_start[index];
}
T& at(const size_t& index) const
{
assert(index < this->size());
return this->m_start[index];
}
✏️ operator[]
Function: returns the reference to the element at position n in the vector.
const T& operator[](const size_t& index) //Overload operator [], to use like an array
{
assert(index < this->size());
return this->m_start[index];
}
const T& operator[](const size_t& index) const
{
assert(index < this->size());
return this->m_start[index];
}
🎓 Modify correlation function
✏️push_back
Function: insert an element at the end.
//Trailing val ---- the value to be inserted
void push_back(const T&val)
{
if (this->m_finish == this->m_endofstorage)
{
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(newCapacity);
}
*this->m_finish = val;
++this->m_finish;
}
✏️insert
There are many overloaded versions of insert. Here we only simulate the most commonly used one.
Function: insert an element at the specified position.
Return value: the iterator pointing to the first newly inserted element.
//Position --- insertion position, insertion range [m_start, m_finish] Val ------ value to be inserted, return value --- return the iterator position of the inserted val
iterator insert(iterator position, const T& val)
{
assert(this->m_start<=position&&position<=this->m_finish); //Determine whether the insertion position is wrong
if (this->m_finish == this->m_endofstorage) //Judge whether to expand capacity
{
size_t len = position - this->m_start; //Record the position we want to insert to prevent iterator failure after capacity expansion
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(newCapacity);
// Update position to solve the problem of position failure after capacity increase
position = this->m_start + len; //Get the corresponding position to be inserted after capacity expansion
}
iterator end = this->m_finish-1;
while (end>=position)
{
*(end + 1) = *end;
--end;
}
*position = val;
++this->m_finish;
return position; //Returns the iterator position of the inserted val
}
✏️pop_back
Function: delete trailing elements.
//Tail deletion
void pop_back()
{
assert(!this->empty());
--this->m_finish;
}
✏️erase
Function: delete the value of a given position or delete the value of a range.
Return value: an iterator pointing to the new iterator location of the element after the last element deleted by the function call. If the operation deletes the last element in the sequence, this is the end of the container.
//Position --- the return value of the position to be deleted --- delete the iterator of the element after the position
iterator erase(const iterator position)
{
assert(this->m_start <= position && position < this->m_finish); //Judge whether the deleted position is out of bounds
iterator end = const_cast<iterator>(position);
while (end < this->m_finish)
{
*end = *(end + 1);
++end;
}
--this->m_finish;
return position;
}
//first --- delete the starting position last --- the interval before closing and after opening of the deleted end position
iterator erase(iterator first, iterator last)
{
assert(first<last&&this->m_start <= first && last <= this->m_finish); //Judge whether the deleted position is out of bounds
iterator begin = first;
iterator end = last;
while (end < this->m_finish)
{
*begin = *last;
++begin;
++end;
}
this->m_finish =begin;
if (this->empty()) //If there is no data in the space, the content of the space is empty and cannot be accessed. The nullptr pointer is returned directly
{
return nullptr;
}
else
{
return first;
}
}
✏️clear
Function: delete all elements from the container so that the size of the container is 0.
void clear() //empty
{
this->m_finish = this->m_start;
}
✏️swap
Function: used to exchange two containers of the same type.
void swap(vector<T>& x) //Two vector exchange functions
{
std::swap(this->m_start, x.m_start);
std::swap(this->m_finish, x.m_finish);
std::swap(this->m_endofstorage, x.m_endofstorage);
}
The complete code is as follows:
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <assert.h>
#include<iostream>
using namespace std;
namespace ZJ
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
public:
vector() //Default constructor
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{}
//n --- number of elements value --- the default initialization value, and the initial value is 0
vector(int n, const T& value = T()) //Constructor with default value
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{
assert(n > 0);
reserve(n);
while (n--)
{
*this->m_finish = value;
++this->m_finish;
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:m_start(nullptr)
,m_finish(nullptr)
,m_endofstorage(nullptr)
{
reserve(last - first);
while (first != last)
{
*this->m_finish = (*first);
++first;
++this->m_finish;
}
}
vector(const vector<T>& x) //copy constructor
{
this->m_start = new T[x.capacity()];
//memcpy cannot be used because if it is a built-in type or a user-defined type with a pointer, a shallow copy error will occur
for (size_t i = 0; i < x.size(); ++i)
{
this->m_start[i] = x[i];
}
this->m_finish = this->m_start + x.size();
this->m_endofstorage = this->m_start + x.capacity();
}
vector<T>& operator=(const vector<T>& x) //Assignment function overload
{
if (this != &x)
{
vector<T>temp(x);
this->swap(temp);
}
return *this;
}
~vector() //Destructor
{
if (this->m_start != nullptr)
{
delete[] this->m_start;
this->m_start = this->m_endofstorage = this->m_finish = nullptr;
}
}
void swap(vector<T>& x) //Two vector exchange functions
{
std::swap(this->m_start, x.m_start);
std::swap(this->m_finish, x.m_finish);
std::swap(this->m_endofstorage, x.m_endofstorage);
}
size_t capacity() const //Get the capacity size function
{
return this->m_endofstorage - this->m_start;
}
size_t size() const //Get the number of elements function
{
return this->m_finish - this->m_start;
}
T& front()
{
assert(!this->empty());
return *(this->m_start);
}
const T& front()const
{
assert(!this->empty());
return *(this->m_start);
}
T& back()
{
assert(!this->empty());
return *(this->m_finish-1);
}
const T& back() const
{
assert(!this->empty());
return *(this->m_finish - 1);
}
iterator begin() //Start iterator
{
return this->m_start;
}
iterator end() //End iterator
{
return this->m_finish;
}
const_iterator begin() const //Constant start iterator
{
return this->m_start;
}
const_iterator end() const //Constant end iterator
{
return this->m_finish;
}
bool empty() const //Judge whether it is empty
{
return this->m_start == this->m_finish;
}
T& at(const size_t& index)
{
assert(index < this->size());
return this->m_start[index];
}
T& at(const size_t& index) const
{
assert(index < this->size());
return this->m_start[index];
}
const T& operator[](const size_t& index) //Overload operator [], to use like an array
{
assert(index < this->size());
return this->m_start[index];
}
const T& operator[](const size_t& index) const
{
assert(index < this->size());
return this->m_start[index];
}
//Trailing val ---- the value to be inserted
void push_back(const T&val)
{
if (this->m_finish == this->m_endofstorage)
{
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(newCapacity);
}
*this->m_finish = val;
++this->m_finish;
}
//Tail deletion
void pop_back()
{
assert(!this->empty());
--this->m_finish;
}
//newsize --- the size of the capacity to be expanded
void reserve(const size_t newsize)
{
if (this->capacity() < newsize) //Judge whether it is greater than the current capacity value. If it is greater than the current capacity value, it needs to be expanded
{
T* temp = new T[newsize];
int size = this->size(); //This temporary traversal size stores the number of data before capacity expansion
//If you do not store size, the following M_ An error occurs when finish + this - > size()
//Because our size() uses this - > M_ finish - this->m_ From start
//Because we changed m first_ Address of start, M_ The address of finish has not been changed. What you subtract here is a new size()
//And size() may be a large number, and the subsequent insertion may cause null pointer access errors
if (this->m_start != nullptr)
{
//memcpy(temp, this->m_start, sizeof(T) * size);
//memcpy cannot be used because if it is a built-in type or a user-defined type with a pointer, a shallow copy error will occur
for (size_t i = 0; i < this->size(); ++i)
{
temp[i] = this->m_start[i];
}
delete[] this->m_start;
}
this->m_start = temp;
this->m_finish = this->m_start+size;
this->m_endofstorage = this->m_start + newsize;
}
}
//Newsize --- specified size val --- if newsize is larger than our size, the following values are val, and the default value is 0
/*
There are three situations:
1,newsize<size()，At this point, we just need to put our significant bit M_ Change finish to m_start+newsize
2,newsize>size()&&newsize<capacity(),At this point, we just need to put M_ The newsize element after finish can be given the value val
3,newsize>size()&&newsize>capacity(),At this time, we need to expand the capacity. After expanding the capacity, put M_ The newsize element after finish can be given the value val
*/
void resize(const size_t newsize, const T &val = T())
{
if (this->size() < newsize)
{
if (newsize > capacity())
{
reserve(newsize);
}
while (this->m_finish < this->m_start + newsize)
{
*this->m_finish = val;
++this->m_finish;
}
}
else
{
this->m_finish = this->m_start + newsize;
}
}
//Position --- insertion position, insertion range [m_start, m_finish] Val ------ value to be inserted, return value --- return the iterator position of the inserted val
iterator insert(iterator position, const T& val)
{
assert(this->m_start<=position&&position<=this->m_finish); //Determine whether the insertion position is wrong
if (this->m_finish == this->m_endofstorage) //Judge whether to expand capacity
{
size_t len = position - this->m_start; //Record the position we want to insert to prevent iterator failure after capacity expansion
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(newCapacity);
// Update position to solve the problem of position failure after capacity increase
position = this->m_start + len; //Get the corresponding position to be inserted after capacity expansion
}
iterator end = this->m_finish-1;
while (end>=position)
{
*(end + 1) = *end;
--end;
}
*position = val;
++this->m_finish;
return position; //Returns the iterator position of the inserted val
}
//Position --- the return value of the position to be deleted --- delete the iterator of the element after the position
iterator erase(const iterator position)
{
assert(this->m_start <= position && position < this->m_finish); //Judge whether the deleted position is out of bounds
iterator end = const_cast<iterator>(position);
while (end < this->m_finish)
{
*end = *(end + 1);
++end;
}
--this->m_finish;
return position;
}
//first --- delete the starting position last --- the interval before closing and after opening of the deleted end position
iterator erase(iterator first, iterator last)
{
assert(first<last&&this->m_start <= first && last <= this->m_finish); //Judge whether the deleted position is out of bounds
iterator begin = first;
iterator end = last;
while (end < this->m_finish)
{
*begin = *last;
++begin;
++end;
}
this->m_finish =begin;
if (this->empty()) //If there is no data in the space, the content of the space is empty and cannot be accessed. The nullptr pointer is returned directly
{
return nullptr;
}
else
{
return first;
}
}
void clear() //empty
{
this->m_finish = this->m_start;
}
private:
iterator m_start;
iterator m_finish;
iterator m_endofstorage;
};
}
If there are any mistakes, please point them out. Thank you!!!
END...