🌟 Initial structure
_ start: point to the first element
_ Find: points to the next position of the last element
_ End of storage: the next location of the last in the space
namespace gpy
{
template <class T>
class vecrot
{
public:
typedef T* iterator;
~vector()
{
delete[] _start;
_start = _finsh = _endofstorage = nullptr;
}
private:
iterator _start;
iterator _finsh;
iterator _endofstorage;
};
}
🌟 Constructor
Here we implement a simple parameterless constructor
vector()
:_start(nullptr)
, _finsh(nullptr)
, _endofstorage(nullptr)
{}
🌟 copy construction
//copy construction
vector(const vector<T>& v)
:_start(nullptr)
, _finsh(nullptr)
, _endofstorage(nullptr)
{
//Open the space in advance and insert the data tail
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
🌟 assignment
//assignment
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
🌟 Capacity related operations
✨reserve
When we do not have enough space to insert data, we can call reserve. If we know how much space we need, it will be convenient to use reserve in advance.
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//Open a new space
size_t sz = size();//Record the size of the old space
if (_start)//_ If start is empty, only space is opened
{
memcpy(tmp, _start, sizeof(T)*sz);//Copy data from old space to new space
//Free up old space
delete[] _start;
}
//Update new space
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}
✨resize
resize changes the size, which is the same as string.
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//Open a new space
size_t sz = size();//Record the size of the old space
if (_start)//_ If start is empty, only space is opened
{
memcpy(tmp, _start, sizeof(T)*sz);//Copy data from old space to new space
//Free up old space
delete[] _start;
}
//Update new space
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}
💫size
Get the number of data, that is, find start
size_t size()const//Let const objects also be used
{
return _finsh - _start;
}
💫capacity
Get the capacity size, which is the same as size
size_t capacity()const//Let const objects also be used
{
return _endofstorage - _start;
}
🌟 iterator
//iterator
iterator begin()
{
return _start;
}
iterator end()
{
return _finsh;
}
//const object usage
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finsh;
}
🌟 Add, delete, check and modify
✨push_back
//Tail insertion
void push_back(const T& x)
{
//if (_finsh == _endofstorage)
//{
// //For capacity increase, consider the case where capacity is 0
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
insert data
//*_finsh = x;
//++_finsh;
//Once the insert is implemented, it can be reused
insert(_finsh,x);
}
✨pop_back
//Tail deletion
void pop_back()
{
assert(!empty());//Can only be deleted if it is not empty
--_finsh;
}
✨operator[]
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
✨ Iterator failure problem
💥 Let's first talk about an iterator failure problem, which is similar to the wild pointer problem. It can be directly applied to the code
std::vector<int> v2;
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(5);
std::vector<int> ::iterator pos = find(v2.begin(),v2.end(),3);
if (pos != v2.end())
{
v2.insert(pos, 30);
}
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
*pos = 100;
At this time, the code has reported an error. Why?
💥 After the capacity expansion, the original space will be released. At this time, the pos becomes a wild pointer, and an error will be reported in the dereference program. If the capacity expansion is in place, we also think it is invalid, because the meaning has changed. I originally pointed to 2 and now pointed to 20
💥 Erase will also cause the problem of iterator failure. Although erase does not cause the problem of wild pointer, the meaning changes. At this time, we will return a new iterator
✨insert
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finsh);//Ensure the effectiveness of pos
if (_finsh == _endofstorage)
{
size_t n = pos - _start;//Record the location of the original pos
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + n;
}
//Start moving data
iterator end = _finsh - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finsh;
return pos;
}
✨erase
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finsh);
iterator it = pos + 1;
while (it != _finsh)
{
*(it - 1) = *it;
++it;
}
--_finsh;
return pos;
}
The problematic code above needs to receive a pos.
std::vector<int> v2;
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(5);
std::vector<int> ::iterator pos = find(v2.begin(),v2.end(),3);
if (pos != v2.end())
{
pos = v2.insert(pos, 30);
}
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
*pos = 100;
At this point, the code can run.
🌟 memcpy shallow copy problem of reserve
vector<string> v;
v.reserve(2);
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
Each vector stores a string, and the string will open space on the heap. When deleting the old space, the destructor of the string will release the original space, and the space pointed to by the new copy will be released. When the vector calls the destructor, it will release the space just now,
The same space will be released twice.
Correct writing:
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//Open a new space
size_t sz = size();//Record the size of the old space
if (_start)//_ If start is empty, only space is opened
{
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
//Update new space
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}