Handwritten Vector (imitating STL-vector) (only encapsulation idea)
/********************************************** ***************************
> File Name: vector.cpp
> Author:Xiao Yuheng
> Mail:[email protected]
> Created Time: Wed Nov 1 07:04:57 2023
*************************************************** ************************/
?
#include <iostream>
#include <cstring>
?
using namespace std;
?
int *allocate(int n) { return new int[n]; }
void destroy(int *data) { delete[] data; }
?
class Vector{
public:
Vector(int n = 0) : n(n), first(n > 0 ? allocate(n) : nullptr), last(first + n), now(first + n) {};
Vector(const Vector & amp;);
int *insert(int *, const int & amp;);
void __insert(int *, const int & amp;);
void push_back(const int & amp;);
int size() { return now - first; }
int & amp;operator[](int ind) { return *(first + ind); }
int front() { return *first; }
int back() { return *(now - 1); }
int *begin() { return first; }
int *end() { return now; }
void pop_back();
void clear() { now = first; }
void erase(const int, const int);
bool empty() { return now == first ? true : false; }
~Vector();
private:
int n;
int *first, *last, *now;
};
?
void construct(int *now, const int & amp;x) { new(now) int(x); }
?
// copy construction
Vector::Vector(const Vector & amp;vec) : n(vec.n),
first(n > 0 ? allocate(n) : nullptr),
last(first + n),
now(first + (vec.now - vec.first)) {
for (int i = 0; i < n; i + + ) {
construct(first + i, vec.first[i]);
}
}
?
int *copyInt(int *nowBegin, int *oldBegin, int *oldEnd) {
memmove(nowBegin, oldBegin, sizeof(int) * (oldEnd - oldBegin));
return nowBegin + (oldEnd - oldBegin);
}
?
void Vector::__insert(int *ind, const int & amp;x) {
if (now != last) {
construct(now, *(now - 1));
+ + now;
copyInt(ind + 1, ind, now - 1);
*ind = x;
}
else {
const int oldSize = size();
const int len = oldSize != 0 ? 2 * oldSize : 1;
int *newFirst = allocate(len);
int *newNow = newFirst;
newNow = copyInt(newFirst, first, ind);
construct(newNow, x);
+ + newNow;
newNow = copyInt(newNow, ind, last);
destroy(first);
first = newFirst;
now = newNow;
last = newFirst + len;
}
}
?
void Vector::__insert(int *ind, const int & amp;x) {
if (now != last) {
construct(now, *(now - 1));
+ + now;
copyInt(ind + 1, ind, now - 1);
*ind = x;
}
else {
// Assign new address
const int oldSize = size();
const int len = oldSize != 0 ? 2 * oldSize : 1;
int *newFirst = allocate(len);
int *newNow = newFirst;
//Move the address to the new address
newNow = copyInt(newFirst, first, ind);
construct(newNow, x);
+ + newNow;
newNow = copyInt(newNow, ind, last);
// Delete source address
destroy(first);
// update address
first = newFirst;
now = newNow;
last = newFirst + len;
}
}
?
void Vector::push_back(const int & amp;x) {
if (now != last) {
construct(now, x);
+ + now;
}
else
__insert(now, x);
}
?
void Vector::pop_back() {
if (empty()) return ;
--now;
}
?
void Vector::erase(const int first, const int last) {
copyInt(this->first + first, this->first + last + 1, now);
now -= (last - first + 1);
}
?
Vector::~Vector() {
delete[] first;
}
?
int main() {
Vectorvec;
cout << "push_back : " << endl;
for (int i = 0; i < 10; i + + ) {
vec.push_back(i);
}
for (int i = 0; i < vec.size(); i + + ) {
cout << vec[i] << endl;
}
cout << "pop_back : " << endl;
while (vec.begin() != vec.end()) {
vec.pop_back();
}
cout << vec.size() << endl;
cout << "insert : " << endl;
for (int i = 0; i < 10; i + + ) {
vec.insert( & amp;vec[0], i);
}
for (int i = 0; i < vec.size(); i + + ) {
cout << vec[i] << endl;
}
cout << "erase(first, last) : " << endl;
vec.erase(1, 5);
for (int i = 0; i < vec.size(); i + + ) {
cout << vec[i] << endl;
}
cout << "clear() : " << endl;
vec.clear();
cout << vec.size() << endl;
return 0;
}
Analysis
I feel that the key points in this code are the push_back() function and the insert() function (because I understand this little thing). Let me compare it below. Source code to explain your own code.
push_backAnalysis
Let’s first take a look at what the source code in stl looks like:
What does this paragraph in the source code mean? Here’s my opinion:
// What do _M_finish and _M_end_of_storage mean respectively? Let me tell you my opinion (simple first-hand analysis) // _M_finish is the tail address of the number currently stored in the array // _M_end_of_storage is the tail address of the array space allocated // Expand the first address of a _M_start array // Okay, let’s look down now
In line 339, it makes a judgment to determine whether the space is full. If not, we add the value of __x to the array, and then move the address of _M_finish to Move one position later.
Let’s first take a look at how construct is implemented in the source code. The source code is as follows:
We can find that this place is implemented using an in-situ structure. Let’s take a look at my code.
void construct(int *now, const int & amp;x) { new(now) int(x); }
?
void Vector::push_back(const int & amp;x) {
if (now != last) {
construct(now, x);
+ + now;
}
else
__insert(now, x);
}
It can be found that the structure is exactly the same (if you don’t have your own thoughts, learn to write first, hahahahahahahahahaha), but what? What it passes is a template type, and then it is constructed in-situ (since I haven’t learned it yet, I won’t write it yet). It can be applied to many situations. If a pointer type is passed in, it can also be constructed in-situ. It’s easy to solve. We only have one int type here, but the design idea should be like this.
If the space is full, we call the _M_insert_aux() function. Let’s go in and take a look. What is this function?
Huo, it’s such a big area, let’s analyze it slowly. Let’s first take a look at the name _M_insert_aux(). Why does this name seem to be a branch of insert? Why doesn’t it look like what the push_back function should call? Let’s think about it, can push_back and insert call the same function? Is push_back a special insert? (The insertion location is the tail address) Yes, this is the first point I learned, the reusability of functions, the same function can be called. We will talk about this code when we talk about insert below.
insertAnalysis
Let’s start with the source code first.
He first asked how far his insertion position was from the starting position. Why did he ask for this value? what’s the function? He finally returned an address, but isn’t begin() + __n the same as __position? No, no, this is different, because our begin() will change, because we may perform expansion operations, and then begin will change, so We need to first ask for the value of __n so that we can finally return it. Okay, let’s continue looking down.
In the 362 lines of code, he first made a judgment to determine whether the array is full, and inserted at the end. If so, we will perform the same operation as if push_back is not full. We Omit it here. If it is full, call the _M_insert_aut function.
Let’s take a look at the core code (I think). It first makes a judgment to determine whether the function is full. If not, we call the construct function and first put the _M_finishThe value of this bit is occupied, then run + + _M_finish, and then perform a copy_backward function. We enter this function to see what is inside thing:
After continuous calls, such a function was finally called. What does this function do? ? Explanation: memmove is a C standard library function used to move a piece of data in memory. Can it handle the situation where the source address and the target address overlap? Yes, this is a function that moves data, so in our code above, it moves the data back one space, and then assigns the value to __position
What should I do if it’s full? This is how it is handled in the source code:
-
First record the size of the source array (644)
-
I am wondering how much internal division needs to be expanded (645)
-
Then allocate memory (646)
-
Move the first half of the data into the new array (649)
-
Then insert the value we need to insert (650 651)
-
Finally, move the second half to the new array (652)
-
Clear the original array (656)
-
Update your address (658 659 660)
Ok, this is my understanding of the source code. Now please take a look at our code:
void Vector::__insert(int *ind, const int & amp;x) { if (now != last) { construct(now, *(now - 1)); + + now; copyInt(ind + 1, ind, now - 1); *ind = x; } else { // Assign new address const int oldSize = size(); const int len = oldSize != 0 ? 2 * oldSize : 1; int *newFirst = allocate(len); int *newNow = newFirst; //Move the address to the new address newNow = copyInt(newFirst, first, ind); construct(newNow, x); + + newNow; newNow = copyInt(newNow, ind, last); // Delete source address destroy(first); // update address first = newFirst; now = newNow; last = newFirst + len; } } ? int *Vector::insert(int *ind, const int & amp;x) { int __n = ind - begin(); if (now != last & amp; & amp; ind == end()) { construct(now, x); + + now; } else { __insert(ind, x); } return begin() + __n; }My code is basically the same as what I analyzed. There are no changes. You can take a look.