Table of contents
Insert an element at a certain position insert()
overview
The underlying principle of the vector container is actually a sequence table, which encapsulates a pointer (pointing to the open array) and two (array related parameters, the number of array elements and the size of the open space) into a class as attributes of the class. Then realize the function of the vector container by defining various interface functions as member functions.
Note: The article draws on the following blog, thank you for sharing, let me learn more knowledge, hold hands together https://blog.csdn.net/weixin_50941083/article/details/122354948
vector class definition
The vector container is actually a class template, which allows the container to store various types of elements. The definition of the vector class is as follows, including attributes, member functions, and operator overloading. MyVector.h file.
#pragma once
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
#define InitCapacity 8
//Create vector class template
template<typename T>
class vector {
public:
typedef T dataType;//rename the type
typedef T* iterator;//The meaning of iterator in vector
public:
dataType* _data;//The vector attribute stores data space
int _size;//Amount of stored data
int _capacity;//The size of the allocated space
public:
vector();//no-argument constructor initialization
vector(const vector& vec);//copy constructor
vector& operator=(const vector& vec)//assignment operator overloading
{
//Release original space Deep copy
delete[] this->_data;
//copy over
this->_capacity = vec._capacity;
this->_data = new dataType[this->_capacity];
for (int i = 0; i < vec._size; i++) {
this->_data[i] = vec._data[i];
}
this->_size = vec._size;
return *this;
}
bool operator==(const vector& vec)//Equals relational operator overloading
{
if (this->_size != vec._size)
return false;
for (int i = 0; i < vec._size; i++) {
if (this->_data[i] != vec._data[i])
return false;
}
return true;
}
dataType& operator[](size_t i)//[] operator overloading
{
return this->_data[i];
}
void check_capacity();//check capacity
void push_back(dataType val);//Insert an element val at the end
void insert(iterator pos, dataType val);//Insert element val at a certain position
void pop_back();//tail delete
void erase(iterator pos);//delete a positional element
dataType front();//Get the header element
dataType back();//Get the tail element
iterator begin();//head pointer
iterator end();//tail pointer
int size();//number of elements
int capacity();//Capacity
bool empty();//Is it empty
~vector();//destructor release
};constructor and destructor
The constructor and destructor are the first thing to be defined when creating a class. The constructor is mainly used to initialize member variables when creating an object; the destructor is mainly used to release the space allocated for the instantiated object. When an object leaves itself The destructor will be called automatically when the scope of the object is set to release the space.
template<typename T>//The out-of-class implementation of a class template member function must be marked with a template
vector<T>::vector() {
this->_data = NULL;
this->_size = 0;
this->_capacity = 0;
}
template<typename T> //copy constructor
vector<T>::vector(const vector& vec) {
this->_capacity = vec._capacity;
this->_data = new dataType[this->_capacity];
for (int i = 0; i < vec._size; i++) {
this->_data[i] = vec._data[i];
}
this->_size = vec._size;
}
template<typename T>//And each member function must be marked with a template, and the .cpp file must be included when using it
vector<T>::~vector() {
delete[] this->_data;
this->_data = NULL;
this->_capacity = 0;
this->_size = 0;
}Tail plug push_back()
When inserting elements, it is necessary to judge whether the size of the opened space is sufficient, thus creating the check_capacity() function:
template<typename T>
void vector<T>::check_capacity() {//check capacity
if (0 == this->_capacity) {//initial
this->_capacity = InitCapacity;
this->_data = new dataType[this->_capacity];
return;
}
if (this->_size == this->_capacity) {//already filled
this->_capacity *= 2;
dataType* tmp = new dataType[this->_capacity];//Create a temporary space to store previous data
for (int i = 0; i < this->_size; i++) {
tmp[i] = this->_data[i];
}
delete[] this->_data;//free up the original space
this->_data = tmp;//Now point to the newly created space
}
}
template<typename T>
void vector<T>::push_back(dataType val)//Inserting an element val at the end needs to judge the capacity
{
this->check_capacity();//Judgment capacity
this->_data[this->_size] = val;
this->_size++;
}Insert an element at a certain position insert()
To insert an element at a certain position, the principle is as follows:
template<typename T>
void vector<T>::insert(iterator pos, dataType val)//Insert element val at a certain position
{
this->check_capacity();//Judgment capacity
int index = pos - this->_data;
for (int i = this->_size - 1; i >= index; i--) {
this->_data[i + 1] = this->_data[i];
}
this->_data[index] = val;
this->_size++;
}other member functions
template<typename T>
void vector<T>::pop_back()//tail delete
{
this->_size--;
}
template<typename T>
void vector<T>::erase(iterator pos)//delete a positional element
{
int index = pos - this->_data;
for (int i = index; i < this->_size - 1; i++) {
this->_data[i] = this->_data[i + 1];
}
this->_size--;
}
template<typename T>
T vector<T>::front()//Get the header element
{
return this->_data[0];
}
template<typename T>
T vector<T>::back()//Get the tail element
{
return this->_data[this->_size - 1];
}
template<typename T>
T* vector<T>::begin()//head pointer
{
return this->_data;
}
template<typename T>
T* vector<T>::end()//tail pointer
{
return this->_data + this->_size;
}
template<typename T>
int vector<T>::size()//number of elements
{
return this->_size;
}
template<typename T>
int vector<T>::capacity()//Capacity
{
return this->_capacity;
}
template<typename T>
bool vector<T>::empty()//Is it empty
{
return this->_size == 0;
}
Test code test.cpp
#include"MyVector.h"
#include"MyVector.cpp"
int main() {
vector<string> vec;//No parameter construction
vec.push_back(string("xiaoming"));//tail plug
vec.push_back(string("xiojun"));
vec.push_back(string("xiaomei"));
vec.push_back(string("xiaoxin"));
vector<string> vec1(vec);//copy construction
if (vec == vec1) {//Overloading the == operator
cout << "vec vec1 two sequence tables are equal" << endl;
}
vector<string> vec2 = vec;//overloaded = operator
if (vec1 == vec2) {
cout << "vec1 vec2 two sequence tables are equal" << endl;
}
cout << "element is vec[1] = " << vec[1] << endl;//Overloading the [] operator
vec.insert(vec._data, string("xiaofang"));//Insert at a certain position, iterator pass parameter
vec.pop_back();//tail delete
vec.pop_back();
vec.erase(vec._data);//delete element
cout << "The first element is:" << vec.front() << endl;
vec.push_back(string("xiaocao"));
vec.push_back(string("xiaotang"));
cout << "The last element is:" << vec.back() << endl;
cout << "The number of elements is:" << vec.size() << endl;
cout << "The space capacity is:" << vec.capacity() << endl;
cout << "Is it empty:" << vec.empty() << endl;
cout << "traverse the entire sequence table************************" << endl;
for (vector<string>::iterator it = vec.begin(); it != vec.end(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}Summarize
The article describes the process of implementing vector containers through C++. During this process, the understanding of C++ classes and object characteristics has been deepened; the realization principle of standard class templates has been understood; knowledge of related data structures, memory allocation and release, etc. has also been used. A simple and meaningful experiment.