Vector
Vector is also one of the six components of STL. In short, it is a sequential container that encapsulates dynamic size arrays. At the same time, it can store various objects, such as int, char, string types and so on
Because it is essentially a sequential container, it is stored in a sequential manner, similar to an array, and it can store dynamically, that is, the container can be inserted, deleted and changed in size
Class member
private: iterator _start; iterator _last; iterator _endofstorage;
_ start is the header pointer_ last is the tail pointer_ End of storage is the maximum location (container size) that can be stored
ps: iterator iterator pointer is behind
Constructor, copy constructor and destructor
vector()
:_start(nullptr)//Null pointer
,_last(nullptr)
,_endofstorage(nullptr)
{}
template <class InputIterator>
vector(InputIterator first, InputIterator last)//This constructor allows other containers
: _start(nullptr) //It can be stored in the vector container
, _last(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);//Insert one by one
++first;
}
}
// v2(v1), traditional writing
vector(const vector<T>& v)
:_start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)//You can directly insert the range for into v2 one by one without reopening the vector object of tmp as in modern writing
{
push_back(e);
}
}
~vector()
{
delete[] _start;//Remember to add []
_last = nullptr;
_start = nullptr;
_endofstorage = nullptr;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_last, v._last);
std::swap(_endofstorage, v._endofstorage);
}
//Modern writing v1=v2
vector<T>& operator=(vector<T> v)//There is no need to use references here, that is, a new space will be opened up when creating v
{
swap(v);//At this time, you can directly call the swao function, and v is the formal parameter. After swap, you can obtain the original data of this. At the end of the function, v is released together with the original data of this
return *this;
}
Deep copy is also performed in the Vector container
I don't have the traditional writing method of = or the modern writing method of (). Interested friends can learn about it by themselves
iterator
Templates are used here so that vector s can pass in various types of data
typedef T* iterator;//The contents of the object can be read and written
typedef const T* const_iterator;//The contents of the object can only be read
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _last;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _last;
}
Here, like String iterators, their essence is pointers, but for other containers, their essence is not pointers. I will explain later when writing to the list container, but remember that iterators are used to make our operations on containers look like pointers
Function function
size_t size()//Object size
{
return _last - _start;
}
size_t capacity()//Object capacity
{
return _endofstorage - _start;
}
bool empty()//Is it empty
{
return _start == _last;
}
void reserve(size_t n)//Open space
{
if (n > size())
{
size_t sz = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * sz);
_start = tmp;
_last = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n,const T& val=T())
{
if (n <= size())
{
_last = _start + n;//Is to reduce the size, not expand
}
else
{
if (n > capacity())
{
reserve(n);
}
while(_last<_start+n)//It doesn't have to be equal to because_ Last is the last bit pointing to a valid character
{
*_last= val;
_last++;
}
}
}
T& operator[](size_t n)//Can be used like arrays
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}
void Push_back(const T& x)
{
/*if (_last==_endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_last = x;
++_last;*/
insert(end(), x);
}
void Pop_back()
{
assert(!empty());
--_last;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _last);
if (_last == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}//This sentence is to improve reusability and can be used directly to Push_back for reuse
//size_t len = pos - _start;
//iterator end = _last + 1;
//if (_last == _endofstorage)
//{
// reserve(capacity() + 1);
//}
//pos = _start + len;// Note: after reopening the space, POS also becomes a wild pointer; So we need to get it back
//end = _last;// Note: end must be written once after the if statement, because the reserve function will reopen the space, otherwise end will become a wild pointer
iterator end = _last;
while (end >= pos)
{
*end = *(end - 1);//Note -- end cannot be used here because the previous end will also be changed
--end;
}
*pos = x;
++_last;
return pos;//In order to give the user the ability to reuse the original pointed number and avoid the situation of wild pointer
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _last);
iterator end = pos + 1;
while (end < _last)
{
*(end - 1) = *end;//Note -- end cannot be used here because the previous end will also be changed
++end;
}
--_last;
return pos;//Similarly, in order to avoid the problem of wild pointer, give the user a return value, which is the next value after the deleted element
}
The function of vector is roughly the same as that of string. It is worth noting that after using the insert and erase functions in vector, the original iterator is useless and becomes a wild pointer. This is because when the vector object is inserted, if the space is insufficient, it will reopen a new space, and the iterator points to the pointer of the original space, so it cannot be used. But what if there's enough space and you don't need to open space? The iterator still points to a valid space, but the value pointed to by the iterator is not our original value, because the data in that space has been moved and changed. At this time, we still regard it as a wild pointer. Therefore, for the insert and erase functions, we will give a returned iterator to the user for use. Insert is the inserted data, and erase is the next value of the deleted data
as
vector<int> v; v.Push_back(1); v.Push_back(2); v.Push_back(3); v.Push_back(4); vector<int>::iterator it = v.begin(); it = v.insert(it+1 , 9); cout << *it << " "; cout << endl;
Complete code
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _last;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _last;
}
vector()
:_start(nullptr)
,_last(nullptr)
,_endofstorage(nullptr)
{}
template <class InputIterator>
vector(InputIterator first, InputIterator last)//This constructor allows other containers with head and tail iterators to be stored in the vector container
: _start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// v2(v1), traditional writing
vector(const vector<T>& v)
:_start(nullptr)
, _last(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)//You can directly insert the range for into v2 one by one without reopening the vector object of tmp as in modern writing
{
push_back(e);
}
}
~vector()
{
delete[] _start;
_last = nullptr;
_start = nullptr;
_endofstorage = nullptr;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_last, v._last);
std::swap(_endofstorage, v._endofstorage);
}
//Modern writing v1=v2
vector<T>& operator=(vector<T> v)//There is no need to use references here, that is, a new space will be opened up when creating v
{
swap(v);//At this time, you can directly call the swao function, and v is the formal parameter. After swap, you can obtain the original data of this. At the end of the function, v is released together with the original data of this
return *this;
}
size_t size()
{
return _last - _start;
}
size_t capacity()
{
return _endofstorage - _start;
}
bool empty()
{
return _start == _last;
}
void reserve(size_t n)
{
if (n > size())
{
size_t sz = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * sz);
_start = tmp;
_last = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n,const T& val=T())
{
if (n <= size())
{
_last = _start + n;//Is to reduce the size, not expand
}
else
{
if (n > capacity())
{
reserve(n);
}
while(_last<_start+n)//It doesn't have to be equal to because_ Last is the last bit pointing to a valid character
{
*_last= val;
_last++;
}
}
}
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}
void Push_back(const T& x)
{
/*if (_last==_endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_last = x;
++_last;*/
insert(end(), x);
}
void Pop_back()
{
assert(!empty());
--_last;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _last);
if (_last == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}//This sentence is to improve reusability and can be used directly to Push_back for reuse
//size_t len = pos - _start;
//iterator end = _last + 1;
//if (_last == _endofstorage)
//{
// reserve(capacity() + 1);
//}
//pos = _start + len;// Note: after reopening the space, POS also becomes a wild pointer; So we need to get it back
//end = _last;// Note: end must be written once after the if statement, because the reserve function will reopen the space, otherwise end will become a wild pointer
iterator end = _last;
while (end >= pos)
{
*end = *(end - 1);//Note -- end cannot be used here because the previous end will also be changed
--end;
}
*pos = x;
++_last;
return pos;//In order to give the user the ability to reuse the original pointed number and avoid the situation of wild pointer
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _last);
iterator end = pos + 1;
while (end < _last)
{
*(end - 1) = *end;//Note -- end cannot be used here because the previous end will also be changed
++end;
}
--_last;
return pos;//Similarly, in order to avoid the problem of wild pointer, give the user a return value, which is the next value after the deleted element
}
private:
iterator _start;
iterator _last;
iterator _endofstorage;
};
summary
vector is basically similar to string. We often use this container because it is a sequential structure, so it is very convenient for random access and tail insertion and tail deletion. However, for insertion and deletion (such as header plug deletion), it is also a deep copy, so we can use references as much as possible, which can reduce a lot of space
Finally, interested partners can take a look at the implementation of my String container