We must have come into contact with vector when we were learning data structures before. It is the sequence table in our data structure. We have implemented it using C language before.
my_road: my code (gitee.com)
This is the code I use to implement vector in C language; we have to write a lot of things when implementing vector; every time we want to use a data structure such as a sequence table, we need to make a sequence table by ourselves, or complex Use the sequence table you have written; such a process must be troublesome; in order to solve this trouble, our C++ wrote a vector for us in the STL container. We can directly call it to use this vector, which is convenient. our programming;
Next, let’s talk about the various interfaces and underlying layers of stl_vector:
As always, open our more authoritative website first:
cplusplus.com/reference/vector/vector/
Documentation about our vector is written at this URL:
When we click on the website, we can see this interface, all in English. We may be a little uncomfortable at first, but we must slowly learn to read English documents, which is a necessary requirement in our future work (it is really not possible We can also combine reading with translation)
As we scroll down, we can see the various interfaces of vector:
Although the interfaces here seem to be many, they are much simpler than the interfaces in our string;
To look at a class, we need to first know its members and how it is constructed. We first look at the constructor of our vector and its members:
No-argument constructor, vector members and destructor:
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()//Constructor, the initialization list is written as default parameters
{}
~vector()//Destruction
{
delete[]_start;
}
private:
T* _start=nullptr;
T* _finish = nullptr;
T* _end_of_storage = nullptr;
};
Let’s first look at our parameterless constructor and its members. The bottom layer is like this;
Our vector member variables in C++ no longer write members like capacity and size like in C (they are written as function interface calls), but are written as three pointer variables; among these three pointers, _start points to us The first element of the vector, _finish, points to the next position of our last element, and _end_of_storage points to the next position of our opened space;
Expansion function reverse, resize
reverse:
cplusplus.com/reference/vector/vector/resize/cplusplus.com/reference/vector/vector/reserve/cplusplus.com/reference/vector/vector/resize/
resize:
cplusplus.com/reference/vector/vector/resize/
The above are the parameters and function types of our reverse and resize; we can also learn about it through the URL I gave above;
First, let’s talk about reverse. Reverse is a function used to open up a space as large as n (the parameters we pass) val type data. If n is smaller than the space of the original data, reverse will not operate; if we open up a new space If there is still data in the original space, we need to move the original data to the new space and then release the original space; this can be better understood by combining the following code:
void reserve(size_t n)//expansion
{
if (n > capacity())
{
//T here is the template parameter, which is the type of our data. We can understand it by looking at our code above.
T* tmp = new T[n];
size_t sz = size();
if (_start)//If our original space is not empty, we still need to move the original data
{
memcpy(tmp, _start, n*sizeof(T));
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
We use new to open up a space as large as n T for our _start, and let our _start, _finish and _end_of_storage point to the corresponding locations;
Resize also opens up space of n sizes, but if n is smaller than our original space, we will delete the extra n data and move our _finish position to _start + n. If n is greater than If the original data size is the same, all data from the remaining data to the nth element in the space will be changed to the corresponding val (the initialization number passed, the default is the anonymous object T (), our anonymous objects and temporary objects have constant Therefore, const modification is required, and const object references can also extend the life of temporary objects); if there is not enough space, expand the capacity;
The following is the code I simulated to implement, which can help with understanding:
void resize(size_t n, const T & amp; data = T())//Initialize and expand
{
if (n < size())
{
_finish = _start + n;
return;
}
if (n > capacity())
{
reserve(n);
}
/*iterator it = _finish;
while (it != _start + n)
{
*it = data;
it++;
}
_finish = _start + n;*/
while (_finish != _start + n)
{
*_finish = data;
_finish + + ;
}
}
[]Operator overloading
Because our vector is no longer an object like a pointer, it is a class object, so we can only randomly access each element after overloading [];
T & amp; operator [](size_t pos)//[] operator overloading
{
assert(pos < size());
return _start[pos];
}
const T & amp; operator [](size_t pos)const//[] operator overloading
{
assert(pos < size());
return _start[pos];
}
Iterator
As the name suggests, iterator is a tool used to iterate through our data. We have written iterators in string before. The reason why our iterator exists is to provide our container with a universal traversal tool. Although our string and our Current vectors can be traversed without iterators (they are all continuous spaces that support random access), but later when we encounter discontinuous spaces such as linked lists and numbers, it will be difficult to traverse, so We need a common concept like iterators so that we can traverse all containers; this can also simplify our learning; the vector iterator in our g++ version uses an iterator made of native pointers, and the iterator in our vs version is Pointers made using encapsulated classes;
Here we simulate the implementation of some iterators under the g++ version:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
We can also traverse the vector through such an iterator;
for example:
iterator it = _finish;
while (it != _start + n)
{
cout<<*it;
it++;
}
_finish = _start + n;
This is the iterator usage of traversing the vector and printing each data
Various interfaces
size_t capacity()const
{
return _end_of_storage - _start;
}
\t\t
size_t size()const
{
return _finish - _start;
}
void swap(vector<T> & amp; v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
These interfaces can return the number of data in our vector (size), the number of data that our space can accommodate (capacity), and can also exchange data between two vectors (swap);
Insert and delete
With the above functions, we can perform addition and deletion work. In fact, it is just adding and deleting at specified locations. It is easy to understand here. You can understand it by looking at the code.
iterator insert(iterator pos, const T & amp; data)//Insert data to pos position - increase
{
assert(pos>=begin() & amp; & amp;pos<=end());
if (_end_of_storage == _finish)//Expansion
{
size_t len = pos - _start;//After expansion, our iterator will become invalid and we need to find pos again.
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator it = end();
while (it > pos)//Move data
{
*it = *(it - 1);
it--;
}
*it = data;
_finish + + ;
return it;
}
iterator erase(iterator pos)//Delete pos position data - delete
{
assert(pos >= begin() & amp; & amp; pos < end());
iterator it = pos + 1;
while (it < end())
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
void push_back(const T & amp; data)//Tail insertion
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = data;
_finish + + ;
}
void pop_back()//Tail deletion
{
assert(size() > 0);
_finish--;
}
Constructor, copy construction, assignment operator overloading:
Because our _start, _finish, _end_of_storage are all pointers, they are all member variables of the built-in type. The built-in type member variable can find its declaration location when initializing the list and then initialize it at the declaration location; this is what we have here situation, so we need to pay attention to the fact that when we call these constructors, we initialize our members in the initialization list:
private: T* _start=nullptr; T* _finish = nullptr; T* _end_of_storage = nullptr;
Construction, copy construction:
Assignment operator overloading:
vector(size_t n, const T & amp; data = T())//Constructor
{
reserve(n);
while (_finish != _end_of_storage)
{
*_finish = data;
_finish + + ;
}
}
vector(int n, const T & amp; data = T())//Constructor
{
reserve(n);
while (_finish != _end_of_storage)
{
*_finish = data;
_finish + + ;
}
}
template <class InputIterator>
vector(InputIterator first,InputIterator last)//Use iterator to construct
{
size_t sz = last - first;
reserve(sz);
iterator it = first;
while (_finish != _end_of_storage)
{
*_finish = *it;
it++;
_finish + + ;
}
}
void swap(vector<T> & amp; v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T> & amp; operator =(vector<T> v)//Assignment operator overloading
{
swap(v);
return *this;
}
vector<T>(const vector<T> & amp; v)//copy construction
{
reserve(v.capacity());
const_iterator it = v.begin();
while (it != v.end())
{
*_finish = *it;
_finish + + ;
it++;
}
}
//vector(const vector<T> & amp; v)//copy construction
//{
// reserve(v.capacity());
// for (size_t i = 0; i < v.size(); + + i)
// {
// _start[i] = v._start[i];
// }
//}
The above is what I said about stl_vector;
2023.11.8